大桃子：
考虑枚举gcd最大值，要保证数列的和可以被gcd整除且商大于数列长度。
code:
#include
using namespace std;
int n,m;
int main()
{
cin>>n>>m;
for(int i=0;;i++)
{
if(m%(n+i)==0)
{
cout<<m/(n+i)<<endl;
return 0;
}
}
return 0;
}
大橘子：
使用桶计算旋转i次可以使多少人满意，取最大值即可。
code:
#include
using namespace std;
int n,ans,p[200010],cnt[200010];
int main()
{
cin>>n;
for(int i=0;i>p[i];
int tmp;
if(p[i]>i)
{
tmp=i+n-p[i];
}
else
{
tmp=i-p[i];
}
cnt[tmp]++;
cnt[(tmp-1+n)%n]++;
cnt[tmp+1]++;
}
cnt[0]+=cnt[n];
for(int i=0;i<n;i++)
{
ans=max(ans,cnt[i]);
}
cout<<ans;
return 0;
}
大苹果：
计数dp，分别统计考虑到第i位的情况下，最多可以存在几个A，AB，ABC。但由于题目要求的是在所有中可能的序列中的答案，所以在相同位置的ABC序列可能被统计多次，所以还要将对序列的统计细分到存在几个不确定的位置即"?，便于最后组合计数。
code:
#include
#define int long long
#define mod 1000000007
using namespace std;
int n,tot,cntA[100010][2],cntAB[100010][3],cntABC[100010][4],ans;
char s[100010];
int quick_pow(int x,int N,int m){
int res=1;
while(N>0){
if(N&1) res=res*x%m;
x=x*x%m;
N>>=1;
}
return res;
}
signed main()
{
cin>>(s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)
{
if(s[i]=='?') tot++;
}
for(int i=1;i<=n;i++)//1+
{
cntABC[i][0]=cntABC[i-1][0];
cntABC[i][1]=cntABC[i-1][1];
cntABC[i][2]=cntABC[i-1][2];
cntABC[i][3]=cntABC[i-1][3];
if(s[i]=='C'||s[i]=='?')
{
if(s[i]=='C')
{
cntABC[i][0]=(cntABC[i][0]+cntAB[i-1][0])%mod;
cntABC[i][1]=(cntABC[i][1]+cntAB[i-1][1])%mod;
cntABC[i][2]=(cntABC[i][2]+cntAB[i-1][2])%mod;
}
else
{
cntABC[i][1]=(cntABC[i][1]+cntAB[i-1][0])%mod;
cntABC[i][2]=(cntABC[i][2]+cntAB[i-1][1])%mod;
cntABC[i][3]=(cntABC[i][3]+cntAB[i-1][2])%mod;
}
}
cntAB[i][0]=cntAB[i-1][0];
cntAB[i][1]=cntAB[i-1][1];
cntAB[i][2]=cntAB[i-1][2];
if(s[i]=='B'||s[i]=='?')
{
if(s[i]=='B')
{
cntAB[i][0]=(cntAB[i][0]+cntA[i-1][0])%mod;
cntAB[i][1]=(cntAB[i][1]+cntA[i-1][1])%mod;
}
else
{
cntAB[i][1]=(cntAB[i][1]+cntA[i-1][0])%mod;
cntAB[i][2]=(cntAB[i][2]+cntA[i-1][1])%mod;
}
}
cntA[i][0]=cntA[i-1][0];
cntA[i][1]=cntA[i-1][1];
if(s[i]=='A'||s[i]=='?')
{
cntA[i][0]=(cntA[i][0]+(s[i]=='A'))%mod;
cntA[i][1]=(cntA[i][1]+(s[i]=='?'))%mod;
}
// cout<<cntAB[i][1];
}
ans=cntABC[n][0]*quick_pow(3,tot,mod)%mod;
ans=(ans+cntABC[n][1]*quick_pow(3,tot-1,mod)%mod)%mod;
ans=(ans+cntABC[n][2]*quick_pow(3,tot-2,mod)%mod)%mod;
ans=(ans+cntABC[n][3]*quick_pow(3,tot-3,mod)%mod)%mod;
cout<<ans;
return 0;
}
大苹果：
题目难点在于加了绝对值的情况下难以统计每个值对于答案的贡献。所以对结果进行分类讨论，这样就可以快速知道正数，负数对于答案的贡献是正还是负。随后排序贪心即可（当然直接暴力dp也行。
#include
using namespace std;
long long n,m,ans,a[1010],b[1010],c[1010],k1,k2,k3,dp[1010][1010];
int main()
{
cin>>n>>m;
for(int i=1;i>a[i]>>b[i]>>c[i];
}
for(int k=0;k<8;k++)
{
if(k==0) k1=1,k2=1,k3=1;
if(k==1) k1=1,k2=1,k3=-1;
if(k==2) k1=1,k2=-1,k3=1;
if(k==3) k1=-1,k2=1,k3=1;
if(k==4) k1=1,k2=-1,k3=-1;
if(k==5) k1=-1,k2=1,k3=-1;
if(k==6) k1=-1,k2=-1,k3=1;
if(k==7) k1=-1,k2=-1,k3=-1;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
dp[i][j]=1ll*INT_MIN*(INT_MAX-1);
}
}
for(int i=0;i<=n;i++) dp[i][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+k1*a[i]+k2*b[i]+k3*c[i]);
}
}
ans=max(ans,dp[n][m]);
}
cout<<ans;
return 0;
}
串串串：
发现对某个字符串x作k的答案为 x \oplus (x>>k)的后n-k位，又因为当一个序列不存在1后无论怎么操作都不会再出现1，有单调性，所以考虑倍增，计算对于每次选取计算x \oplus (x>>2^{p})即可。
code:
#include
#define N 10
using namespace std;
int len,n,ans;
char s[N];
int main()
{
while(scanf("%s",(s))!=EOF)
{
ans=0;
len=n=strlen(s);
bitsetbs(s),tmp;
for(int i=(1<=1;i>>=1)
{
if(i>n) continue;
tmp=bs^(bs>>i);
tmp=((tmp<>(N-n+i));
if(tmp.any())
{
bs=tmp;
ans+=i;
n-=i;
}
}
printf("%d\n",(ans+1)==len?-1:ans+1);
bs.reset();
tmp.reset();
}
return 0;
}
光明:
斜率优化。（我不会）