20250808测试 · ooliver

S+20250808测试 A. 沙漠化暴力BFS即可。 #include using namespace std; int n,m,t,ans; int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; string a[15]; struct node{ int x,y,id; }; queue q; int main(){ cin>>n; for(int i=1;i>a[i]; m=a[1].size(); for(int i=1;i>t; if(!ans){ cout=n*m){ coutn||ny=m) continue; if(a[nx][ny]=='F'){ a[nx][ny]='D'; ans++,q.push({nx,ny,id+1}); } } } cout `#include using namespace std; int n,m,t,ans; int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; string a[15]; struct node{ int x,y,id; }; queue q; int main(){ cin>>n; for(int i=1;i>a[i]; m=a[1].size(); for(int i=1;ifor(int j=0;j if(a[i][j]=='D') ans++,q.push({i,j,0}); cin>>t; if(!ans){ cout0; return 0; } if(t>=n*m){ cout return 0; } while(q.size()){ node now=q.front(); q.pop(); int x=now.x,y=now.y,id=now.id; if(id==t) continue; for(int i=0;i4;i++){ int nx=x+dx[i],ny=y+dy[i]; if(nx1||nx>n||ny0||ny>=m) continue; if(a[nx][ny]=='F'){ a[nx][ny]='D'; ans++,q.push({nx,ny,id+1}); } } } cout return 0; }` C++ B. 筒装球相当于模拟一个包含分别为数字与数字个数两个元素的栈。 #include using namespace std; int n,x,ans; struct node{ int a,sum; }; stack s; int main(){ cin>>n; s.push({0,0}); while(n--){ cin>>x; node now=s.top(); if(now.a==x){ s.pop(); ans-=now.sum; if(now.sum+1!=x) s.push({x,now.sum+1}),ans+=now.sum+1; } else{ s.push({x,1}); ans++; } cout `#include using namespace std; int n,x,ans; struct node{ int a,sum; }; stack s; int main(){ cin>>n; s.push({0,0}); while(n--){ cin>>x; node now=s.top(); if(now.a==x){ s.pop(); ans-=now.sum; if(now.sum+1!=x) s.push({x,now.sum+1}),ans+=now.sum+1; } else{ s.push({x,1}); ans++; } cout } return 0; }` C++ C. 双循环锦标赛暴力DFS，在结尾判断序列是否合法。判断方式：用四个变量 a,b,c,d 分别表示胜场为 n(n-1)，n(n-1)-1，1，0 的数量，若 a>1 或 d>1，显然不对，因为全输和全胜只能存在一个。若 a=1 且 b=1 显然也是不正确的，因为这是双循环赛制，如果有人全胜，不可能存在只输一场的人，对于全败也同理。最后在循环的时候还要判断与没有出现胜场次数大于 n(n-1) 的，这显然不符合。所以代码如下： #include using namespace std; const int N=15; int n,m,ans; int a[N]; void dfs(int x,int y,int sum){ if(x==n){ if(sum==n*(n-1)){ int sum1=0,sum2=0,sum3=0,sum4=0; for(int i=1;i2*(n-1)) return; } if((sum1==0||sum1==1&&sum3==0)&&(sum2==0||sum2==1&&sum4==0)){ ans++; } } } else{ for(int i=0;i>n>>m; a[1]=m; dfs(1,m,m); cout `#include using namespace std; const int N=15; int n,m,ans; int a[N]; void dfs(int x,int y,int sum){ if(x==n){ if(sum==n*(n-1)){ int sum1=0,sum2=0,sum3=0,sum4=0; for(int i=1;i if(a[i]==0) sum1++; if(a[i]==2*(n-1)) sum2++; if(a[i]==1) sum3++; if(a[i]==2*(n-1)-1) sum4++; if(a[i]>2*(n-1)) return; } if((sum1==0||sum1==1&&sum3==0)&&(sum2==0||sum2==1&&sum4==0)){ ans++; } } } else{ for(int i=0;imin(y,n*(n-1)-sum);i++){ a[x+1]=i; dfs(x+1,i,sum+i); } } } int main(){ cin>>n>>m; a[1]=m; dfs(1,m,m); cout return 0; }` C++ D. 奶牛求幂根据题面很容易想到使用迭代加深搜索，但显而易见是需要一点剪枝的。可以发现，设当前两个存储器内存储的指数分别为 a,b，深度限制为 dep，当前深度为 now。首先：无论操作几次，最终都只能得到 na+mb，又因为 gcd(a,b)|na+mb，所以当 gcd(a,b)\nmid p 时可以直接退出；其次：当目前最大的数乘上 2^{dep-now} 还是小于 p 时，也直接退出。所以代码如下： #include using namespace std; int p,dep; int gcd(int x,int y){ if(!y) return x; else return gcd(y,x%y); } bool dfs(int a,int b,int now){ if(a>p; while(!dfs(1,0,0)) dep++; cout `#include using namespace std; int p,dep; int gcd(int x,int y){ if(!y) return x; else return gcd(y,x%y); } bool dfs(int a,int b,int now){ if(aswap(a,b); if(now==dep) return a==p; if(a&&b) if(p%gcd(a,b)) return 0; if(areturn 0; if(dfs(a+a,b,now+1)) return 1; if(dfs(a+a,a,now+1)) return 1; if(dfs(a,b+b,now+1)) return 1; if(dfs(b+b,b,now+1)) return 1; if(dfs(a+b,b,now+1)) return 1; if(dfs(b+a,a,now+1)) return 1; if(dfs(b,abs(a-b),now+1)) return 1; if(dfs(a,abs(a-b),now+1)) return 1; return 0; } int main(){ cin>>p; while(!dfs(1,0,0)) dep++; cout return 0; }` C++ E. 方格路径K大和可以先用 n^2 的复杂度枚举一个点 (i,j)，并以该点为参考，再以 n^3 的复杂度进行dp，设 dp_{i,j,k} 表示走到点 (i,j) 时选了 k 个大于或等于参考点的最小权值和，就可以很轻松地想到如下代码中的转移 #include using namespace std; #define N 35 #define int long long int n,m,k; int mp[N][N],dp[N][N][2*N]; int ans=1e18; signed main(){ cin>>n>>m>>k; for(int i=1;i>mp[i][j]; for(int x=1;x=mp[x][y]) for(int cnt=1;cnt `#include using namespace std; #define N 35 #define int long long int n,m,k; int mp[N][N],dp[N][N][2*N]; int ans=1e18; signed main(){ cin>>n>>m>>k; for(int i=1;ifor(int j=1;j>mp[i][j]; for(int x=1;xfor(int y=1;y memset(dp,0x3f,sizeof(dp)); dp[1][0][0]=dp[0][1][0]=0; for(int i=1;i for(int j=1;j if(mp[i][j]>=mp[x][y]) for(int cnt=1;cnt dp[i][j][cnt]=min(dp[i][j][cnt],min(dp[i-1][j][cnt-1],dp[i][j-1][cnt-1])+mp[i][j]); if(mp[i][j]mp[x][y]) for(int cnt=0;cnt dp[i][j][cnt]=min(dp[i][j][cnt],min(dp[i-1][j][cnt],dp[i][j-1][cnt])); } ans=min(ans,dp[n][m][k]); } } cout return 0; }` C++ F. 树上字符串匹配这题可以考虑kmp。可以发现，建树时将边权改为字符串，当dfs树的时候，只需保留小字符串的指针就可以。所以如下代码比较板子： #include using namespace std; const int N=3e5+5; struct node{ int v; string w; }; int n,ans,siza; int next1[N]; string a; vector t[N]; void get_next(){ next1[0]=-1; int k=-1; for(int i=1;i-1&&a[k+1]!=a[i]) k=next1[k]; if(a[k+1]==a[i]) k++; next1[i]=k; } } void dfs(int u,int idx,int fa){ for(int i=0;i-1&&a[j+1]!=s[k]) j=next1[j]; if(a[j+1]==s[k]) j++; if(j==siza-1){ ans++; j=next1[j]; } } dfs(v,j,u); } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=2;i>u>>s; t[i].push_back({u,s}); t[u].push_back({i,s}); } cin>>a; siza=a.size(); if(siza==0){ cout `#include using namespace std; const int N=3e5+5; struct node{ int v; string w; }; int n,ans,siza; int next1[N]; string a; vector t[N]; void get_next(){ next1[0]=-1; int k=-1; for(int i=1;i while(k>-1&&a[k+1]!=a[i]) k=next1[k]; if(a[k+1]==a[i]) k++; next1[i]=k; } } void dfs(int u,int idx,int fa){ for(int i=0;it[u].size();i++){ int v=t[u][i].v; string s=t[u][i].w; if(v==fa) continue; int j=idx; for(int k=0;ks.size();k++){ while(j>-1&&a[j+1]!=s[k]) j=next1[j]; if(a[j+1]==s[k]) j++; if(j==siza-1){ ans++; j=next1[j]; } } dfs(v,j,u); } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=2;i int u; string s; cin>>u>>s; t[i].push_back({u,s}); t[u].push_back({i,s}); } cin>>a; siza=a.size(); if(siza==0){ cout0; return 0; } get_next(); dfs(1,-1,0); cout return 0; }` C++