Codeforces Round #732 (Div. 2)

A. AquaMoon and Two Arrays

把数组A中的每个元素改为，然后不断选小于0的和大于0的进行操作，由此可以知道才有解。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7,mod=998244353;
int a[105];
vector<pair<int,int> >v;
inline void solve() {
    int n,sum(0);
    v.clear();
    cin>>n;
    for(int i=1; i<=n; ++i) cin>>a[i];
    for(int i=1,x; i<=n; ++i) {
        cin>>x;
        a[i]=a[i]-x;
        sum+=a[i];
    }
    if(sum) return cout<<"-1\n",void();
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n&&a[i]; ++j) {
            while(a[j]>0&&a[i]<0) {
                a[i]+=1;
                a[j]-=1;
                v.emplace_back(make_pair(j,i));
            }
            while(a[j]<0&&a[i]>0) {
                a[i]-=1;
                a[j]+=1;
                v.emplace_back(make_pair(i,j));
            }
        }
    cout<<v.size()<<'\n';
    for(auto &i:v) 
        cout<<i.first<<' '<<i.second<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

B. AquaMoon and Stolen String

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
int a[maxn];
string s;
inline void solve() {
    int n,m;
    cin>>n>>m;
    memset(a,0,sizeof a);
    for(int i=1;i<=n;++i) {
        cin>>s;
        for(int j=0;j<m;++j) a[j]+=s[j]-'a';
    }
    for(int i=2;i<=n;++i) {
        cin>>s;
        for(int j=0;j<m;++j) a[j]-=s[j]-'a';
    }
    for(int i=0;i<m;++i) s[i]=a[i]+'a';
    cout<<s<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

C. AquaMoon and Strange Sort

如果需要只保证最后得到的数组是升序的，那么就是一个冒泡排序，每个元素需要交换的最小次数就是前面比它大的数的个数加上后面比它小的数的个数。有最小次数的原因是相等的数可以互相交换任意次而不改变。

先对原数组排序，记录每个数出现了几次交换次数为奇数次，如果出现了偶数次，那么还可以内部消化，反之不行。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
int tree[maxn],n,a[maxn],b[maxn],c[maxn][2];
bool f[maxn];
#define lowbit(x)    ((x)&-(x))
void add(int x) {
    while(x<maxn) {
        tree[x]+=1;
        x+=lowbit(x);
    }
}
int sum(int x) {
    int sum=0;
    while(x) {
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}
inline void solve() {
    memset(tree,0,sizeof tree);
    cin>>n;
    for(int i=1; i<=n; ++i) {
        cin>>a[i];
        b[i]=sum(maxn-1)-sum(a[i]);
        add(a[i]);
        c[a[i]][0]=c[a[i]][1]=0;
    }
    memset(tree,0,sizeof tree);
    for(int i=n; i; --i) {
        b[i]+=sum(a[i]-1);
        add(a[i]);
        if(b[i]&1) c[a[i]][i&1]+=1;
    }
    for(int i=1; i<=n; ++i) if(c[a[i]][0]!=c[a[i]][1]) {
            cout<<"NO\n";
            return;
    }
    cout<<"YES\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

D. AquaMoon and Chess

每次操作都要移动相邻的1，所以把相邻的1绑在一起。
假设没有单独的1，统计有m对1，那么相当于有n-m个格子，每个格子填一对1，答案就是
如果有单独的1，假设有一对1从这个单独的1左边移过来，比如:"0110100-->0011100-->0010110"，其实就是把这个单独的1往左移了两格。把这个单独的1去掉试试，可以发现没有影响。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7,mod=998244353;
ll inv[maxn],f[maxn],n,jc[maxn];
string s;
inline void init() {
    jc[0]=f[0]=jc[1]=f[1]=inv[1]=1;
    for(int i=2;i<maxn;++i) {
        inv[i]=inv[mod%i]*(mod-mod/i)%mod;
        jc[i]=jc[i-1]*i%mod;
        f[i]=f[i-1]*inv[i]%mod;
    }
}
inline void solve() {
    cin>>n>>s;
    s=" "+s;
    ll x(0),y(0);
    for(int i=1;i<n;++i) {
        if(s[i]=='1'&&s[i+1]=='1') {
            x+=1; i+=1;
        }
        else if(s[i]=='0')y+=1;
    }
    if(s[n]=='0') y+=1;
    cout<<jc[x+y]*f[x]%mod*f[y]%mod<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    init();
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}