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=-1;it=s.upper_bound(x);if(it!=s.end()){ans=max(*it-*s.begin(),*(--s.end())-x)/2.0;}it=s.find(x);if(it!=s.begin()){it=prev(it);if(ans==-1){ans=max(x-*s.begin(),*(--s.end())-*it)/2.0;}else{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\) 。
