AC:61001:题面等价判断一种颜色是否会将11-n,m)分割将所有点和颜色收集从1往上判断如果该颜色不会分割则输出该颜色分割的判断如果从某个点出发按照八连通遍历搜索相同颜色的格子能够同时到达右上/左下则视为可分割同时若到达起点/终点也视为可分割一些代码技巧1.vis里面的变量定义为vid,每种颜色搜索更新避免频繁初始化2.标记搜寻过的点如果新点入队发现以及搜索过之间跳过code:#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 N2e310,mod1e97,M1e610;int lowbit(int x){return x(-x);}struct Node{int val,x,y;};struct Point{int x,y;};int g[N][N];int vis[N][N];int vid0;int n,m;vectorNodevec;int dx[]{-1,-1,0,1,1,1,0,-1};int dy[]{0,-1,-1,-1,0,1,1,1};bool cmp(Node a,Node b){return a.valb.val;}bool f1(int x,int y) {if (x1y1) return 1;if (ymxn) return 1;return 0;}bool f2(int x,int y) {if (y1x1) return 1;if (xnym) return 1;return 0;}bool f(int col,int l,int r){if(g[1][1]col||g[n][m]col)return 1;vid;fr(i,l,r-1){int Xvec[i].x;int Yvec[i].y;if(vis[X][Y]vid)continue;bool F10;bool F20;queuePointq;vis[X][Y]vid;q.push({X,Y});while(!q.empty()){Point totq.front();q.pop();if(f1(tot.x,tot.y))F11;if(f2(tot.x,tot.y))F21;if(F1F2)return 1;fr(k,0,7){int nxtot.xdx[k];int nytot.ydy[k];if(nx1nxnny1nymvis[nx][ny]!vidg[nx][ny]col){vis[nx][ny]vid;q.push({nx,ny});}}}}return 0;}void solve(){cinnm;vec.clear();fr(i,1,n){fr(j,1,m){cing[i][j];vec.pb({g[i][j],i,j});}}sort(all(vec),cmp);int cur0;for(int col0;;col){while(curvec.size()vec[cur].valcol)cur;int Lcur;while(curvec.size()vec[cur].valcol)cur;int Rcur;if(LR){coutcol\n;return;}if(!f(col,L,R)){coutcol\n;return;}}}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}1004经典博弈论状态dp;1.题目条件等价 在进行操作时能够删除这个数此时的抑或和最高位在该数上为12.所以我们考虑预处理出对于每一个位哪些数在该位上为13.根据博弈论在该次操作中后继状态只要存在必败态则当前状态则是必胜态4.dp[0]为必败态5.从0开始逐渐更新状态更新当前状态的抑或和如果抑或和为0则该状态是必败态否则将当前状态与上预处理出来的最高位数的位存在状态得到可能的后继状态遍历所有后继状态如果存在必败态则当前为必胜态否则为必败态代码技巧1.__builtin_ctz为该数二进制状态下末尾有几个0可以用于寻找最低位2.__builtin_clz为该数二进制状态下有几个前导0可以用于寻找最高位code:#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,mod1e97,M32;int lowbit(int x){return x(-x);}int Bit[M];void solve(){int n;cinn;vectorinta(n1);fr(i,0,n-1){cina[i];}fr(i,0,31){Bit[i]0;fr(j,0,n-1){if((a[j]i)1){Bit[i]|(1j);}}}vectorintdp((1n)5,-1);dp[0]0;vectorintXor((1n)5,0);fr(i,1,(1n)-1){int Low__builtin_ctz(i);Xor[i]Xor[i^(1Low)]^a[Low];if(Xor[i]0){dp[i]0;}else{int High__builtin_clz(Xor[i]);int hpos31-High;int MaskiBit[hpos];int f0;fr(j,0,31){if((Maskj)1){if(dp[i^(1j)]0){f1;break;}}}dp[i]f;}}//coutdp[(1n)-1];cout(dp[(1n)-1]?Left:Right)\n;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}1005离散化所有数据令c[i]表示第i个数往后放第一个火车的最小值每次新增一次火车就对它之前所有的状态取min令f[i][j]表示第i个数后放第2^j个火车的最短距离打ST表优化求解code:#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 N1e510,mod1e97,M22;int lowbit(int x){return x(-x);}Pii a[N];int L[N],R[N],C[N1];int f[N][M];int siz,n;void add(int l,int r){while(l){C[l]min(C[l],r);l-lowbit(l);}}int que(int idx){int ressiz1;while(idxsiz){resmin(res,C[idx]);idxlowbit(idx);}return res;}void solve(){cinn;siz0;memset(C,0x3f3f3f3f,sizeof(C));memset(f,0,sizeof(f));vectorintvec;fr(i,1,n){cina[i].x0a[i].y0;vec.pb(a[i].x0);vec.pb(a[i].y0);}int m;cinm;fr(i,1,m){cinL[i]R[i];vec.pb(L[i]);vec.pb(R[i]);}sort(all(vec));vec.erase(unique(all(vec)),vec.end());fr(i,1,n){a[i].x0lower_bound(all(vec),a[i].x0)-vec.begin()1;a[i].y0lower_bound(all(vec),a[i].y0)-vec.begin()1;}fr(i,1,m){L[i]lower_bound(all(vec),L[i])-vec.begin()1;R[i]lower_bound(all(vec),R[i])-vec.begin()1;}sizvec.size();fr(i,1,n)add(a[i].x0,a[i].y0);fr(i,1,siz)f[i][0]que(i);f[siz1][0]siz1;fr(j,1,M-1){fr(i,1,siz1){f[i][j]f[f[i][j-1]][j-1];}}fr(i,1,m){int idxL[i];int cnt0;for(int jM-1;j0;j--){if(f[idx][j]R[i]){idxf[idx][j];cnt(1LLj);}}coutcnt\n;}}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}1007签到#include bits/stdc.husing namespace std;using LL long long;#define endl \nLL mod998244353;LL ksm(LL a,LL n){LL res1;while(n){if(n1)resres*a;aa*a;n/2;}return res;}void solve(){LL n,s;cinns;vectorLLa(n1);int f0,f10;for(int i1;in;i){cina[i];if(a[i]s)f1;if(a[i]!sa[i]!0)f11;}if(f1||!f)coutNOendl;else coutYESendl;}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);LL T1;cinT;while(T--){solve();}}1008暴力枚举每一个数判断是否成立即可虽然数据量很大但很快都会break完全跑不满code:#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 pairstring,intPsi;typedef pairint,intPii;typedef pairstring,stringPss;const int N1e410,mod1e97,M5;int lowbit(int x){return x(-x);}int W[N][M];void P(){fr(i,0,1e4){W[i][4]i%10;W[i][3](i/10)%10;W[i][2](i/100)%10;W[i][1](i/1000)%10;}}void Co(int x){string ansto_string(x);while(ans.size()4){ans0ans;}cans;}void solve(){int n;cinn;vectorPsia(n1);fr(i,1,n){cina[i].x0a[i].y0;a[i].x0 a[i].x0;}fr(i,0,1e4){bool f1;fr(j,1,n){int cnt0;string sa[j].x0;int numa[j].y0;int n1s[1]-0;int n2s[2]-0;int n3s[3]-0;int n4s[4]-0;if(W[i][1]n1)cnt;if(W[i][2]n2)cnt;if(W[i][3]n3)cnt;if(W[i][4]n4)cnt;if(cnt!num){f0;break;}}if(f){//couti\n;Co(i);return;}}}signed main(){GG;int _t1;cin_t;P();while(_t--){solve();}}1010签到#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,mod1e97,M1e610;int lowbit(int x){return x(-x);}void solve(){int n,m;cinnm;int now0;bool f1;fr(i,1,n){vectorinta;fr(j,1,m){int x;cinx;a.pb(x);}sort(all(a));auto itupper_bound(all(a),now);if(ita.end()){f0;}else{now*it;}}cout(f?YES:NO)\n;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}