T1：666
发现长为 (s) 的串能从两个地方转移过来：
-
(frac{s}{2},frac{s}{3},frac{s}{4},...,frac{s}{k}) （(k|s)），代价为 (k)，即复制一次，粘贴 (k-1) 次
-
(s+1,s+2,...,s+k) 代价为 (k) ，即按撤销的次数
(n^2) 的DP就能写了
考场第一类转移代价写错了，外加时间卡成了 (200ms)，得到了 (14pts)
第二类转移发现 (f_s) 最多被 (f_{s+2}) 更新，证明不会
第一类转移比较神奇，玄学做法是 (f_s) 只会被 (f_{frac{s}{2}}) (f_{frac{s}{3}}) (f_{frac{s}{5}}) (f_{frac{s}{7}}) ，证明也不会
我的做法是后 (2w) 的数打表，能过
T2：春思
沙雕题
先考虑 (a=c^k) 即 (a) 只有一个因数的情况
手模一下，发现是个等差数列：
[ans=a imes frac{a^b-1}{a-1}
]
再用暴力搞搞其他的，发现答案是所有质因子的(ans)相乘
时间复杂度： (O(sqrt{n}))
注意底数为 (1) 的情况，即 质因子 (c mod 9901 = 1)，特判一下
ll ans=1;
for(register int i=1;i<=tot;i++){
if(a%prime[i]==0){
ll cnt=1,sum=0;
while(a%prime[i]==0)a/=prime[i],cnt*=prime[i],cnt%=mol,sum+=cnt;
if(prime[i]%mol!=1)ans=ans*(sum%mol*(qpow(cnt,b)-1)%mol*qpow(cnt-1,mol-2)%mol+1)%mol;
else ans=ans*((b+1)%mol)%mol;
if(a==1)break;
}
}
if((a-1)%mol!=0&&a!=1)ans=ans*(a%mol*(qpow(a%mol,b)-1)%mol*qpow(a-1,mol-2)%mol+1)%mol;
else if(a!=1)ans=ans*(b+1)%mol;
cout<<ans<<endl;
T3：密州盛宴
考场直接冲T4DP了，没开正解
正解是个贪心
无解一定是 (0) 的个数大于 (1) 的个数，否则一定有解
计后缀中 (0) 与 (1) 的差的最大值为 (maxsum)，答案一定是 (max(maxsum-1,0))
从后往前扫，如果0的个数大于1的个数，直接把0提至最前，对答案贡献 (+1)
后三十分随便搞搞就行了
while(1){
n=read(),m=read();
ans=-INF;
if(!n&&!m)break;
cnt0=cnt1=0;
for(int i=1,x;i<=m;i++){
cin>>s[i];
scanf("%lld",&a[i]);
}
for(int i=m;i>=1;i--){
len=s[i].size();
int cnt00=0,cnt11=0,Max=-INF;
for(int j=len-1;j>=0;j--){
if(s[i][j]=='0')cnt00++;
else cnt11++;
Max=max(cnt00-cnt11,Max);
// cout<<s[i][j]<<" asd "<<cnt00<<" "<<cnt11<<endl;
}
if(cnt00-cnt11<0)ans=max(ans,cnt0-cnt1+Max);
else ans=max(ans,cnt0-cnt1+(a[i]-1)*(cnt00-cnt11)+Max);
cnt0+=cnt00*a[i];
cnt1+=cnt11*a[i];
//cout<<i<<" "<<cnt0<<" "<<cnt1<<endl;
}
if(cnt1<n)puts("-1");
else printf("%lld
",max(ans-1,0LL));
}
T4：赤壁情
(60pts)随机化:
while(clock()/CLOCKS_PER_SEC<3.0){
random_shuffle(a+1,a+1+n);
sum=0;maxsum++;
for(int i=1;i<n;i++)sum+=abs(a[i]-a[i+1]);
if(sum>=m)ans++;
}
cnt=maxsum;
正解记搜优化DP，沽了