20250812测试 · ooliver

S+20250812测试 A. 炫彩染色枚举两种情况，输出最小答案即可，代码： #include using namespace std; string s; int ans1,ans2; int main(){ cin>>s; for(int i=0;i `#include using namespace std; string s; int ans1,ans2; int main(){ cin>>s; for(int i=0;is.size();i++){ if(i%2==1&&s[i]=='1') ans1++; if(i%2==0&&s[i]=='0') ans1++; } for(int i=0;is.size();i++){ if(i%2==1&&s[i]=='0') ans2++; if(i%2==0&&s[i]=='1') ans2++; } coutmin(ans1,ans2); return 0; }` C++ B. 寻找饼干可以发现，当一个“.”四面起码有两面是“#”时，证明它在长方形内。代码： #include using namespace std; const int N=505; int n,m; int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; char a[N][N]; int main(){ cin>>n>>m; for(int i=1;i>a[i][j]; for(int i=1;in||ym) continue; if(a[x][y]=='#') cnt++; } if(cnt>1){ cout `#include using namespace std; const int N=505; int n,m; int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; char a[N][N]; int main(){ cin>>n>>m; for(int i=1;ifor(int j=1;j>a[i][j]; for(int i=1;ifor(int j=1;j if(a[i][j]=='#') continue; int cnt=0; for(int k=0;k4;k++){ int x=i+dx[k],y=j+dy[k]; if(x1||x>n||y1||y>m) continue; if(a[x][y]=='#') cnt++; } if(cnt>1){ cout" " return 0; } } return 0; }` C++ C. 戴帽子对于每种颜色肯定是一个公差为一，第一个元素为0的等差数列。所以维护3个序列的结尾即可。每个可以添加到结尾的序列，可能性加一，最后答案乘上可能性即可。代码： #include using namespace std; #define int long long const int N=1e6+5,mod=1e9+7; int n,ans=1,a[N],t[]={0,-1,-1,-1},fnl,cnt; signed main(){ cin>>n; for(int i=1;i>a[i]; for(int i=1;i `#include using namespace std; #define int long long const int N=1e6+5,mod=1e9+7; int n,ans=1,a[N],t[]={0,-1,-1,-1},fnl,cnt; signed main(){ cin>>n; for(int i=1;i>a[i]; for(int i=1;i cnt=0; for(int j=1;j3;j++) if(t[j]+1==a[i]) cnt++,fnl=j; (ans*=cnt)%=mod,t[fnl]++; } cout return 0; }` C++ D. 极大递增子序列根据性质暴搜即可，代码： #include using namespace std; #define int long long const int N=55; int n,ans; int a[N]; void dfs(int id){ int y=1,minn=INT_MAX; for(int i=id+1;iminn) continue; minn=a[i],y=0; dfs(i); } if(y) ans++; } signed main(){ cin>>n; for(int i=1;i>a[i]; dfs(0); cout `#include using namespace std; #define int long long const int N=55; int n,ans; int a[N]; void dfs(int id){ int y=1,minn=INT_MAX; for(int i=id+1;i if(a[i]a[id]||a[i]>minn) continue; minn=a[i],y=0; dfs(i); } if(y) ans++; } signed main(){ cin>>n; for(int i=1;i>a[i]; dfs(0); cout return 0; }` C++ E. 守卫树设 dp_{u,j,k} 表示点 u 的子树中恰好有 j 个符合题意的子节点的方案数量，其中 k\in[0,2]，表示该节点被守护的状态： k=0 时，表示该点有一名守卫 k=1 时，表示该点没有守卫，但是被儿子守护 k=2 时，表示该店没有守卫，也不被守护综上，代码如下： #include using namespace std; #define int long long const int N=2005,mod=1e9+7; int n; int siz[N],dp[N][N][3],f[N][3]; vector t[N]; void dfs(int u,int fa){ dp[u][0][1]=dp[u][1][0]=siz[u]=1; for(int i=0;i>n; for(int i=1;i>u>>v; t[u].push_back(v); t[v].push_back(u); } dfs(1,0); for(int i=0;i `#include using namespace std; #define int long long const int N=2005,mod=1e9+7; int n; int siz[N],dp[N][N][3],f[N][3]; vectorint> t[N]; void dfs(int u,int fa){ dp[u][0][1]=dp[u][1][0]=siz[u]=1; for(int i=0;it[u].size();i++){ int v=t[u][i]; if(v==fa) continue; dfs(v,u); memset(f,0,sizeof f); for(int j=0;jsiz[u];j++) for(int k=0;ksiz[v];k++){ (f[j+k][0]+=dp[u][j][0]*(dp[v][k][0]+dp[v][k][2])%mod)%=mod; (f[j+k+1][0]+=dp[u][j][0]*dp[v][k][1]%mod)%=mod;//覆盖v (f[j+k][1]+=dp[u][j][1]*(dp[v][k][1]+dp[v][k][2])%mod)%=mod; (f[j+k+1][2]+=dp[u][j][1]*dp[v][k][0]%mod)%=mod;//覆盖u (f[j+k][2]+=dp[u][j][2]*(dp[v][k][0]+dp[v][k][1]+dp[v][k][2])%mod)%=mod; } siz[u]+=siz[v]; for(int j=0;jsiz[u];j++){ dp[u][j][0]=f[j][0];//选自己 dp[u][j][1]=f[j][1];//不选，未被覆盖 dp[u][j][2]=f[j][2];//不选，被覆盖 } } } signed main(){ cin>>n; for(int i=1;i int u,v; cin>>u>>v; t[u].push_back(v); t[v].push_back(u); } dfs(1,0); for(int i=0;idp[1][i][0]+dp[1][i][1]+dp[1][i][2])%mod return 0; }` C++ F. 计算根号分治题。首先将左右端点都单点离线处理，最后差分，按照端点升序排序，当 $p #include using namespace std; #define int long long const int N=1e5+5; struct node{ int end,p,k,id1,id2; }q[N*2]; int n,m,mx; int a[N],ans[2][N],mod[105][105],t[N]; bool cmp(node x,node y) {return x.end>n>>m; for(int i=1;i>a[i],mx=max(mx,a[i]); for(int i=1;i>l>>r>>p>>k; q[2*i-1]={l-1,p,k,0,i}; q[2*i]={r,p,k,1,i}; } sort(q+1,q+1+2*m,cmp); int idx=0; for(int i=1;i `#include using namespace std; #define int long long const int N=1e5+5; struct node{ int end,p,k,id1,id2; }q[N*2]; int n,m,mx; int a[N],ans[2][N],mod[105][105],t[N]; bool cmp(node x,node y) {return x.endy.end;} void add(int x){ for(int i=1;i100;i++) mod[i][x%i]++; t[x]++; } signed main(){ cin>>n>>m; for(int i=1;i>a[i],mx=max(mx,a[i]); for(int i=1;i int l,r,p,k; cin>>l>>r>>p>>k; q[2*i-1]={l-1,p,k,0,i}; q[2*i]={r,p,k,1,i}; } sort(q+1,q+1+2*m,cmp); int idx=0; for(int i=1;i2*m;i++){ int end=q[i].end,p=q[i].p,k=q[i].k,id1=q[i].id1,id2=q[i].id2; while(idxadd(a[idx]),idx++; if(p100) ans[id1][id2]=mod[p][k]; else for(int i=k;ians[id1][id2]+=t[i]; } for(int i=1;ians[1][i]-ans[0][i] return 0; }` C++ G. 旅行家边双+缩点，缩点后数上差分，最后前缀和一边，权为正的点加上其边双的点权和，代码如下： #include using namespace std; const int N=1e6+5; struct node{ int v,id; }; vector g[N]; vector t[N]; stack s; int n,m,q,ans; int dfn[N],low[N],vis[N],idx,cnt; int w1[N],w[N],sum[N]; int fa[N][25],d[N]; void tj(int u,int e){ dfn[u]=low[u]=++idx; s.push(u); for(int i=0;i=0;i--){ if(d[fa[u][i]]>=d[v]){ u=fa[u][i]; } } if(u==v) return u; for(int i=20;i>=0;i--){ if(fa[u][i]!=fa[v][i]){ u=fa[u][i]; v=fa[v][i]; } } return fa[u][0]; } void dfs2(int u){ for(int i=0;i>n>>m; for(int i=1;i>w1[i]; for(int i=1;i>u>>v; g[u].push_back({v,i>q; while(q--){ int x,y; cin>>x>>y; x=vis[x],y=vis[y]; sum[x]++,sum[y]++,sum[lca(x,y)]--,sum[fa[lca(x,y)][0]]--; } dfs2(1); cout `#include using namespace std; const int N=1e6+5; struct node{ int v,id; }; vector g[N]; vectorint> t[N]; stackint> s; int n,m,q,ans; int dfn[N],low[N],vis[N],idx,cnt; int w1[N],w[N],sum[N]; int fa[N][25],d[N]; void tj(int u,int e){ dfn[u]=low[u]=++idx; s.push(u); for(int i=0;ig[u].size();i++){ int v=g[u][i].v,id=g[u][i].id; if(!dfn[v]){ tj(v,id); low[u]=min(low[u],low[v]); } else if((id^1)!=e) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]){ cnt++; while(1){ int y=s.top();s.pop(); vis[y]=cnt; w[cnt]+=w1[y]; if(y==u) break; } } } void dfs(int u,int f){ fa[u][0]=f,d[u]=d[f]+1; for(int i=1;i20;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=0;it[u].size();i++){ int v=t[u][i]; if(v==f) continue; dfs(v,u); } } int lca(int u,int v){ if(d[u]d[v]) swap(u,v); for(int i=20;i>=0;i--){ if(d[fa[u][i]]>=d[v]){ u=fa[u][i]; } } if(u==v) return u; for(int i=20;i>=0;i--){ if(fa[u][i]!=fa[v][i]){ u=fa[u][i]; v=fa[v][i]; } } return fa[u][0]; } void dfs2(int u){ for(int i=0;it[u].size();i++){ int v=t[u][i]; if(v==fa[u][0]) continue; dfs2(v); sum[u]+=sum[v]; } if(sum[u]) ans+=w[u]; } int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i>w1[i]; for(int i=1;i int u,v; cin>>u>>v; g[u].push_back({v,i1}); g[v].push_back({u,i1|1}); } tj(1,-1); for(int u=1;ufor(int i=0;ig[u].size();i++){ int v=g[u][i].v; if(vis[u]!=vis[v]){ t[vis[u]].push_back(vis[v]); t[vis[v]].push_back(vis[u]); } } for(int i=1;i sort(t[i].begin(),t[i].end()); t[i].erase(unique(t[i].begin(),t[i].end()),t[i].end()); } dfs(1,0); cin>>q; while(q--){ int x,y; cin>>x>>y; x=vis[x],y=vis[y]; sum[x]++,sum[y]++,sum[lca(x,y)]--,sum[fa[lca(x,y)][0]]--; } dfs2(1); cout"\n"; return 0; }` C++