2026-08-30~09-01 hetao1733837 的刷题记录
CF2255B A Ribbon for Tomorrow
原题链接：B. A Ribbon for Tomorrow
分析
需要从回文串的方向进行思考。要不直接把回文串删了吧……剩下的直接组合数做，然后加上1 11，表示原来的，就做完了？
为什么想到回文串呢？因为我们有一个反转操作，回文串的反转是没有卵用的。
感觉删掉回文的不好做（因为我没有模出来）。
先打一个O ( n 3 ) O(n^3)O(n3)的暴力吧……
你会发现，这个是一个01串，不加以利用实在可惜。
为啥我的暴力假了？
bur，一个非回文会出现相同的情况吗/xia
难道是好做的？
就是，我把1看成1 11，0看成− 1 -1−1，然后我们可以轻松地统计一些位置，然后做完了？
回文子串和前缀和没有任何关系！！！
又假了😭
切记，假了就是假了，不能有什么理由。
思考一下正解。
拿到一道题，先按照题目模拟一下，拿到分数再思考正解。保证有分再说。这个题理论上直接模拟不难吧，先别猜什么结论。先模拟再说。
呃，不过这个也没有什么意义。
考虑到，因为回文串没有用，所以要主动破坏回文性，所以，我们发现对于一个形如0110···011，反转实际上是把前面的0挪到后面，所以，问题变成了把0插入到若干位置。一个插板法做完了。然后1的答案直接和0的答案乘起来就行。
不是，操作 **任意次！！！**我又没有读对题😭
正解
#include<bits/stdc++.h>#defineintlonglong#definemod998244353usingnamespacestd;constintN=1000005;intt,n;string s;intfac[N];intqpow(inta,intb){intres=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}returnres;}intcalc(intn,intm){if(m>n||m<0||n<0)return1;returnfac[n]*qpow(fac[n-m],mod-2)%mod*qpow(fac[m],mod-2)%mod;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;fac[0]=1;for(inti=1;i<N;i++){fac[i]=fac[i-1]*i%mod;}for(intcs=1;cs<=t;cs++){cin>>n;cin>>s;intcnt0=0,cnt1=0;inttmp0=0,tmp1=0;for(inti=0;i<n;i++){if(i==0){if(s[0]=='0'){tmp0++;}if(s[0]=='1'){tmp1++;}}if(s[i]=='0'){cnt0++;}if(s[i]=='1'){cnt1++;}if(i>0){if(s[i]!=s[i-1]){if(s[i]=='0'){tmp0++;}if(s[i]=='1'){tmp1++;}}}}cout<<calc(cnt0-1,tmp0-1)*calc(cnt1-1,tmp1-1)%mod<<'\n';}}CF1174F Ehab and the Big Finale
原题链接：F. Ehab and the Big Finale
分析
bur，咋是这个？？？
正解
#include<bits/stdc++.h>usingnamespacestd;constintN=390005;intquery1(intu){intres;cout<<"d "<<u<<'\n';cout.flush();cin>>res;returnres;}intquery2(intv){intres;cout<<"s "<<v<<'\n';cout.flush();cin>>res;returnres;}voidanswer(intx){cout<<"! "<<x<<'\n';cout.flush();exit(0);}intn;vector<int>e[N];intD;intde[N],sz[N],son[N],fa[N];voiddfs(intu,intf,intdep){de[u]=dep;fa[u]=f;sz[u]=1;if(dep>=D)return;for(intv:e[u]){if(v==f)continue;dfs(v,u,dep+1);sz[u]+=sz[v];if(sz[v]>sz[son[u]])son[u]=v;}}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(inti=1,u,v;i<n;i++){cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}D=query1(1);if(D==0)answer(1);dfs(1,0,0);intrt=1;while(true){if(de[rt]==D)answer(rt);if(sz[rt]>=sz[son[rt]]*2){rt=query2(rt);continue;}inttmp=rt;while(sz[son[tmp]]*2>sz[tmp])tmp=son[tmp];intdis=query1(tmp);if(dis==0)answer(tmp);if(de[tmp]+dis==D){rt=query2(tmp);continue;}while(de[tmp]+dis!=D){tmp=fa[tmp];dis--;}rt=query2(tmp);}return0;}AT_abc473_g [ABC473G] Wipeout
原题链接：[ABC473G] Wipeout
分析
哦，这个困难就在于我既要钦定某个位置被记住，而且还要保证一些东西，就是没有被记住，或者怎么样吧……呃……啊吧啊吧……
对，这个特殊性质是好做的。直接拿下了42 p t s 42pts42pts的高分。
我将会在第二次学习完Stirling和Catlan之后写这个。
