20250816测试

用户头像 发布于 2025-08-16 70 次阅读 OI

S+20250816测试

A. 回文插入

暴力找到插入位置即可，
代码：

#include<bits/stdc++.h>
using namespace std;
int ans;
string a,b;
bool check(string s){
    for(int i=0,j=s.size()-1;i<s.size();i++,j--)
        if(s[i]!=s[j]) return 0;
    return 1;
}
int main(){
    cin>>a>>b;
    for(int i=0;i<=a.size();i++){
        string c=a.substr(0,i)+b+a.substr(i,a.size()-i);
        if(check(c)) ans++;
    }
    cout<<ans;
    return 0;
}
C++

B. 三角形

判断三个点是否共线即可，
可以算出任意两点之间的斜率比较，
代码：

#include<bits/stdc++.h>
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<=n;i++) cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) for(int k=j+1;k<=n;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<<ans;
    return 0;
}
C++

C. 幂次整除

进行质因数分解，
判断指数之间的关系，
代码：

#include<bits/stdc++.h>
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<=t;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<cnt;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<e*d){
            cout<<"not divisible";
            return 0;
        }
    }
    cout<<"divisible";
    return 0;
}
C++

D. 完整正方形

dp，可以发现：
以 $(x, y)$ 为左上角的最大无洞正方形的边长，
取决于其右侧、下侧和右下侧的最大无洞正方形的边长中的最小值加一。
所以代码如下：

#include<bits/stdc++.h>
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<=n;i++) for(int j=1;j<=m;j++) ans+=dp[i][j];
    cout<<ans;
    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<bits/stdc++.h>
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<<0;
    else{
        for(int i=1;i*i<=b-a;i++) if((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<ans) ans=ans1,k=k1;
            if(ans2<ans) ans=ans2,k=k2;
        }
        cout<<k;
    }
    return 0;
}
C++

F. 小学数学

不难发现，可以将每个 $i$ 与其运算结果建边，
一定会形成一个二分图，
套上二分图最大匹配的模板即可，
代码：

#include<bits/stdc++.h>
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<int,int> m;
vector<int> g[N];
bool dfs(int u){
    for(int i=0;i<g[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<=n;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<=n;i++){
        memset(vis,0,sizeof vis);
        if(!dfs(i)){
            cout<<"impossible";
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        int x=a[i],y=b[i];
        if(x+y==sum[mtch[i]]) cout<<x<<" + "<<y<<" = "<<sum[mtch[i]]<<endl;
        else if(x-y==sum[mtch[i]]) cout<<x<<" - "<<y<<" = "<<sum[mtch[i]]<<endl;
        else if(x*y==sum[mtch[i]]) cout<<x<<" * "<<y<<" = "<<sum[mtch[i]]<<endl;
    }
    return 0;
}
C++

G. XOR寄存器

考虑对二进制每一位单独操作，
对于每一位的两种取值，我们可以建两个点，
对于操作二，如果异或后结果是 $1$，那就将 $0$ 与 $0$、$1$ 与 $1$ 建边，
结果是 $1$ 则反之。
对于操作一，可以标记移了多少位，循环对应时再考虑即可。
当一个位置上的两种取值在同一个集合里，显然无解，
而对于有解的情况，贪心使高位为 $0$，
代码如下：

#include<bits/stdc++.h>
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<=e;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;i<32;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;i<=n;i++) for(int j=0;j<32;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<=n;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<<j);
            }
        }
        for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    }
    return 0;
}
C++