工艺品商城网站建设,织梦网站默认密码,上海响应式网站建设企业,游戏策划要学什么20260312紫题训练 A - 棋盘覆盖 TYPE ADP 或 网络流? 1.黑白染色 2.答案等价于最大匹配TYPE B考虑构造#xff0c;答案上界为nm/33 发现:34易填 填完后剩包含特殊点的三行 发现23易填 填完后剩包含特殊点的三行两列 于是证得上界可取TYPE C考虑插头DP 插头情况复杂#xff0…20260312紫题训练A - 棋盘覆盖TYPE ADP 或 网络流?1.黑白染色2.答案等价于最大匹配TYPE B考虑构造答案上界为nm/33发现:34易填填完后剩包含特殊点的三行发现23易填填完后剩包含特殊点的三行两列于是证得上界可取TYPE C考虑插头DP插头情况复杂考虑状压DP发现状态数过多似乎无法优化重新考虑插头DP好像也没有那么复杂开始写代码#includebits/stdc.h # define Maxn 105 # define ll long long using namespace std; bool bz[Maxn][Maxn]; int n,m,k,x,y,sum; string N,M; char type; int v[]{0,0,1,-1},s[]{1,-1,0,0}; struct TYPE_A{ bool vis[Maxn*Maxn]; int pos[Maxn][Maxn],p[Maxn*Maxn],ans; int head[Maxn*Maxn],tot1; struct Node{int to,next;}e[Maxn*Maxn*4]; void add(int u,int v) {e[tot]{v,head[u]},head[u]tot;} bool dfs(int rt) { for(int ihead[rt];i;ie[i].next) { if(!vis[e[i].to]) {vis[e[i].to]1; if((!p[e[i].to])||dfs(p[e[i].to])) {p[e[i].to]rt;return 1;} } }return 0; } void SolveA() { for(int i1;in;i) for(int j1;jm;j) pos[i][j](i-1)*mj; for(int i1;in;i) { for(int j1;jm;j) { for(int k0;k4;k) { int xiv[k],yjs[k]; if((ij)%20bz[i][j]!1) { if(x1xny1ymbz[x][y]!1) add(pos[i][j],pos[x][y]); } } } } for(int i1;in;i) { for(int j1;jm;j) { if((ij)%20bz[i][j]!1) { memset(vis,0,sizeof(vis)); ansdfs(pos[i][j]); } } }printf(%d\n,ans); } }A; struct TYPE_B{ ll mod998244353,G13,G2332748118; ll ksm(ll a,ll b) { ll res1; while(b) { if(b1) resres*a%mod; aa*a%mod; b1; }return res; } int limit1,l,r[2000053]; ll f[2000053],g[2000053],ans[2000053]; void NTT(ll *a,ll type) { for(int i0;ilimit;i) if(ir[i]) swap(a[i],a[r[i]]); for(int len1;lenlimit;len1) { ll Wnksm(type1?G1:G2,(mod-1)/(len1)); for(int l0;llimit;l(len1)) {ll w1; for(int il;illen;i,ww*Wn%mod) { ll Aa[i],Bw*a[ilen]%mod; a[i](AB)%mod,a[ilen](A-Bmod)%mod; } } } } void SolveB() { nN.size()-1; for(int i0;in;i) f[n-i]N[i]-0; mM.size()-1; for(int i0;im;i) g[m-i]M[i]-0; while(limitnm) limit1,l; for(int i0;ilimit;i) r[i](r[i1]1)|((i1)(l-1)); NTT(f,1),NTT(g,1); for(int i0;ilimit;i) f[i]f[i]*g[i]%mod; NTT(f,-1); int v0; for(int i0;ilimit;i) { f[i]f[i]*ksm(limit,mod-2)%mod; f[i]v; vf[i]/10,f[i]%10; } // for(int ilimit-1;i0;i--) printf(%lld,f[i]);printf(\n); f[0]--; v0; for(int ilimit-1;i0;i--) { int Vvf[i]; ans[i]V/3; vV%3*10; } int lenlimit-1; while(len(!ans[len])) len--; for(int ilen;i0;i--) printf(%lld,ans[i]);printf(\n); } }B; # define pr pairint,int # define fir first # define sec second struct TYPE_C{ int f[2][1500005],cur; int cnt[2]; unordered_mapint,int Hash[2]; vectorint State[2]; vectorpr e[2][1500005]; int Bit(int s,int x) {return ((s(2*x))3);} int Set(int s,int x,int v) {return s(-Bit(s,x)v)*(1(2*x));} void Insert(int x) { if(Hash[cur^1].count(x)0) Hash[cur^1][x]cnt[cur^1],State[cur^1].push_back(x); } void clear() { for(int s:State[cur]) { e[cur][Hash[cur][s]].clear(); f[cur][Hash[cur][s]]0; } State[cur].clear(),Hash[cur].clear(),cnt[cur]0; } void FindState(int i,int j,int s) { int x(jm)?i1:i,y(jm)?1:j1; if(jm) { if(Bit(s,m)) return ; if(bz[x][y]) { if(Bit(s,0)) return ; int STSet(Set(s2,0,0),1,0); e[cur][Hash[cur][s]].push_back({ST,0}),Insert(ST); return ; } if(Bit(s,0)) { if(Bit(s,0)1) { int STSet(Set(s2,0,2),1,0); e[cur][Hash[cur][s]].push_back({ST,0}),Insert(ST); int ST1Set(Set(s2,0,0),1,2); e[cur][Hash[cur][s]].push_back({ST1,0}),Insert(ST1); } if(Bit(s,0)2) { int STSet(Set(s2,0,0),1,0); e[cur][Hash[cur][s]].push_back({ST,1}),Insert(ST); } } else { int STSet(Set(s2,0,0),1,0); e[cur][Hash[cur][s]].push_back({ST,0}),Insert(ST); int ST1Set(Set(s2,0,1),1,1); e[cur][Hash[cur][s]].push_back({ST1,0}),Insert(ST1); int ST2Set(Set(s2,0,0),1,1); e[cur][Hash[cur][s]].push_back({ST2,0}),Insert(ST2); int ST3Set(Set(s2,0,1),1,0); e[cur][Hash[cur][s]].push_back({ST3,0}),Insert(ST3); } } else { int bz1Bit(s,j),bz2Bit(s,j1); if(bz[x][y]) { if(bz1||bz2) return ; int STSet(Set(s,j,0),j1,0); e[cur][Hash[cur][s]].push_back({ST,0}),Insert(ST); return ; } if((!bz1)(!bz2)) { int STSet(Set(s,j,0),j1,0); e[cur][Hash[cur][s]].push_back({ST,0}),Insert(ST); int ST1Set(Set(s,j,1),j1,1); e[cur][Hash[cur][s]].push_back({ST1,0}),Insert(ST1); int ST2Set(Set(s,j,0),j1,1); e[cur][Hash[cur][s]].push_back({ST2,0}),Insert(ST2); int ST3Set(Set(s,j,1),j1,0); e[cur][Hash[cur][s]].push_back({ST3,0}),Insert(ST3); } else { if(bz11bz21) { if(Bit(s,j-1)) return ; int STSet(Set(s,j,0),j1,0); e[cur][Hash[cur][s]].push_back({ST,1}),Insert(ST); } else if(bz1bz2) return ; if(bz11) { if(Bit(s,j-1)1) { int STSet(Set(Set(s,j,0),j1,0),j-1,2); e[cur][Hash[cur][s]].push_back({ST,0}),Insert(ST); } else { int STSet(Set(s,j,2),j1,0); e[cur][Hash[cur][s]].push_back({ST,0}),Insert(ST); int ST1Set(Set(s,j,0),j1,2); e[cur][Hash[cur][s]].push_back({ST1,0}),Insert(ST1); } } if(bz12) { int STSet(Set(s,j,0),j1,0); e[cur][Hash[cur][s]].push_back({ST,1}),Insert(ST); } if(bz21) { int STSet(Set(s,j,2),j1,0); e[cur][Hash[cur][s]].push_back({ST,0}),Insert(ST); int ST1Set(Set(s,j,0),j1,2); e[cur][Hash[cur][s]].push_back({ST1,0}),Insert(ST1); } if(bz22) { int STSet(Set(s,j,0),j1,0); e[cur][Hash[cur][s]].push_back({ST,1}),Insert(ST); } } } } void SolveC() { if(n11m11k22) {printf(33\n);return ;} if(bz[1][1]) Insert(0); else Insert(5),Insert(1),Insert(4),Insert(0); cur1; for(int i1;in;i) { for(int j1;jm;j) { if(injm) continue; for(int s:State[cur]) { FindState(i,j,s); for(pr it:e[cur][Hash[cur][s]]) f[cur^1][Hash[cur^1][it.fir]]max(f[cur^1][Hash[cur^1][it.fir]],f[cur][Hash[cur][s]]it.sec); }clear(),cur^1; } } int ans0; ansf[cur][Hash[cur][0]]; printf(%d\n,ans); } }C; int main() { cinNMktype; if(typeA) { for(int i0;iN.size();i) nn*10(N[i]-0); for(int i0;iM.size();i) mm*10(M[i]-0); swap(n,m); for(int i1;ik;i) scanf(%d%d,x,y),bz[x][y]1; A.SolveA(); return 0; } if(typeB) { B.SolveB(); return 0; } if(typeC) { for(int i0;iN.size();i) nn*10(N[i]-0); for(int i0;iM.size();i) mm*10(M[i]-0); swap(n,m); for(int i1;ik;i) scanf(%d%d,x,y),bz[x][y]1; C.SolveC(); return 0; } return 0; }B - 密室之门容易列出一个同余方程组然后就能联想到中国剩余定理但后面由于数据范围就不好做了发现题目只需要判有没有解于是两两判断有没有解即可#includebits/stdc.h # define Maxn 5005 # define ll long long int T,n; ll a[Maxn],b[Maxn]; ll Gcd(ll x,ll y) { if(!y) return x; return Gcd(y,x%y); } int main() { scanf(%d,T); while(T--) { bool bz0; scanf(%d,n); for(int i1;in;i) scanf(%d%d,a[i],b[i]),b[i]a[i]-b[i]; for(int i1;in;i) { for(int ji1;jn;j) { ll gcdGcd(a[i],a[j]); if(abs(b[i]-b[j])%gcd) {bz1;break;} }if(bz) break; } bz?printf(impossible\n):printf(possible\n); bz0; } return 0; }C - 飞镖恶心分讨#includebits/stdc.h # define ll long long # define int __int128 using namespace std; int T; int A1,B1,C1,D1,K,ans; int A2,B2,C2,D2,M; int A3,B3,C3,D3,X; bool Check(int x) { if(x6ll*K) return 0; if(x0) return 0; if(x4ll*K) return 1; if(x5ll*K) if(x!(5ll*K-1)) return 1; return x%30; } bool Check1(int x) { if(x0) return 0; if(xK) return 1; if(x2ll*K) { if((x%20)||(x%30)) return 1; } if(x3ll*K) return (x%30); return 0; } bool Check2(int x) { if(x2) return 0; if(x%20x/2K) return 1; return 0; } bool Check3(int x) { if(x2) return 0; if(x5ll*Kx!5ll*K-1) return 1; return 0; } void Do() { K(A1*K*KB1*KC1)%D120; M(A2*M*MB2*MC2)%D220; X(A3*X*XB3*XC3)%D320; } // Fast I/O (关键优化) char buf[1 23], *p1 buf, *p2 buf; #define getchar() (p1 p2 (p2 (p1 buf) fread(buf, 1, 1 23, stdin), p1 p2) ? EOF : *p1) template typename T inline void read(T x) { x 0; char c getchar(); while (c 0 || c 9) c getchar(); while (c 0 c 9) x x * 10 (c - 0), c getchar(); } char obuf[1 23], *O obuf; template typename T inline void print(T x) { if (x 9) print(x / 10); *O x % 10 0; } // signed main() { read(T); read(A1),read(B1),read(C1),read(D1),read(K); read(A2),read(B2),read(C2),read(D2),read(M); read(A3),read(B3),read(C3),read(D3),read(X); while(T--) { // printf(%lld %lld %lld\n,K,M,X); if(X6ll*K) {ans,Do();continue;} int Sum6ll*K2ll*K; if(XSumX!Sum-1) { // printf(1\n); ans,Do();continue; } Sum3ll*K4ll*K; if(XSumX!Sum-1) { // printf(1\n); ans,Do();continue; } if(Check(X-2ll*M)) { // printf(2\n); ans,Do();continue; } if(Check1(X-2ll*M-M)||Check1(X-2ll*M-2ll*M)) { // printf(3\n); ans,Do();continue; } if(X%M0X/M2X/M6) { // printf(4\n); ans,Do();continue; } if(Check3(X-M)||Check3(X-2ll*M)) { // printf(5\n); ans,Do();continue; } if(Check2(X-M)||Check2(X-2ll*M)||Check2(X-3ll*M)||Check2(X-4ll*M)) { // printf(6\n); ans,Do();continue; } Do(); }print(ans); fwrite(obuf, 1, O - obuf, stdout); return 0; }总结AAA可以说是满意的整体思路没有错一步步轻松正解BBB两两判断套路题CCC分讨第一眼的推性质没错但后续的分讨没有注意到“红心”这一特殊的东西观察力还待加强