Wannafly挑战赛24游记
A - 石子游戏
题目大意：
A和B两人玩游戏，总共有\(n(n\le10^4)\)堆石子，轮流进行一些操作，不能进行下去的人则输掉这局游戏。操作包含以下两种：
- 把石子数为奇数的一堆石子分为两堆正整数个石子；
- 把两堆石子数为偶数的石子合并为一堆。
若两人都按照最优策略进行操作。求若A先手，最后谁能赢得比赛。
思路：
首先最优策略中一定是将奇数拆成\(1\)和另一个偶数，然后不断将所有偶数进行合并。
因此我们可以统计非\(1\)奇数的个数\(a\)和所有非\(1\)数的个数\(b\)。由此我们可以求出拆分次数和合并次数，根据操作次数的奇偶性判断即可。
源代码：
#include<cstdio>
#include<cctype>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
int main() {
const int n=getint();
int cnt=0,tmp=0,tot=0;
for(register int i=1;i<=n;i++) {
const int x=getint();
if(x==1) continue;
cnt++;
if(x&1) tot++;
}
while(cnt>1) {
tmp+=cnt/2;
cnt=cnt/2+cnt%2;
}
puts((tmp+tot)%2?"Alice":"Bob");
return 0;
}
B - 222333
题目大意：
给定质数\(p(p\le10^7)\)，一定存在\(m,n\)满足\(p|2^m3^n-1\)且\(m+n\le p\)。求数对\((m,n)\)。若存在多种，优先输出\(m+n\)最小的一种。若还有多中，优先输出\(m\)最小的一种。
思路：
\(p|2^m3^n-1\)意味着\(2^m3^n\equiv1\pmod{p}\)，即\(3^m\)在模\(p\)意义下是\(2^n\)的逆元。
而\(p\le10^7\)，因此我们可以先求出\(3^n\)的取值在模\(p\)意义下有多少种可能。然后枚举\(m\)，判断\(2^m\)的逆元是否有对应的\(3^m\)即可。
其中\(2^m\)的逆元不需要每次重新求，直接根据\(2^{-1}\)推即可。
小优化：当\(n\ge\)目前\(n+m\)的最小值时，直接跳出循环。
时间复杂度\(\mathcal O(10p)\)。
源代码：
#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef long long int64;
const int N=1e7+1;
int n,b[N];
inline void exgcd(const int &a,const int &b,int &x,int &y) {
if(!b) {
x=1,y=0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
inline int get_inv(const int &x) {
int ret,tmp;
exgcd(x,n,ret,tmp);
return (ret%n+n)%n;
}
int main() {
while(~scanf("%d",&n)) {
const int inv=get_inv(2);
for(register int i=1,p=3;i<=n;i++) {
if(!b[p]) b[p]=i;
p=p*3%n;
}
int min=INT_MAX,x,y;
for(register int i=1,q=inv;i<=n;i++) {
if(i>=min) break;
if(b[q]) {
if(i+b[q]<min) {
min=i+b[q];
x=i;
y=b[q];
}
}
q=(int64)q*inv%n;
}
printf("%d %d\n",x,y);
std::fill(&b[1],&b[n]+1,false);
}
return 0;
}
C - 失衡天平
题目大意：
有\(n(n\le100)\)个物品，每个物品有一个价值\(v_i(v_i\le100)\)。你可以每次选取两堆物品，若这两堆物品价值总和之差\(\le m(m\le100)\)则可以将这两堆物品全部取出。问最后最多取走多少价值的物品？
思路：
首先可以证明可以将这些取走物品分成两堆，使得价值和之差仍旧小于\(m\)。
\(f[i][j][k]\)表示前\(i\)个物品，一堆价值为\(j\)，一堆价值为\(k\)是否可行。使用滚动数组和bitset优化即可。
时间复杂度\(\mathcal O(\frac{n^5}{32})\)。
源代码：
#include<cstdio>
#include<cctype>
#include<bitset>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=101,M=1e4+1;
int a[N];
std::bitset<M> b[2][M];
int main() {
const int n=getint(),m=getint();
for(register int i=1;i<=n;i++) a[i]=getint();
std::sort(&a[1],&a[n]+1);
b[0][0]=true;
int sum=0;
for(register int i=1;i<=n;i++) {
const bool cur=i&1;
sum+=a[i];
for(register int j=0;j<=sum;j++) {
b[cur][j]|=b[!cur][j]<<a[i];
b[cur][j]|=b[!cur][j];
}
for(register int j=a[i];j<=sum;j++) {
b[cur][j]|=b[!cur][j-a[i]];
}
}
int ans=0;
for(register int i=0;i<=sum;i++) {
for(register int j=std::max(i-m,0);j<=std::min(i+m,sum);j++) {
if(b[n&1][i][j]) ans=std::max(ans,i+j);
}
}
printf("%d\n",ans);
return 0;
}