赛时没看到F的时限给了10s扩展kmp后打完二进制状态压缩的拓扑解后感觉时间复杂度暴了想了半天点分治。。。最后赛时5k,AJ待补有时间更新好多题要补呀划掉D:图论签到题 基础bfs变种分别维护奇偶最小值判断时注意k为偶数而维护值为奇数无解#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N5e510,mod1e97,M1e610;int lowbit(int x){return x(-x);}vectorintg[N];int dis[N][2];//01int n,m,k;int Get(int d,int op){if(dinf)return inf;if(k%20){if(op1)return inf;int x(dk-1)/k;return x*k;}else{int x(dk-1)/k;if((x1)!op)x;return x*k;}}void init(int n){fr(i,1,n){g[i].clear();dis[i][0]dis[i][1]inf;}}void solve(){cinnmk;init(n);fr(i,1,m){int u,v;cinuv;g[u].pb(v);g[v].pb(u);}queuePiiq;dis[1][0]0;q.push({1,0});while(!q.empty()){auto [u,op]q.front();q.pop();for(auto v:g[u]){if(dis[v][op^1]dis[u][op]1){dis[v][op^1]dis[u][op]1;q.push({v,op^1});}}}for(int i1;in;i){int ansmin(Get(dis[i][0],0),Get(dis[i][1],1));if(ansinf/2)cout-1 ;else coutans ;}cout\n;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}F题目翻译一下就是给出若干字母在特定字母表排序方法下的大小对应关系这个关系通过每个后缀和前缀相同的第一个字母给出扩展kmp(Z函数寻找每个后缀与前缀的最长公共长度然后根据这个关系拓扑即可#includebits/stdc.h#define int long longusing u32uint32_t;using u64uint64_t;#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N2e410,mod1LL32,M1e610;int lowbit(int x){return x(-x);}u32 msk[26];u32 ot[26];u32 eg[26];u32 C[30][30];void init(){C[0][0]1;fr(i,1,26){C[i][0]1;fr(j,1,i)C[i][j](C[i-1][j]C[i-1][j-1]);}}u32 dfs(u32 Mask){if(Mask0)return 1;vectoru32v;u32 rMask;while(r){u32 qlowbit(r);u32 now0;while(q){u32 plowbit(q);q^p;if(nowp)continue;now|p;int id__builtin_ctz(p);q|(eg[id]Mask(~now));}r~now;v.pb(now);}if(v.size()1){u32 ans1;int sum0;for(auto x:v){int siz__builtin_popcount(x);ans(u32)((u64)ans*dfs(x));ans(u32)((u64)ans*C[sumsiz][siz]);sumsiz;}return ans;}int cnt0,pos-1;u32 tmpMask;while(tmp){u32 plowbit(tmp);tmp^p;int id__builtin_ctz(p);if((msk[id]Mask)0){cnt;posid;}}if(cnt0)return 0;if(cnt1){return dfs(Mask^(1upos));}int id[26];vectorintnode;memset(id,-1,sizeof(id));tmpMask;while(tmp){u32 plowbit(tmp);tmp^p;int x__builtin_ctz(p);id[x]node.size();node.pb(x);}int siznode.size();vectorintdp(1siz,0);dp[0]1;vectoru32pre(siz,0);for(int i0;isiz;i){int xnode[i];u32 pmsk[x]Mask;while(p){u32 blowbit(p);p^b;int y__builtin_ctz(b);pre[i]|(1uid[y]);}}u32 Max(1usiz)-1;for(u32 mk0;mkMax;mk){if(dp[mk]0)continue;u32 restMax^mk;while(rest){u32 plowbit(rest);rest^p;int x__builtin_ctz(p);if((pre[x]mk)pre[x]){dp[mk|p]dp[mk];}}}return dp[Max];}void solve(){string s;cins;int ns.size();vectorintz(n);int l0,r0;fr(i,1,n-1){if(ir)z[i]min(r-i1,z[i-l]);while(iz[i]ns[z[i]]s[iz[i]])z[i];if(iz[i]-1r)li,riz[i]-1;}//vectorintmsk(26,0);fr(i,1,n-1){if(z[i]n-i){cout0\n;return;}//msk[s[z[i]]-a]|1(s[iz[i]]-a);msk[s[iz[i]]-a]|1(s[z[i]]-a);ot[s[z[i]]-a]|1(s[iz[i]]-a);}fr(i,0,25){eg[i]msk[i]|ot[i];}int ans0;vectorintdp(126,0);dp[0]1;/*for (int i0;i(126);i) {for (int j0;j26;j) {if (!(ij1)((msk[j]i)msk[j])) {dp[i^(1j)]dp[i];dp[i^(1j)]%mod;}}}coutdp.back()\n;*/for(int i0;i(126);i){for(int ji;j;j-lowbit(j)){int k__builtin_ctz(j);if((msk[k]i)msk[k]){dp[i]dp[i^(1k)];dp[i]%mod;}}}coutdp.back()\n;// coutdfs((1u26)-1)\n;}signed main(){GG;int _t1;init();//cin_t;while(_t--){solve();}}os:代码能看出作者的心路历程。。G蛮好玩的图论博弈题一个点必胜的条件是 它的边上存在sp点 或 存在一条通向必胜的边一条必胜边的条件是 u-v v在除去这条边后还存在2的 相邻sp点 或 必胜边定义一个dfs过程为 对于一个点u遍历与它相邻的所有点假设从该点走向u,判断这条边是否为必胜边是则标记并将该边加入搜索队列读入并编号所有边先对相邻sp点增加cnt,接着尝试搜索所有点得到部分必胜边再用必胜边更新cnt由度数不大于3可知该方法正确#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N2e510,mod1e97,M4e510;int lowbit(int x){return x(-x);}int fr[M],to[M],re[M],cnt[N];bool st[M],sp[N];vectorPiig[N];queueintq,qe;int n,m,k;void dfs(int u){if(sp[u])return;for(auto [v,id]:g[u]){if(st[re[id]])continue;int fsp[v]|st[id];if(cnt[u]-f2){st[re[id]]1;q.push(re[id]);}}}void init(int n,int m){fr(i,1,n){g[i].clear();sp[i]0;cnt[i]0;}fr(i,1,m1){fr[i]0;to[i]0;re[i]0;st[i]0;}qqe;}void solve(){cinnmk;init(n,m);int tot0;fr(i,1,m){int u,v;cinuv;int id1tot;int id2tot;g[u].pb({v,id1});g[v].pb({u,id2});fr[id1]u;to[id1]v;fr[id2]v;to[id2]u;re[id1]id2;re[id2]id1;}fr(i,1,k){int x;cinx;sp[x]1;/*for(Pii p:g[x]){int vp.x0;cnt[v];}*/}fr(i,1,n){for(auto [v,id]:g[i]){if(sp[v])cnt[i];}}fr(i,1,n){if(!sp[i])dfs(i);}while(!q.empty()){int idq.front();q.pop();int ufr[id];int vto[id];cnt[u];dfs(u);}vectorintans;fr(i,1,n){if(sp[i])continue;bool f0;for(auto [v,id]:g[i]){if(sp[v]||st[id]){f1;break;}}if(f)ans.pb(i);}coutans.size()\n;for(int x:ans)coutx ;cout\n;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}H签到打个表即可#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N2e510,mod1e97,M1e610;int lowbit(int x){return x(-x);}/*bool Prm(int x){if(x1)return 0;for(int i2;i*ix;i){if(x%i0)return 0;}return 1;}bool ok(const vectorinta,int n){fr(i,0,n-1){if(Prm(abs(a[i]-a[i%n1])))return 0;}return 1;}*/bool st[N];int prime[N],cnt;void init(){st[0]st[1]1;for(int i2;iN;i){if(!st[i])prime[cnt]i;for(int j1;jcnti*prime[j]N;j){st[i*prime[j]]1;if(i%prime[j]0)break;}}}void solve(){/*vectorinta;for(int i1;i10;i){a.pb(i);do {if(ok(a,a.size())){for(auto x:a)coutx ;cout\n;}} while (next_permutation(a.begin(), a.end()));}*/int n;cinn;if(n3||n4||n6){cout-1\n;return;}if(st[n-1]){fr(i,1,n)couti ;cout\n;return;}if(n8){cout1 2 3 4 8 7 6 5\n;return;}fr(i,1,n-4){couti ;}coutn n-1 n-2 n-3\n;}signed main(){GG;init();int _t1;cin_t;while(_t--){solve();}}I数位dp,一个小check是加法的数位dp存在从低位到高位的情况毕竟要向高位进位嘛维护一个Mask,记录当前位的 i 是否存在进位 已经当前的 n-(id) 是否存在退位它的意义是保证状态合法最终的合法状态为0 0 即不存在进位/退位我们假定fiA,fidB,在当前位i为x(0|1),id为y(0|1)(Ax)*(By)ABA*yB*xx*y维护 每一种状态的 i的1总数 id的1总数 状态数 i的1个数)*(id的1个数状态数的意义是 每个可能会产生1贡献时总贡献为1*状态数#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N2e410,mod998244353,M1e610;int lowbit(int x){return x(-x);}struct Node{int cnt,sx,sy,sxy;};void solve(){int n,d;cinnd;Node dp[4],ndp[4];memset(dp,0,sizeof(dp));dp[0].cnt1;fr(i,0,60){memset(ndp,0,sizeof(ndp));int bitn(ni)1;int bitd(di)1;fr(j,0,3){int upj1;int dow(j1)1;Node curdp[j];if(cur.cnt0)continue;int D0,U(i60);fr(x,D,U){int y(xbitdup)1;int nxty(xbitdup)1;int nxtn((bitn-x-dow)0);int Nxt(nxtn1)|nxty;Node nxtndp[Nxt];nxt.cnt(nxt.cntcur.cntmod)%mod;nxt.sx(nxt.sxcur.sxmod)%mod;if(x)nxt.sx(nxt.sxcur.cntmod)%mod;nxt.sy(nxt.sycur.symod)%mod;if(y)nxt.sy(nxt.sycur.cntmod)%mod;nxt.sxy(nxt.sxycur.sxymod)%mod;if(x)nxt.sxy(nxt.sxycur.symod)%mod;if(y)nxt.sxy(nxt.sxycur.sxmod)%mod;if(xy)nxt.sxy(nxt.sxycur.cntmod)%mod;}}//dpndp;swap(dp,ndp);}//coutdp[0].cnt\n;coutdp[0].sxy\n;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}