20250816测试

2025年8月16日 ooliver OI

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{array}{l} ∵ [PARSE ERROR: Undefined("Command(\"gcd\")")] (a + k, b + k) & a m p; = [PARSE ERROR: Undefined("Command(\"gcd\")")] (a + k, b - a) \\ ∴ [PARSE ERROR: Undefined("Command(\"gcd\")")] (a + k, b + k) & a m p; | (b - a) \end{array}$ 对于 $(b - a)$ 的每一个因子 $i$ ， $lcm (a + k, b + k)_{\max} ⟹ k \equiv - a ([PARSE ERROR: Undefined("Command(\"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++