20250814测试 · ooliver

S+20250814测试 A. 交换序列暴力枚举即可代码： #include using namespace std; int n,y=1,ans; int a[55]; int main(){ cin>>n; for(int i=1;i>a[i]; if(a[i] `#include using namespace std; int n,y=1,ans; int a[55]; int main(){ cin>>n; for(int i=1;i cin>>a[i]; if(a[i]a[i-1]) y=0; } if(y){ cout"YES"; return 0; } for(int i=1;ifor(int j=1;jif(i!=j){ swap(a[i],a[j]); int ye=1; for(int k=1;kif(a[k]a[k-1]) ye=0; if(ye){ cout"YES"; return 0; } swap(a[i],a[j]); } cout"NO"; return 0; }` C++ B. 最小绝对值解方程： \begin{align} x^2+y^2-D&=0 \\ y&=\sqrt{D-x^2} \\ \end{align} 因为精度问题需要将 y 的上下界都计算一遍，代码： #include using namespace std; long long d,ans=LONG_LONG_MAX; int main(){ cin>>d; for(long long x=0;x*x `#include using namespace std; long long d,ans=LONG_LONG_MAX; int main(){ cin>>d; for(long long x=0;x*x long long y=sqrt(d-x*x); ans=min(min(ans,abs(d-x*x-y*y)),abs(d-x*x-(y+1)*(y+1))); } cout return 0; }` C++ C. 3色骨牌染色问题，一共有两种可能，两个横着的和一个竖着的。动手模拟一下就可以，这里不赘述。代码： #include using namespace std; #define int long long const int mod=1e9+7; int n,ans=1; char a[3][55]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i>a[i][j]; for(int i=1;i `#include using namespace std; #define int long long const int mod=1e9+7; int n,ans=1; char a[3][55]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i2;i++) for(int j=1;j>a[i][j]; for(int i=1;i if(a[1][i]!=a[2][i]){ if(i==1) (ans*=6)%=mod; else if(a[1][i-1]!=a[2][i-1]) (ans*=3)%=mod; else (ans*=2)%=mod; i++; } else{ if(i==1) (ans*=3)%=mod; else if(a[1][i-1]!=a[2][i-1]) ans%=mod; else (ans*=2)%=mod; } } cout return 0; }` C++ D. 翻转行列枚举每行每列最终反转了几个，判断是否与条件所给的数模 2 同余，再用组合数计算一下答案即可。 #include using namespace std; #define int long long const int N=3e3+5,mod=555555555; int c[N][N]; int h,w,r,c1,s,ans; int check(int m,int n,int k){ if(k%2!=n%2) return 0; return (c[m][k]%mod*c[(n-k)/2+m-1][m-1])%mod; } signed main(){ cin>>h>>w>>r>>c1>>s; c[0][0]=1; for(int i=1;i `#include using namespace std; #define int long long const int N=3e3+5,mod=555555555; int c[N][N]; int h,w,r,c1,s,ans; int check(int m,int n,int k){ if(k%2!=n%2) return 0; return (c[m][k]%mod*c[(n-k)/2+m-1][m-1])%mod; } signed main(){ cin>>h>>w>>r>>c1>>s; c[0][0]=1; for(int i=1;ifor(int j=0;j if(j==i||j==0) c[i][j]=1; else (c[i][j]=c[i-1][j]+c[i-1][j-1])%=mod; } for(int i=0;ifor(int j=0;j if(i*w+j*h-2*i*j==s) (ans+=check(h,r,i)*check(w,c1,j%mod))%=mod; } cout return 0; }` C++ E. 键帽暴力的dp： \begin{align} dp_{i,0}&=\sum_{j=max(0,i-k)}^{i-1}dp_{j,1}·5^{i-j} \\ dp_{i,1}&=(dp_{i-1,1}+dp_{i-1,1})·21 \\ \end{align} 其中 0 表示以元音结尾，1 以辅音结尾。发现第一个转移和哈希非常像，可以用类似的思想优化，代码如下： #include using namespace std; #define int long long const int mod=1e9+7; const int N=5e6+5; int T; int n,k,dp[N][2],p[N]; signed main(){ p[0]=1; for(int i=1;i>T; while(T--){ int hsh=1; cin>>n>>k; dp[0][0]=dp[0][1]=1; for(int i=1;ik) (hsh+=mod-dp[i-k-1][1]*p[k+1]%mod)%=mod; dp[i][0]=hsh; } cout `#include using namespace std; #define int long long const int mod=1e9+7; const int N=5e6+5; int T; int n,k,dp[N][2],p[N]; signed main(){ p[0]=1; for(int i=1;ip[i]=p[i-1]*5)%=mod; cin>>T; while(T--){ int hsh=1; cin>>n>>k; dp[0][0]=dp[0][1]=1; for(int i=1;i dp[i][1]=dp[i-1][0]*21%mod,(hsh=hsh*5+dp[i][1])%=mod; if(i>k) (hsh+=mod-dp[i-k-1][1]*p[k+1]%mod)%=mod; dp[i][0]=hsh; } coutdp[n][0] } return 0; }` C++ F. 偷金计划计算出每个点与守卫的距离作为点权那么新的边权可以看成两个端点的点权最小值，然后计算最大生成树，做树上lca。代码： #include using namespace std; #define int long long const int N=2e5+5, K=20, INF=2e18; int n,m,k,qs,x,y,dis[N],f[N][K+1],mm[N][K+1],dep[N],fa[N]; bool vis[N]; struct edge{int u,v,w;} p[N]; struct node{int id,val;}; vector e[N],g[N]; priority_queue q; bool operatorb.val;} bool operatorb.w;} int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} void dfs(int u,int fa){ f[u][0]=fa, dep[u]=dep[fa]+1; for(auto v:g[u]) if(v.id!=fa){ mm[v.id][0]=v.val, dfs(v.id,u); } } int lca(int x,int y){ int res=INF; if(dep[x]=0;i--) if(dep[f[x][i]]>=dep[y]) res=min(res,mm[x][i]),x=f[x][i]; if(x==y) return res-1; for(int i=K;i>=0;i--) if(f[x][i]!=f[y][i]){ res=min({res,mm[x][i],mm[y][i]}); x=f[x][i],y=f[y][i]; } return min({res,mm[x][0],mm[y][0]})-1; } signed main(){ ios::sync_with_stdio(0),cin.tie(0); cin>>n>>m; for(int i=1;i>p[i].u>>p[i].v>>p[i].w; e[p[i].u].push_back({p[i].v,p[i].w}); e[p[i].v].push_back({p[i].u,p[i].w}); } cin>>k; for(int i=1;i>x,q.push({x,dis[x]=0}); while(!q.empty()){ auto u=q.top(); q.pop(); if(vis[u.id]) continue; vis[u.id]=1; for(auto v:e[u.id]) if(dis[v.id]>dis[u.id]+v.val) q.push({v.id,dis[v.id]=dis[u.id]+v.val}); } for(int i=1;i>qs; while(qs--){ cin>>x>>y; cout `#include using namespace std; #define int long long const int N=2e5+5, K=20, INF=2e18; int n,m,k,qs,x,y,dis[N],f[N][K+1],mm[N][K+1],dep[N],fa[N]; bool vis[N]; struct edge{int u,v,w;} p[N]; struct node{int id,val;}; vector e[N],g[N]; priority_queue q; bool operator(node a,node b){return a.val>b.val;} bool operator(edge a,edge b){return a.w>b.w;} int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} void dfs(int u,int fa){ f[u][0]=fa, dep[u]=dep[fa]+1; for(auto v:g[u]) if(v.id!=fa){ mm[v.id][0]=v.val, dfs(v.id,u); } } int lca(int x,int y){ int res=INF; if(dep[x]dep[y]) swap(x,y); for(int i=K;i>=0;i--) if(dep[f[x][i]]>=dep[y]) res=min(res,mm[x][i]),x=f[x][i]; if(x==y) return res-1; for(int i=K;i>=0;i--) if(f[x][i]!=f[y][i]){ res=min({res,mm[x][i],mm[y][i]}); x=f[x][i],y=f[y][i]; } return min({res,mm[x][0],mm[y][0]})-1; } signed main(){ ios::sync_with_stdio(0),cin.tie(0); cin>>n>>m; for(int i=1;i cin>>p[i].u>>p[i].v>>p[i].w; e[p[i].u].push_back({p[i].v,p[i].w}); e[p[i].v].push_back({p[i].u,p[i].w}); } cin>>k; for(int i=1;idis[i]=INF,fa[i]=i; while(k--) cin>>x,q.push({x,dis[x]=0}); while(!q.empty()){ auto u=q.top(); q.pop(); if(vis[u.id]) continue; vis[u.id]=1; for(auto v:e[u.id]) if(dis[v.id]>dis[u.id]+v.val) q.push({v.id,dis[v.id]=dis[u.id]+v.val}); } for(int i=1;ip[i].w=min(dis[p[i].u],dis[p[i].v]); sort(p+1,p+m+1); for(int i=1;i int fu=find(p[i].u),fv=find(p[i].v); if(fu==fv) continue; fa[fu]=fv; g[p[i].u].push_back({p[i].v,p[i].w}); g[p[i].v].push_back({p[i].u,p[i].w}); } dfs(1,0); for(int j=1;jfor(int i=1;i f[i][j]=f[f[i][j-1]][j-1]; mm[i][j]=min(mm[i][j-1],mm[f[i][j-1]][j-1]); } cin>>qs; while(qs--){ cin>>x>>y; coutmax(0ll,lca(x,y))'\n'; } return 0; }` C++