2024CSP-S第二轮（复赛）模拟赛
\(T1\) A. 坦白 \(30pts\)
-
部分分
-
\(30pts\) ：爆搜。
点击查看代码
ll ans[300010]; char s[300010]; int main() { freopen("confess.in","r",stdin); freopen("confess.out","w",stdout); ll t,n,cnt,i,j,k; __int128_t I=1ull<<63,tmp; I*=2; scanf("%lld",&t); for(k=1;k<=t;k++) { scanf("%s",s); n=strlen(s); memset(ans,-0x3f,sizeof(ans)); for(i=0;i<=(1<<n)-1;i++) { tmp=I; cnt=0; for(j=0;j<=n-1;j++) { if((i>>j)&1) { cnt++; tmp^=1; } else { if(s[j]=='+') { tmp++; } else { tmp--; } } } ans[cnt]=max(ans[cnt],(ll)(tmp-I)); } for(i=0;i<=n;i++) { printf("%lld ",ans[i]); } printf("\n"); } fclose(stdin); fclose(stdout); return 0; } -
\(70pts\) ：设 \(f_{i,j,0/1}\) 表示前 \(i\) 个数选择了 \(j\) 个数进行异或且是偶数/奇数的最大收益，直接转移即可。
点击查看代码
__int128_t f[2][300010][2]; char s[300010]; int main() { freopen("confess.in","r",stdin); freopen("confess.out","w",stdout); ll t,n,cnt,i,j,k; __int128_t I=1ull<<63; I*=2; scanf("%lld",&t); for(k=1;k<=t;k++) { scanf("%s",s+1); n=strlen(s+1); memset(f,-0x3f,sizeof(f)); f[0][0][0]=I; for(i=1;i<=n;i++) { for(j=0;j<=i;j++) { f[i&1][j][0]=f[(i-1)&1][j][1]+((s[i]=='+')?1:-1); f[i&1][j][1]=f[(i-1)&1][j][0]+((s[i]=='+')?1:-1); if(j-1>=0) { f[i&1][j][0]=max(f[i&1][j][0],f[(i-1)&1][j-1][1]-1); f[i&1][j][1]=max(f[i&1][j][1],f[(i-1)&1][j-1][0]+1); } } } for(i=0;i<=n;i++) { printf("%lld ",(ll)(max(f[n&1][i][0],f[n&1][i][1])-I)); } printf("\n"); } fclose(stdin); fclose(stdout); return 0; } -
\(90pts\) ：考虑 Slope Trick 优化上述过程。
-
-
正解
- 因为有 \(2^{64}\) 的进、退位存在，故每次操作都会使数的奇偶性发生变化。
- 那么 \(\bigoplus\) 放在奇数个事件等价于 \(+1\) ，放在偶数个事件等价于 \(-1\) 。
- 统计 \(\bigoplus\) 用来可能和必须更改贡献的次数即可。
点击查看代码
char s[300010]; int main() { freopen("confess.in","r",stdin); freopen("confess.out","w",stdout); int t,n,sum,maybe,must,i,j,k; cin>>t; for(j=1;j<=t;j++) { cin>>(s+1); n=strlen(s+1); sum=maybe=must=0; for(i=1;i<=n;i++) { sum+=(s[i]=='+'?1:-1); maybe+=((i%2==0&&s[i]=='-')||(i%2==1&&s[i]=='+')); must+=(i%2==1&&s[i]=='-'); } for(i=0;i<=must;i++) { cout<<sum+i*2<<" "; } for(i=must+1;i<=must+maybe;i++) { cout<<sum+must*2<<" "; } for(i=must+maybe;i<=n;i++) { cout<<sum+must*2-(i-must-maybe)*2<<" "; } cout<<endl; } fclose(stdin); fclose(stdout); return 0; }
\(T2\) B. 秘密 \(0pts\)
-
最左/右边的人一定会往右/左走。
-
以 \(x\) 向右走为例，设 \(x\) 遇到的第一个人是 \(y\) ，在他们相遇后，让 \(y\) 接着往左走， \(x\) 接着往右走更新其他人。而更新的其他人往哪个方向走已经不重要了，因为完全可以被 \(x,y\) 所替代。
-
左右两种情况取 \(\min\) 即可。
点击查看代码
set<ll>s; set<ll>::iterator it; int main() { freopen("secret.in","r",stdin); freopen("secret.out","w",stdout); ll n,q,x,i; double ans; char pd; cin>>n>>q; for(i=1;i<=n;i++) { cin>>x; s.insert(x); } for(i=1;i<=q;i++) { cin>>pd>>x; if(pd=='+') { s.insert(x); } if(pd=='-') { s.erase(x); } if(pd=='?') { ans=0x7f7f7f7f; it=s.upper_bound(x); if(it!=s.end()) { ans=min(ans,max(*it-*s.begin(),*(--s.end())-x)/2.0); } it=s.find(x); if(it!=s.begin()) { it=prev(it); ans=min(ans,max(x-*s.begin(),*(--s.end())-*it)/2.0); } printf("%.2lf\n",ans); } } fclose(stdin); fclose(stdout); return 0; }
\(T3\) C. 潜力值 \(0pts\)
-
部分分
-
测试点 \(1,2\) ：模拟。
点击查看代码
const ll p=1000000007; ll b[510],id[510]; deque<ll>q; int main() { freopen("potential.in","r",stdin); freopen("potential.out","w",stdout); ll n,m,ans=0,i; cin>>n>>m; for(i=1;i<=n;i++) { cin>>b[i]; id[i]=i; } do { q.clear(); for(i=1;i<=m;i++) { q.push_back(0); } for(i=1;i<=n;i++) { if(q.front()<b[id[i]]) { q.pop_front(); q.push_back(b[id[i]]); } } for(i=0;i<q.size();i++) { ans=(ans+q[i])%p; } }while(next_permutation(id+1,id+1+n)); cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
-
-
正解
- 等有时间再来补，先咕了。
- 挂下 官方题解 。
\(T4\) D. 括号 \(5pts\)
-
部分分
- 测试点 \(6\) ：不存在子序列
()，故输出 \(0\) 即可。
- 测试点 \(6\) ：不存在子序列
-
正解
- 等有时间再来补，先咕了。
- 挂下 官方题解 。
总结
- \(T1\)
- 因为不想处理负数的异或，所以直接手动判断 \(+/-1\) ，然后就把符号写反了，导致 \(DP\) 没调出来。
- 观察样例和手摸后发现有一堆连续段，然后就不会做了。
- \(T2\) 处理传递完消息后的行动方向赛时因为基本没看题所以没去想，要是正儿八经地想或许能想出来。
- \(T3\) 文件粘成 \(T1\) 文件了，挂了 \(10pts\) 。
- \(T4\) 输出文件后缀名写的是输入文件后缀名了，挂了 \(5pts\) 。