20260413紫题训练

P2499 [SDOI2012] 象棋题意给出一个n×mn\times mn×m的盘面和kkk颗棋子的起点和终点位置要将kkk颗棋子都移动到目标位置移动规则形如象棋的马不过从1×21\times21×2变成了a×ba\times ba×b求移动的最小步数其中1≤n,m≤1001\le n,m\le 1001≤n,m≤1001≤k≤5001\le k\le 5001≤k≤500赛时思路 以及 题解由于有障碍的存在所以两点距离应该没有通用的形式所以不妨先把两点间距离预处理出来记为gi,j,i′,j′g_{i,j,i,j}gi,j,i′,j′​则原题转化为一个二分图最小权最大匹配问题套一个费用流即可代码#includebits/stdc.h # define Maxn 105 # define Maxk 505 # define pr pairint,int # define fir first # define sec second # define inf 2e91 using namespace std; int n,m,k,a,b; int x[Maxk],y[Maxk],sx[Maxk],sy[Maxk]; char A[Maxn][Maxn]; int d[Maxk][Maxn][Maxn]; queuepr Q; int fx[]{1,1,-1,-1},fy[]{1,-1,1,-1}; void BFS(int x,int y,int I) { for(int i1;in;i) for(int j1;jm;j) d[I][i][j]inf; d[I][x][y]0,Q.push({x,y}); while(!Q.empty()) { pr hQ.front();Q.pop(); for(int i0;i4;i) { int sxh.firfx[i]*a,syh.secfy[i]*b; if(sx1sxnsy1symA[sx][sy].d[I][sx][sy]inf) { d[I][sx][sy]d[I][h.fir][h.sec]1; Q.push({sx,sy}); } sxh.firfx[i]*b,syh.secfy[i]*a; if(sx1sxnsy1symA[sx][sy].d[I][sx][sy]inf) { d[I][sx][sy]d[I][h.fir][h.sec]1; Q.push({sx,sy}); } } } } int st,ed,head[Maxk1],tot2; struct Node{int to,next,w,cost;}e[(MaxkMaxkMaxk*Maxk)1]; void add(int u,int v,int w,int cost) {e[tot]{v,head[u],w,cost},head[u]tot;} void addedge(int u,int v,int w,int cost) {add(u,v,w,cost),add(v,u,0,-cost);} bool vis[Maxk1]; int dis[Maxk1],cur[Maxk1],ans; queueint q; bool spfa() { for(int i1;ied;i) vis[i]0,dis[i]inf,cur[i]head[i]; while(!q.empty()) q.pop(); dis[st]0,vis[st]1,q.push(st); while(!q.empty()) { int hq.front();q.pop(),vis[h]0; for(int ihead[h];i;ie[i].next) { if(e[i].wdis[e[i].to]dis[h]e[i].cost) { dis[e[i].to]dis[h]e[i].cost; if(!vis[e[i].to]) { vis[e[i].to]1; q.push(e[i].to); } } } }return dis[ed]!inf; } bool Vis[Maxk1]; int dfs(int rt,int flow) { if(rted) {ansdis[rt]*flow;return flow;}; Vis[rt]1; int res0; for(int icur[rt];i;ie[i].next) {cur[rt]i; if((!Vis[e[i].to])e[i].wdis[e[i].to]dis[rt]e[i].cost) { int nowflowdfs(e[i].to,min(flow,e[i].w)); if(!nowflow) dis[e[i].to]inf; else { e[i].w-nowflow; e[i^1].wnowflow; flow-nowflow; resnowflow; if(!flow) {Vis[rt]0;return res;} } } }Vis[rt]0;return res; } int main() { scanf(%d%d%d%d%d,n,m,k,a,b); for(int i1;in;i) for(int j1;jm;j) cinA[i][j]; for(int i1;ik;i) { scanf(%d%d,x[i],y[i]); BFS(x[i],y[i],i); } stk*21,edk*22; for(int i1;ik;i) { scanf(%d%d,sx[i],sy[i]); addedge(st,i,1,0),addedge(ki,ed,1,0); for(int j1;jk;j) if(d[j][sx[i]][sy[i]]!inf) addedge(j,ki,1,d[j][sx[i]][sy[i]]); } // for(int i1;in;i) { // for(int j1;jm;j) // printf(%d ,d[1][i][j]); // printf(\n); // } while(spfa()) dfs(st,inf); printf(%d\n,ans); return 0; }P3715 [BJOI2017] 魔法咒语题意给出nnn个基础串以及mmm个忌讳串求将基础串任意拼接为一个长为LLL的串且其不存在一个字串为忌讳串若两串拼接方式不同即视为不同即使它们外在形式一样其中数据范围分为两档1.n≤50,1.m≤50,1.L≤100\verb!1.n!\leq50,\verb!1.m!\leq50,\verb!1.L!\leq1001.n≤50,1.m≤50,1.L≤1002.n≤50,1.m≤50,1.L≤1e8\verb!2.n!\leq50,\verb!1.m!\leq50,\verb!1.L!\leq1e82.n≤50,1.m≤50,1.L≤1e8, 同时每个基础串长度不超过222对于所有数据而言串长总和不超过100100100题解如洛谷题解所说只要熟悉ACACAC自动机就是一道板题我们考虑把自动机建出来那么就可以在自动机形成的图上做DPDPDP令fi,jf_{i,j}fi,j​为长度为iii且当前停在自动机jjj位置上的方案数容易有filen,p←fi,jf_{ilen,p} \gets f_{i,j}filen,p​←fi,j​那么据此就有了O(L×len2)O(L\times len^2)O(L×len2)的DPDPDP足以通过第一档再考虑第二档发现有一个串长度≤2\leq2≤2的性质那么尝试套一个矩阵快速幂那么就有了O(len3×logL)O(len^3\times logL)O(len3×logL)的做法足以通过第二档总结遇到这种涉及多模式串匹配的计数都可以尝试往ACACAC自动机上套代码#includebits/stdc.h # define Maxn 55 # define Maxm 105 # define ll long long # define mod 1000000007 using namespace std; int n,m,L,len[Maxn]; string s[Maxn],t[Maxn]; namespace AC{ int trie[Maxm][30],fail[Maxm],num[Maxm],tot; void Insert(int x) { int lent[x].size(),rt0; for(int i0;ilen;i) { if(!trie[rt][t[x][i]-a]) trie[rt][t[x][i]-a]tot; rttrie[rt][t[x][i]-a]; } num[rt]; } queueint q; void GetFail() { for(int i0;i26;i) if(trie[0][i]) q.push(trie[0][i]); while(!q.empty()) { int hq.front();q.pop(); for(int i0;i26;i) { if(!trie[h][i]) trie[h][i]trie[fail[h]][i]; else { fail[trie[h][i]]trie[fail[h]][i]; num[trie[h][i]]num[fail[trie[h][i]]]; q.push(trie[h][i]); } } } } int Walk(int p,int I) { for(int i0;ilen[I];i) { ptrie[p][s[I][i]-a]; if(num[p]) return -1; } return p; } }; namespace Part1{ ll f[Maxm][Maxm],ans; void Solve() { f[0][0]1; for(int i0;iL;i) { for(int j0;jAC::tot;j) { for(int k1;kn;k) { if(ilen[k]L) { int pAC::Walk(j,k); if(p!-1) f[ilen[k]][p](f[ilen[k]][p]f[i][j])%mod; } } } } for(int i0;iAC::tot;i) ans(ansf[L][i])%mod; printf(%lld\n,ans); exit(0); } }; namespace Part2{ ll F[Maxm1]; ll A[Maxm1][Maxm1],G[Maxm1][Maxm1]; void KSM(int n) { while(n) { if(n1) { for(int i0;i0;i) { for(int j0;j(AC::tot*21);j) { for(int k0;k(AC::tot*21);k) G[i][j](G[i][j]F[k]*A[k][j])%mod; } } for(int i0;i0;i) { for(int j0;j(AC::tot*21);j) F[j]G[i][j],G[i][j]0; } } for(int i0;i(AC::tot*21);i) { for(int j0;j(AC::tot*21);j) { for(int k0;k(AC::tot*21);k) G[i][j](G[i][j]A[i][k]*A[k][j])%mod; } } for(int i0;i(AC::tot*21);i) { for(int j0;j(AC::tot*21);j) A[i][j]G[i][j],G[i][j]0; } n1; } } void Solve() { F[0]1; for(int i1;in;i) { if(len[i]1) { for(int j0;jAC::tot;j) { int pAC::Walk(j,i); if(p!-1) A[j][p]; } } else { for(int j0;jAC::tot;j) { int pAC::Walk(j,i); if(p!-1) A[jAC::tot1][p]; } } } // for(int i0;iAC::tot*21;i) { // for(int j0;jAC::tot*21;j) { // printf(%lld ,A[i][j]); // }printf(\n); // } for(int i0;iAC::tot;i) A[i][iAC::tot1]; KSM(L); ll ans0; for(int i0;iAC::tot;i) ans(ansF[i])%mod; printf(%lld\n,ans); exit(0); } }; int main() { scanf(%d%d%d,n,m,L); for(int i1;in;i) cins[i],len[i]s[i].size(); for(int i1;im;i) cint[i],AC::Insert(i); AC::GetFail(); if(L100) Part1::Solve(); else Part2::Solve(); return 0; }P4582 [FJOI2014] 树的重心题意有TTT组数据每次给出一个大小为nnn的树求有多少个联通字树的重心与原树一样注意若原树有两个点都能视作重心那么联通子树也应该有其中1≤T≤50,1≤n≤2001 \le T \le 50, 1 \le n \le 2001≤T≤50,1≤n≤200赛时思路 以及 题解先记原树重心为f1,f2f1,f2f1,f2(f1可能等于f2)(f1可能等于f2)(f1可能等于f2)f1!f2f1!f2f1!f2先考虑f1!f2f1!f2f1!f2的情况则f1,f2f1,f2f1,f2肯定各管辖了一个大小为n2\frac{n}{2}2n​的块而删点后联通块大小最大值恰恰取决于对方管辖的块的大小所以把联通子图看作是原图删边得到的对f1,f2f1,f2f1,f2所管辖的块分别做一次背包即可f1f2f1f2f1f2首先f1f1f1各子树大小必小于n12\frac{n1}{2}2n1​先分别对每个子树做一次DPDPDP记fv,if_{v,i}fv,i​为vvv子树删掉iii个的方案数现枚举全局删去xxx个则子树vvv至少删掉max(0,Szv−(n12−1))max(0,Sz_v-(\frac{n1}{2}-1))max(0,Szv​−(2n1​−1))直接背包时间复杂度似乎为O(n4)O(n^4)O(n4)不对由于总子树和为n−1n-1n−1所以时间复杂度为O(n3)O(n^3)O(n3)综上总时间复杂度O(qn3)O(qn^3)O(qn3)代码#includebits/stdc.h # define Maxn 205 # define mod 10007 using namespace std; int T,n,u,v; int head[Maxn],tot1; struct Node{int to,next;}e[Maxn1]; void add(int u,int v) {e[tot]{v,head[u]},head[u]tot;} int Mn2e91,sz[Maxn],nowMx[Maxn]; void FindRoot(int rt,int fa) { sz[rt]1; nowMx[rt]0; for(int ihead[rt];i;ie[i].next) { if(e[i].tofa) continue; FindRoot(e[i].to,rt),sz[rt]sz[e[i].to]; nowMx[rt]max(nowMx[rt],sz[e[i].to]); }nowMx[rt]max(nowMx[rt],n-sz[rt]); Mnmin(Mn,nowMx[rt]); } bool vis[Maxn]; int f1,f2; int f[Maxn][Maxn],g[Maxn],h[Maxn],ans; void DP(int rt,int fa) { sz[rt]1,f[rt][0]1; for(int ihead[rt];i;ie[i].next) { if(vis[e[i].to]||e[i].tofa) continue; DP(e[i].to,rt); for(int jsz[rt];j0;j--) { for(int ksz[e[i].to];k1;k--) f[rt][jk](f[rt][jk]f[rt][j]*f[e[i].to][k])%mod; } sz[rt]sz[e[i].to]; } f[rt][sz[rt]]1; } void clear() { for(int i1;in;i) { head[i]vis[i]0; for(int j0;jn;j) f[i][j]0; } tot1,f1f20,Mn2e91; } int main() { scanf(%d,T); for(int t1;tT;t) { scanf(%d,n); for(int i1;in;i) { scanf(%d%d,u,v); add(u,v),add(v,u); } FindRoot(1,0); for(int i1;in;i) { if(nowMx[i]Mn) { if(!f1) f1i; else f2i; vis[i]1; } } if(!f2) { DP(f1,0); for(int x0;xn;x) { g[0]1; int SZ0; for(int ihead[f1];i;ie[i].next) { int Valn-x; Val(Val1)/2-1; int Limmax(0,sz[e[i].to]-(Val)); for(int jSZ;j0;j--) { for(int ksz[e[i].to];kLim;k--) h[jk](h[jk]g[j]*f[e[i].to][k])%mod; } SZsz[e[i].to]; for(int j0;jSZ;j) g[j]h[j],h[j]0; // if(t2x2) { // printf(GGBond: ); // for(int j0;jSZ;j) printf(%d ,g[j]); // printf(\n); // } } ans(ansg[x])%mod; for(int i0;in;i) g[i]0; } } else { // printf(%d %d\n,f1,f2); DP(f1,0),DP(f2,0); for(int i0;in/2;i) ans(ansf[f1][i]*f[f2][i])%mod; } printf(Case %d: %d\n,t,ans),ans0; clear(); } return 0; }