Bits Reverse
题意：给出两个数，每次操作其中一个数，将其二进制位上连续的三个数翻转，求最小的操作次数
Solution
每次操作相当于交换了左右两个二进制位的数，所以一次操作只会改变奇数位/偶数位上的数，考虑到只用求最小的操作次数，我们可以将每个数的二进制位上的1所在的位置分奇偶存一下，然后把对应位置相差的距离给加到答案的贡献里即可
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
int x,y;cin>>x>>y;
int cnt=0;
int temp=x;
int flag=0;
vector<int>x1,x2,y1,y2;
while(temp>0)
{
if(temp&1)
{
if(cnt&1)x1.push_back(cnt);
else x2.push_back(cnt);
}
temp>>=1;
cnt++;
}
temp=y;
cnt=0;
while(temp>0)
{
if(temp&1)
{
if(cnt&1)y1.push_back(cnt);
else y2.push_back(cnt);
}
temp>>=1;
cnt++;
}
reverse(x1.begin(),x1.end());
reverse(x2.begin(),x2.end());
reverse(y1.begin(),y1.end());
reverse(x2.begin(),x2.end());
if(x1.size()!=y1.size()||x2.size()!=y2.size())
{
cout<<"Case "<<i<<": -1\n";
continue;
}
int ans=0;
for(int i=0;i<x1.size();i++)
{
if(x1[i]==y1[i])continue;
else ans+=abs(x1[i]-y1[i])/2;
}
for(int i=0;i<x2.size();i++)
{
if(y2[i]==x2[i])continue;
else ans+=abs(y2[i]-x2[i])/2;
}
cout<<"Case "<<i<<": "<<ans<<"\n";
}
}
Empty Squares
题意：有一个大小为1*N的矩阵，现在有长为1,2,...,n，宽都为1的方块，每个方块只能用一次，先填入一个长为k的方块，并给出它左边空格的长度，问最少剩余方块数是多少
Solution
我们可以枚举填入左边的方块长度和填入右边的方块长度，看是否能满足刚好填入这么多即可
情况有点多，需要仔细讨论
int f(int i,int k,int j)
{
if(i!=k&&k!=j&&i!=j)return 0;
else if(i==k&&i==j)
{
if(k>=5)return 0;
else if(k==1||k==4)return 2;
else if(k==2||k==3)return 3;
}
else
{
if(i>j)swap(i,j);
if(i==k)
{
if(i==1||i==2)return 1;
else if(i>=3)return 0;
}
else if(j==k)
{
if(k==1)return 1;
if(k==2)return 1+i;
else if(k==3)return i;
else if(k==4&&(i==0||i==2))return 0;
else if(k==4&&(i==1||i==3))return 1;
else return 0;
}
else if(i==j)
{
if(i==0)return 0;
if(i<k)
{
if(k==2)return 1;
else if(k==3)return 1;
else if(k>=4&&i<=2)return 1;
else if(k>=4&&i>=3)return 0;
}else
{
if(i==2)return 2;
else if(i==3)return k;
else if(i==4&&(k==1||k==3))return 1;
else if(i==4&&k==2)return 0;
else if(i>=5)return 0;
}
}
}
}
void solve()
{
int n,k,e;cin>>n>>k>>e;
int ll=e,rr=n-k-e;
int ans=n;
for(int i=0;i<=ll;i++)
{
for(int j=0;j<=rr;j++)
{
ans=min(ans,n-(i+j+k-f(i,k,j)));
}
}
cout<<ans<<"\n";
}
Wall Painting
题意：给出一个数组，对于k=1,2,...,n，在其中选出k个不同的数进行异或，求对于每一个k，C(n,k)种方案的异或和
Solution
不难联想到二进制，因为对于每一个k，C(n,k)种方案必须都覆盖到，所以每一位上的贡献都是独立的，所以我们可以枚举选择当前二进制位中的1的个数，这样也可以得到选择0的个数，然后计算它们的贡献
void solve()
{
int n;
while(cin>>n)
{
for(int i=0;i<=40;i++)p[i]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
int cnt=0;
int temp=a[i];
while(temp>0)
{
if(temp&1)p[cnt]++;
cnt++;
temp>>=1;
}
}
for(int k=1;k<=n;k++)
{
int ans=0;
int now=1;
for(int i=0;i<=40;i++)
{
int cnt0=n-p[i];
for(int j=1;j<=min(k,p[i]);j++)
{
if(!(j&1))continue;
if(k-j>cnt0)continue;
ans=(ans+(((C(cnt0,k-j)*C(p[i],j))%mod)*now)%mod)%mod;
}
now=(now*2)%mod;
}
cout<<ans;
if(k!=n)cout<<" ";
}
cout<<"\n";
}
}
Little Tiger vs. Deep Monkey
题意：老虎和猴子答题，猴子每道题答对的概率都是0.5，老虎至少要拿多少分才能使得不输的概率至少是p
Solution
我们可以dp处理出猴子最终成绩的每一分的概率，然后从小到大加起来看到哪里才能至少到p即可
void solve()
{
memset(dp,0,sizeof(dp));
int n;double p;cin>>n>>p;
for(int i=1;i<=n;i++)cin>>a[i];
int sum=a[1];
dp[1][0]=0.5;
dp[1][a[1]]=0.5;
for(int i=1;i<n;i++)
{
sum+=a[i+1];
for(int j=0;j<=sum;j++)
{
dp[i+1][j]=dp[i][j]*0.5;
if(j>=a[i+1])dp[i+1][j]+=dp[i][j-a[i+1]]*0.5;
}
/*for(int k=0;k<=sum;k++)cout<<dp[i][k]<<' ';
cout<<"\n";*/
}
double res=0;
int pos;
/*for(int k=0;k<=sum;k++)cout<<dp[n][k]<<' ';
cout<<"\n";*/
for(int i=0;i<=sum;i++)
{
res+=dp[n][i];
if(res>=p)
{
pos=i;
break;
}
}
cout<<pos<<"\n";
}
Greatest Common Divisor
题意：给一个数组，每次操作可以对所有数+1，至少要多少次才能使得所有数的gcd>1
Solution
因为gcd(a,b)=gcd(a,b-a)，令所有相邻的数的差的gcd得到的数为res，第一个数进行若干次操作之后得到的数为x，要使得gcd(res,x)大于1，那么只需找一下res的最小质因子即可
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
int res=0;
for(int i=1;i<n;i++)
{
p[i]=a[i+1]-a[i];
}
res=0;
for(int i=1;i<n;i++)
{
res=gcd(res,p[i]);
}
if(res==1)
{
cout<<"Case "<<(ttime++)<<": "<<"-1"<<"\n";
return;
}else if(res==0)
{
cout<<"Case "<<(ttime++)<<": "<<(a[1]==1?1:0)<<"\n";
return;
}
int ans=1e18;
for(int i=2;i*i<=res;i++)
{
if(res%i==0)
{
while(res%i==0)res/=i;
if(a[1]%i!=0)
ans=min(ans,i-(a[1]%i));
else ans=0;
}
}
//cout<<res<<"\n";
if(res>1)
{
if(a[1]%res!=0)
ans=min(ans,res-(a[1]%res));
else ans=0;
}
cout<<"Case "<<(ttime++)<<": "<<ans<<"\n";
}
Inscryption
题意：有一个人走在长为n的森林里，他会遇到很多数字，其中
1：代表获得一个攻击力为1的叉子
-1：失去一个叉子，并将其攻击力加到另一个叉子上，如果他只有一个叉子，则他不能走出森林
0：可以进行上述两个事件中的一个
初始时自带一个攻击力为1的叉子，问他能否走出森林，并且走出森林后攻击力平均值最大是多少
Solution
贪心地想，首先要满足走出森林，那么我们可以把所有的0都看成1，然后从后往前把0变成-1，对答案取大即可
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int num=1,sum=1;
int cnt1=0,cnt0=0,cnt2=0;
for(int i=1;i<=n;i++)
{
if(a[i]==-1)
{
if(num==1)
{
cout<<"-1\n";
return;
}
cnt2++;
num--;
}else
{
num++;
sum++;
if(a[i]==0)cnt1++;
else cnt0++;
}
p[i]=num;
}
double z=(1.0*sum)/(1.0*num);
int ans1=sum,ans2=num;
int low=1e18;
for(int i=n;i>=1;i--)
{
low=min(low,p[i]);
if(a[i]!=0)continue;
if(low-2<1)break;
num-=2;
sum--;
double pp=(1.0*sum)/(1.0*num);
if(pp>z)
{
z=pp;
ans1=sum,ans2=num;
}
low-=2;
}
int kk=gcd(ans1,ans2);
ans1/=kk,ans2/=kk;
cout<<ans1<<" "<<ans2<<"\n";
}
Money Game
题意：有n个玩家，初始都有一个钱数，操作1次会让第1个玩家给第2个玩家自己当前钱数的一半，第2个玩家再给第3个玩家自己当前钱数的一半，以此类推，第n个玩家会给第一个玩家自己当前钱数的一半，现在进行20221024次操作，问最终的所有玩家的钱数
Solution
打表找规律，发现最后第一个玩家的钱数是其他任意一个玩家的两倍，其他玩家的钱数都相同
void solve()
{
int n;cin>>n;
double sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
}
for(int i=1;i<=n;i++)
{
if(i!=1)
a[i]=sum/((n+1)*1.0);
else
a[i]=sum*2.0/((n+1)*1.0);
}
for(int i=1;i<=n;i++)cout<<fixed<<setprecision(6)<<a[i]<<" ";
}
No Bug No Game
题意：有一个大小为k的背包，和n个不同价值的物品，第i个物品如果能完整地被装入背包中，会给答案贡献p[i][n]的点数，如果第j个物品不能被完整装入背包中，会给答案贡献p[i][背包剩余大小]，如果当前背包已满，则对答案无贡献，问答案最大是多少
Solution
dp一下，定义dp[i][j][0/1]表示为当前为第i个，背包里面已经有了大小为j的物品，并且在前i个物品中是否有未能完整装满的物品
每次转移的时候顺带转移一下如果当前物品装1,2,...,sz[i]-1的情况
void solve()
{
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>p[i];
for(int j=1;j<=p[i];j++)
{
cin>>a[i][j];
}
}
int ans=0;
memset(dp,-INF,sizeof(dp));
dp[0][0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=k-1;j>=0;j--)
{
dp[i][j][0]=dp[i-1][j][0];
dp[i][j][1]=dp[i-1][j][1];
if(p[i]<=k-j)
{
dp[i][j+p[i]][0]=max(dp[i][j+p[i]][0],dp[i-1][j][0]+a[i][p[i]]);
dp[i][j+p[i]][1]=max(dp[i][j+p[i]][1],dp[i-1][j][1]+a[i][p[i]]);
}
for(int m=1;m<p[i];m++)
{
if(j+m<=k)dp[i][j+m][1]=max(dp[i][j+m][1],dp[i-1][j][0]+a[i][m]);
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=k;j++)
{
ans=max(dp[i][j][0],ans);
}
ans=max(ans,dp[i][k][1]);
}
cout<<ans<<"\n";
}
Modulo Ruins the Legend
题意：有一个数组，给这个数组所有数加上s+kd(k=1,2,...,n)，问使得对m取模后最小的s，d组合
Solution
令原数组和为sum，操作后变为sum+ns+d(1+n)n/2
令g1=gcd(n,(1+n)/2)
由裴蜀定理可得k*g1+sum
求这个值模m的最小值，我们可以给它加上t*m，这样不会影响答案
那么我们就要让(k*g1+tm)%m+sum%m尽量的小，也就是尽可能地靠近m的倍数
再进行一次裴蜀定理，可得(p*g2%m+sum%m)%m，此时就可以得到p
\[p=[\frac{m-sum\%m}{g2}] \]通过p可以求得答案的最小值，然后反推得到k*g1的k以及s,d
void solve()
{
int n,m;cin>>n>>m;
int sum=0;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
sum=(x+sum)%m;
}
int a=n,b=(n+1)*n/2;
int x,y;
exgcd(a,b,x,y);
int g1=gcd(a,b);
int g2=gcd(g1,m);
int k,t;
exgcd(g1,m,k,t);
int kk=(m-sum+g2-1)/g2;
cout<<kk*g2+sum-m<<"\n";
int cnt=kk*k%m;
cout<<(x*cnt%m+m)%m<<" "<<(y*cnt%m+m)%m;
}
Find Maximum
题意：有这样一个函数
f(0)=1,f(k)=f(k-1)+1(k%3!=0),f(k)=f(k/3)+1(k%3=0)
求区间[l,r]中f(i)的最大值
Solution
太神奇，很难，发现这是一道三进制题，f(i)其实是i的三进制位上的所有数的和与有效三进制数位个数的和
那么我们可以设一个x，令其等于r，然后从高到低遍历每一个有效三进制位上大于0的数，将其减一，那么我们就可以将所有比该位更低位的数都变成2，这样保证了答案最大
void solve()
{
int l,r;cin>>l>>r;
int x=r;
int ans=f(x);
int sum=0;
for(int i=38;i>=0;i--)
{
int tp=get_3(x,i);
if(tp)
{
int res=(tp-1)*p[i]+sum+p[i]-1;
if(res>=l)ans=max(ans,f(res));
sum+=tp*p[i];
}
}
cout<<ans<<"\n";
}