CF959

A

看了大佬们的做法都是比较复杂的，jiangly神写的很简洁，可以学习一下，还有换行的技巧。

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    int N = n * m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x;
            std::cin >> x;
            
            if (N == 1) {
                x = -1;
            } else if (x == N) {
                x = 1;
            } else {
                x++;
            }
            std::cout << x << " \n"[j == m - 1];
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

B

容易发现：只需要在\(s_i=0,t_i=1\)的情况下，判断\(s_i\)前面有没有1就行，可以使用一个前缀和统计一下。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
void solve()
{
    int n;  cin>>n;
    string s,t; cin>>s>>t;
    std::vector<int> cnt(n,0);
    if(s[0]=='1')   cnt[0]=1;
    for(int i=1;i<n;i++)
    {
        cnt[i]=cnt[i-1]+s[i]-'0';
    }
    for(int i=0;i<n;i++)
    {
        if(s[i]=='0' && t[i]=='1')
        {
            if(!cnt[i])
            {
                cout<<"NO\n";
                return;
            } 
        }
    }
    cout<<"YES\n";
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}
 

看完jiangly神的码，总是感觉自己很蠢，看大佬的码还是大有裨益。

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    
    std::string s, t;
    std::cin >> s >> t;
    
    bool ok = true;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            break;
        }
        if (t[i] == '1') {
            ok = false;
            break;
        }
    }
    if (ok) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

C

直接暴力肯定会TLE，不难想到：可以使用前缀和先计算各个区间的值。

考虑一个合法的区间\(a_l-a_{p-1}\)，那么\(a_{p-1}\)之后（从\(a_p\)开始）就是重置为0的情况。不难发现：如果是在\(a_{l}-a_{p-1}\)之间，答案就是\(p-l-1\)，那么在\(a_{p-1}\)之后呢？就是\(a_p\)合法的情况（类似的推导），所以这里可以使用\(dp\)，不难得到状态转移方程为\(dp_i=dp_p+p-1-i\)。（这里\(dp_i\)表示的就是从\(i\)位置以后找到的合法情况）。

至于找\(p\)，可以用二分查找，具体看代码。

//wsm in queue
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
const ll mod=998244353;
void solve()
{
    ll n;  ll m;   cin>>n>>m;
    std::vector<ll> v(n+1,0);
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    std::vector<ll> sum(n+1,0);
    for(int i=1;i<=n;i++)    sum[i]=sum[i-1]+v[i];

    std::vector<ll> dp(n+2,0);
    for(int i=n-1;i>=0;i--)
    {
        int p=upper_bound(sum.begin()+i,sum.end(),sum[i]+m)-sum.begin();
        dp[i]=dp[p]+p-i-1;
    }
    cout<<accumulate(dp.begin(),dp.end(),0ll)<<"\n";
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

下面是双指针的做法，这里\(dp\)数组维护的是从\(a_i\)后，一直到\(a_{n-1}\)之间，不合法的区间的长度（包含本身，所以基本长度就是1，所以\(dp_n=1\)），先用双指针寻找合法的区间，再进行\(dp\)。

解释一下状态转移方程：\(a_i\)到\(a_{j-1}\)为合法的区间， 那么从\(dp_j\)往后开始就是非法的区间了，所以状态转移方程是\(dp_i=dp_j+1\)，所以不难得到此时非法的范围数值就是\(dp_j\)，这里用\(dp_i-1\)主要是因为需要讨论\(j\)，写成这样简单一点。

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n, x;
    std::cin >> n >> x;
    
    //a的下标是从0~n-1
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    //sum的下标是从1~n
    std::vector<i64> s(n + 1);
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + a[i];
    }
    
    i64 ans = 1LL * n * (n + 1) / 2;
    std::vector<int> dp(n + 1,0);
    dp[n] = 1;
    for (int i = n - 1, j = n + 1; i >= 0; i--) {
        while (s[j - 1] - s[i] > x) {
            j--;
        }
        dp[i] = 1 + (j <= n ? dp[j] : 0);
        ans -= dp[i] - 1;
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

D

容易想到是并查集，合并的条件是\(|a_u-a_v|\%x=0\)，不难想到\(a_u=k_1x+b,a_v=k_2x+b\)，我们执行\(n\)次操作，对应就是\(x：1-n\)，我们可以通过枚举\(x\)，再枚举\(a_u\)进行合并，\(a_v\)怎么处理？不妨让\(a_v\)直接为\(a\%x\)，也就是\(b\)即可。通过一个数组先存起来，直到寻找到满足条件的即可。

关键的是\(x\)需要从\(n-1\)开始倒序枚举，这里是利用了抽屉原理，想一下：如果当前有\(x\)个点，然后所有数都取模于\(x-1\)，那么他们的范围一定是在\(0-(x-2)\)之间，说明一定会有两个点取模后存在相同的值，这样可以保证每一次操作都能连接两个不同的集合，故必定有解。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
void solve()
{
    int n;  cin>>n;
    std::vector<ll> a(n,0);
    for(auto &t: a) cin>>t;
    std::vector<int> fa(n,0);
    auto init=[&](int n)->void
    {
        for(int i=0;i<n;i++)    fa[i]=i;
    };
    auto find=[&](auto&& self,int x)->int 
    {
        if(fa[x]==x)    return x;
        return fa[x]=self(self,fa[x]);
    };

    auto merge=[&](int x,int y,auto&& find)->void
    {
        int fx=find(find,x),fy=find(find,y);
        if(fx!=fy)  fa[fx]=fy;
    };
    init(n);
    std::vector<int> u(n);
    std::vector<int> v(n);
    //|au-av|%x==0 说明两者都是kx+b 只是k不同而已
    //可以通过au%x得到b 并且找到av 满足kx+b
    for(int x=n-1;x>=1;x++)
    {
        std::vector<int> tmp(x,-1);//用来暂时存放b的数组，可以到时候用来寻找av
        for(int i=0;i<n;i++)
        {
            if(find(find,i)!=i) continue;   //说明已经找到了，合并在一起
            if(tmp[a[i]%x]!=-1)
            {
                u[x]=tmp[a[i]%x];
                v[x]=i;
                merge(u[x],v[x],find);
                break;
            }
            else    tmp[a[i]%x]=i;
        }
    }
    cout<<"YES\n";
    for(int i=1;i<n;i++)
    {
        cout<<u[i]+1<<" "<<v[i]+1<<"\n";
    }
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}