• A. Shovels and Swords
• B. Shuffle
• C. Palindromic Paths
• D. Two Divisors
• E. Two Arrays

A. Shovels and Swords

MC 好评

我的方法详见代码，先来欣赏一下猛男（%gyz%jiedai 等人）的方法。

scanf("%d%d",&n,&m);
n=min(n,m*2);
m=min(m,n*2);
printf("%d\n",(n+m)/3);

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=200010; typedef long long ll;
//#define int ll
int T,a,b,ans;
signed main(){
    cin>>T;
    while(T--){
        ans=0;
        cin>>a>>b;
        if(a>b)swap(a,b); //让钻石锹个数小于钻石剑个数
        int t=min({a,b/2,b-a}); //买钻石剑
        a-=t; b-=2*t; ans+=t;
        t=min({a/3,b/3}); //钻石锹和钻石剑一起买
        a-=t*3; b-=t*3; ans+=2*t;
        if(a && b && a+b>=3)ans++;
        cout<<ans<<endl;
    }
    return 0;
}

B. Shuffle

每输入一个区间，就扩展一下区间 \{i | a_i 可能为 1\}（←这个是区间）。

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=200010; typedef long long ll;
#define int ll
int T;
signed main(){
    cin>>T;
    while(T--){
        int n,m,x,y;
        cin>>n>>x>>m; y=x;
        while(m--){
            int l,r;
            cin>>l>>r;
            if(!(max(l,r)<min(x,y) || max(x,y)<min(l,r))){ //区间有公共部分
                x=min(x,l);
                y=max(y,r);
            }
        }
        cout<<y-x+1<<endl;
    }
    return 0;
}

C. Palindromic Paths

其实就是所有需要相等的数放在一起计算的事情。

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=210; typedef long long ll;
#define int ll
int T,n,m;
map<int,int> mp[N];
signed main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        repeat(i,2,n+m+1)mp[i].clear();
        repeat(i,1,n+1)
        repeat(j,1,m+1){
            int x; cin>>x;
            if((n+m)%2==0 && i+j==(n+m+2)/2)continue; //回文串的中间是不需要考虑是否相等的
            mp[min(i+j,n+m+2-i-j)][x]++;
        }
        int ans=0;
        repeat(i,2,n+m+1){
            int mx=0,sum=0;
            for(auto j:mp[i])mx=max(mx,j.second),sum+=j.second;
            ans+=sum-mx;
        }
        cout<<ans<<endl;
    }
    return 0;
}

D. Two Divisors

挺好一题。

引理：如果 $d_1,d_2$ 互质，那么 $d_1+d_2,d_1d_2$ 互质。

根据引理，我们只要找到 $d_1d_2=a$ 且 $d_1,d_2$ 互质的两个数 $d_1,d_2$。互质，就是不能包含相同质因子，我们让 $d_1$ 吃掉 $a$ 的全部的某个质因子，这样 $d_2=\dfrac a {d_1}$ 一定不包含这个质因子也就互质了。最终只要判断 $d_2=\dfrac a {d_1}>1$ 即可。

由于时间卡得有点紧，不如找个能求最小质因数的线性筛 qwq。

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=10000010; typedef long long ll;
#define int ll
int a[N],rec[N]; bool vis[N];
//a[i]表示第i+1个质数，vis[i]==0表示i是素数，rec[i]为i的最小质因数
void get_prime(int n){
    int cnt=0; vis[1]=1;
    repeat(i,2,n+1){
        if(!vis[i])
            a[cnt++]=i,rec[i]=i;
        repeat(j,0,cnt){
            if(i*a[j]>n)break;
            vis[i*a[j]]=1;
            rec[i*a[j]]=a[j];
            if(i%a[j]==0)break;
        }
    }
}
vector<pair<int,int>> ans;
signed main(){
    get_prime(N-1);
    int n; cin>>n; 
    while(n--){
        int x; cin>>x;
        int p=rec[x],y=1;
        if(p>1)while(x%p==0)x/=p,y*=p;
        if(x>1 && y>1)
            ans.push_back({x,y});
        else ans.push_back({-1,-1});
    }
    for(auto i:ans)cout<<i.first<<' '; cout<<endl;
    for(auto i:ans)cout<<i.second<<' '; cout<<endl;
    return 0;
}

E. Two Arrays

一开始没看到 $b[i]$ 是单增的。既然单增，那简单亿倍。

我们让 $a[i]=min(a[i],a[i+1])$，这样可以强行让 $a[i]$ 单调不减。假设 $[l,r]$ 覆盖了 $a[i]=b[j]$ 的所有 $i$，很显然 $b[j]$ 对应的区间右端点必须为 $r$，区间左端点可以是 $[l,r]$ 的任何数（除了 $j=1$ 的情况）。这样就完美解决问题。

特判几种情况即可。

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=200010; typedef long long ll; const int inf=~0u>>2;
const int mod=998244353;
#define int ll
int a[N],b[N],n,m,ans=1;
map<int,int> mp;
signed main(){
    cin>>n>>m;
    repeat(i,0,n)cin>>a[i];
    repeat(i,0,m)cin>>b[i],mp[b[i]]=0;
    repeat_back(i,0,n-1)a[i]=min(a[i],a[i+1]);
    if(a[0]!=b[0])cout<<0<<endl,exit(0); //最小值不相等
    repeat_back(i,0,n){
        if(mp.count(a[i]))
            mp[a[i]]++;
    }
    for(auto it=++mp.begin();it!=mp.end();it++){ //++mp.begin()跳过了第一个区间
        (ans*=it->second)%=mod;
    }
    cout<<ans<<endl;
    return 0;
}