20250816测试 · ooliver

S+20250816测试 A. 回文插入暴力找到插入位置即可，代码： #include using namespace std; int ans; string a,b; bool check(string s){ for(int i=0,j=s.size()-1;i>a>>b; for(int i=0;i `#include using namespace std; int ans; string a,b; bool check(string s){ for(int i=0,j=s.size()-1;is.size();i++,j--) if(s[i]!=s[j]) return 0; return 1; } int main(){ cin>>a>>b; for(int i=0;ia.size();i++){ string c=a.substr(0,i)+b+a.substr(i,a.size()-i); if(check(c)) ans++; } cout return 0; }` C++ B. 三角形判断三个点是否共线即可，可以算出任意两点之间的斜率比较，代码： #include using namespace std; #define ll long long const int N=305; int n,ans; ll x[N],y[N]; int main(){ cin>>n; for(int i=1;i>x[i]>>y[i]; for(int i=1;i `#include using namespace std; #define ll long long const int N=305; int n,ans; ll x[N],y[N]; int main(){ cin>>n; for(int i=1;i>x[i]>>y[i]; for(int i=1;ifor(int j=i+1;jfor(int k=j+1;k if(x[i]==x[j]&&x[j]==x[k]) continue; if(y[i]==y[j]&&y[j]==y[k]) continue; if((x[j]-x[i])*(y[k]-y[j])==(x[k]-x[j])*(y[j]-y[i])) continue; ans++; } cout return 0; }` C++ C. 幂次整除进行质因数分解，判断指数之间的关系，代码： #include using namespace std; #define int long long int a,b,c,d; int p[32],ex[32],cnt; signed main(){ cin>>a>>b>>c>>d; if(c==1){ cout1) p[cnt]=t,ex[cnt]=1,cnt++; for(int i=0;i `#include using namespace std; #define int long long int a,b,c,d; int p[32],ex[32],cnt; signed main(){ cin>>a>>b>>c>>d; if(c==1){ cout"divisible"; return 0; } int t=c; for(int i=2;i*i if(t%i==0){ p[cnt]=i; ex[cnt]=0; while(t%i==0) ex[cnt]++,t/=i; cnt++; } } if(t>1) p[cnt]=t,ex[cnt]=1,cnt++; for(int i=0;i int pr=p[i],e=ex[i]; int ea=0,ta=a; while(ta%pr==0) ea++,ta/=pr; if(ea==0||ea*b cout"not divisible"; return 0; } } cout"divisible"; return 0; }` C++ D. 完整正方形 dp，可以发现：以 (x, y) 为左上角的最大无洞正方形的边长，取决于其右侧、下侧和右下侧的最大无洞正方形的边长中的最小值加一。所以代码如下： #include using namespace std; #define int long long const int N=3005; int n,m,q,ans; int a[N][N],dp[N][N]; signed main(){ cin>>n>>m>>q; while(q--){ int x,y; cin>>x>>y; a[x][y]=1; } for(int i=n;i>=1;i--) for(int j=m;j>=1;j--){ if(a[i][j]) continue; else if(i==n&&j==m) dp[n][m]=1; else dp[i][j]=min(dp[i+1][j],min(dp[i][j+1],dp[i+1][j+1]))+1; } for(int i=1;i `#include using namespace std; #define int long long const int N=3005; int n,m,q,ans; int a[N][N],dp[N][N]; signed main(){ cin>>n>>m>>q; while(q--){ int x,y; cin>>x>>y; a[x][y]=1; } for(int i=n;i>=1;i--) for(int j=m;j>=1;j--){ if(a[i][j]) continue; else if(i==n&&j==m) dp[n][m]=1; else dp[i][j]=min(dp[i+1][j],min(dp[i][j+1],dp[i+1][j+1]))+1; } for(int i=1;ifor(int j=1;jdp[i][j]; cout return 0; }` C++ E. 偏移量 \begin{align} \because \gcd(a+k,b+k)&=\gcd(a+k,b-a) \\ \therefore \gcd(a+k,b+k)& | (b-a) \end{align} 对于 (b-a) 的每一个因子 i， \text{lcm}(a+k,b+k)_{\max} \implies k \equiv -a (\bmod i) 所以代码如下： #include using namespace std; #define int long long int a,b,ans=INT_MAX,k; signed main(){ cin>>a>>b; if(a>b) swap(a,b); if(a==b) cout `#include using namespace std; #define int long long int a,b,ans=INT_MAX,k; signed main(){ cin>>a>>b; if(a>b) swap(a,b); if(a==b) cout0; else{ for(int i=1;i*iif((b-a)%i==0){ int mod1=i,mod2=(b-a)/i; int k1=((-a)%mod1+mod1)%mod1,k2=((-a)%mod2+mod2)%mod2; int ans1=(a+k1)*(b+k1)/__gcd(a+k1,b+k1), ans2=(a+k2)*(b+k2)/__gcd(a+k2,b+k2); if(ans1 if(ans2 } cout } return 0; }` C++ F. 小学数学不难发现，可以将每个 i 与其运算结果建边，一定会形成一个二分图，套上二分图最大匹配的模板即可，代码： #include using namespace std; #define int long long const int N=1e5+5; int n,idx; int vis[N],match[N],mtch[N],sum[N]; int a[N],b[N]; map m; vector g[N]; bool dfs(int u){ for(int i=0;i>n; for(int i=1;i>x>>y; a[i]=x,b[i]=y; if(!m[x+y]){ m[x+y]=++idx,sum[idx]=x+y; g[i].push_back(idx); } else g[i].push_back(m[x+y]); if(!m[x-y]){ m[x-y]=++idx,sum[idx]=x-y; g[i].push_back(idx); } else g[i].push_back(m[x-y]); if(!m[x*y]){ m[x*y]=++idx,sum[idx]=x*y; g[i].push_back(idx); } else g[i].push_back(m[x*y]); } for(int i=1;i `#include using namespace std; #define int long long const int N=1e5+5; int n,idx; int vis[N],match[N],mtch[N],sum[N]; int a[N],b[N]; mapint,int> m; vectorint> g[N]; bool dfs(int u){ for(int i=0;ig[u].size();i++){ int v=g[u][i]; if(vis[v]) continue; vis[v]=1; if(!match[v]||dfs(match[v])){ match[v]=u; mtch[u]=v; return 1; } } return 0; } signed main(){ cin>>n; for(int i=1;i int x,y; cin>>x>>y; a[i]=x,b[i]=y; if(!m[x+y]){ m[x+y]=++idx,sum[idx]=x+y; g[i].push_back(idx); } else g[i].push_back(m[x+y]); if(!m[x-y]){ m[x-y]=++idx,sum[idx]=x-y; g[i].push_back(idx); } else g[i].push_back(m[x-y]); if(!m[x*y]){ m[x*y]=++idx,sum[idx]=x*y; g[i].push_back(idx); } else g[i].push_back(m[x*y]); } for(int i=1;i memset(vis,0,sizeof vis); if(!dfs(i)){ cout"impossible"; return 0; } } for(int i=1;i int x=a[i],y=b[i]; if(x+y==sum[mtch[i]]) cout" + "" = "sum[mtch[i]] else if(x-y==sum[mtch[i]]) cout" - "" = "sum[mtch[i]] else if(x*y==sum[mtch[i]]) cout" * "" = "sum[mtch[i]] } return 0; }` C++ G. XOR寄存器考虑对二进制每一位单独操作，对于每一位的两种取值，我们可以建两个点，对于操作二，如果异或后结果是 1，那就将 0 与 0、1 与 1 建边，结果是 1 则反之。对于操作一，可以标记移了多少位，循环对应时再考虑即可。当一个位置上的两种取值在同一个集合里，显然无解，而对于有解的情况，贪心使高位为 0，代码如下： #include using namespace std; typedef unsigned u32; const int N=1e5+1; int n,e; u32 ans[N]; int tag[N],fa[N*64]; int find(int x){ return fa[x]>n>>e; for(int j=1;j>op>>k>>l; if(op==1) tag[k]=(tag[k]+l)%32; if(op==2){ u32 x; cin>>x; for(int i=0;i>i)&1; if(!y){ merge(id(k,(i+tag[k])%32,0),id(l,(i+tag[l])%32,0)); merge(id(k,(i+tag[k])%32,1),id(l,(i+tag[l])%32,1)); } else{ merge(id(k,(i+tag[k])%32,0),id(l,(i+tag[l])%32,1)); merge(id(k,(i+tag[k])%32,1),id(l,(i+tag[l])%32,0)); } } } } bool flag=0; for(int i=1;i=0;j--){ if(fa[find(id(i,j,0))]==0) fa[find(id(i,j,0))]=-1,fa[find(id(i,j,1))]=-2; else if(fa[find(id(i,j,0))]==-2) ans[i]+=(1u `#include using namespace std; typedef unsigned u32; const int N=1e5+1; int n,e; u32 ans[N]; int tag[N],fa[N*64]; int find(int x){ return fa[x]0?x:fa[x]=find(fa[x]); } void merge(int u,int v){ if(find(u)==find(v)) return; fa[find(u)]=find(v); } int id(int n1,int p,int b){ int x=(n1-1)*32+p+1; if(b) x+=n*32; return x; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>e; for(int j=1;j int op,k,l; cin>>op>>k>>l; if(op==1) tag[k]=(tag[k]+l)%32; if(op==2){ u32 x; cin>>x; for(int i=0;i32;i++){ int y=(x>>i)&1; if(!y){ merge(id(k,(i+tag[k])%32,0),id(l,(i+tag[l])%32,0)); merge(id(k,(i+tag[k])%32,1),id(l,(i+tag[l])%32,1)); } else{ merge(id(k,(i+tag[k])%32,0),id(l,(i+tag[l])%32,1)); merge(id(k,(i+tag[k])%32,1),id(l,(i+tag[l])%32,0)); } } } } bool flag=0; for(int i=1;ifor(int j=0;j32;j++) if(find(id(i,j,0))==find(id(i,j,1))) flag=1; if(flag) cout"-1\n"; else{ for(int i=1;i for(int j=31;j>=0;j--){ if(fa[find(id(i,j,0))]==0) fa[find(id(i,j,0))]=-1,fa[find(id(i,j,1))]=-2; else if(fa[find(id(i,j,0))]==-2) ans[i]+=(1u } } for(int i=1;ians[i]" "; } return 0; }` C++