作为蒟蒟蒻，打的时候只会A题，为了补题加深印象来写题解了TAT

A.AquaMoon and Two Arrays

题意

给你a,b两个数组,还有一个操作：使a数组的第i个元素-1，第j个元素+1,(i!=j).
使得你能够在几次操作后使a数组和b数组完全相等

思路

因为操作特性，a数组减去的总数和加上的总数一定相等，如果不相等就输出-1
同时操作次数=减去的总数=加上的总数
然后模拟输出就好了

#include <bits/stdc++.h>

using namespace std;

const int N=110;
int t,n,a[N],b[N];

int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i]; 
        for(int i=1;i<=n;i++) cin>>b[i];
        int sum=0,cnt=0;
        for(int i=1;i<=n;i++)
        {
            sum+=b[i]-a[i];
            if(a[i]>b[i]) cnt+=a[i]-b[i];
        }
        if(sum!=0) cout<<-1<<endl;
        else
        {
            cout<<cnt<<endl;
            for(int k=1;k<=cnt;k++)
            {
                int x=0,y=0;
                for(int i=1;i<=n;i++)
                {
                    if(a[i]<b[i] && !y)
                    {
                        y=i;
                        a[i]++;
                    }
                    else if(a[i]>b[i] && !x)
                    {
                        x=i;
                        a[i]--;
                    }
                    if(x && y)
                    {
                        cout<<x<<' '<<y<<endl;
                        break;
                    }
                }
            }

        }
    }

    return 0;
}

B.AquaMoon and Stolen String

题意

给出n（n为奇数）个长度为m的串，然后将其中n-1个串两两配对，配对的串会随机交换相同位置的字符，给出配对完后被打乱顺序的n-1个串，要你找出是哪个串没有配对。

思路

由于不管怎么配对怎么变，每个字符交换后的下标都是不变的，只是变了所在的字符串。
所以用一个二维数组统计，a[i][j]表示字符i在位置j出现过几次。配对后再把出现的字符减去，最后二维数组里留下的那个字符就是未配对字符串的。

#include <bits/stdc++.h>

using namespace std;

int t,n,m,cnt[26];
string s[200010],s1;

int main()
{
    cin>>t;
    while(t--)
    {

        cin>>n>>m;
        for(int i=1;i<=n*2-1;i++)
            cin>>s[i];

        for(int j=0;j<m;j++)
        {
            memset(cnt,0,sizeof cnt);
            for(int i=1;i<=n;i++)
            {
                cnt[s[i][j]-'a']++;
            }

            for(int i=n+1;i<=n*2-1;i++)
            {
                cnt[s[i][j]-'a']--;
            }

            for(int i=0;i<26;i++)
            {
                if(cnt[i]) cout<<(char)(i+'a');
            }
        }
        cout<<endl;
    }
    return 0;
}

C. AquaMoon and Strange Sort

题意

    一个乱序数组，每个元素都有一个方向，初始都向右.
    相邻两个元素交换位置的同时方向也会变，要使数组升序排序并且方向都还是指向右。

思路

    首先得到结论：原先初始位置在奇数位置的数排序完后也在奇数位置，才能保证方向不变，偶数位置同理。 
    直接sort数组，然后判断能不能完成上述结论的排序。

    因为数组的值可以重复，sort之后可能同样的值的顺序不一定正确，
    本来的想法是直接for循环找到两两对应的错序同值元素然后交换位置，但被一个1e5个同值数组卡TLE了

    所以转换一下思路，先用map记下各个值的数量，原先在奇数位的数量，原先在偶数位的数量，然后遍历数组的每一个值，
    看看每一个值占的区间的奇数位个数和偶数位个数和原先的是否相等就好了

    计算区间奇数位和偶数位个数结论：
    （当最后一位是奇数位时，偶数位一共有 区间位数/2 个，奇数位减一减就好了） 
    （当最后一位是偶数位时，奇数位一共有 区间位数/2 个，偶数位减一减就好了）

#include <bits/stdc++.h>

using namespace std;

int t,n;
struct number
{
    int val,pos;
}num[100010];

bool cmp(number x,number y)
{
    return x.val<y.val;
}

int main()
{
    cin>>t;
    while(t--)
    {
        map<int,int> mp,mp1,mp2;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>num[i].val;
            num[i].pos=i;
            mp[num[i].val]++;
            if(i%2) mp1[num[i].val]++;
            else mp2[num[i].val]++;
        }

        sort(num+1,num+1+n,cmp);

        bool st=true;
        for(int i=1;i<=n;i++)
        {
            while(num[i].val==num[i-1].val) i++;
            if(i>n) break; 

            int sum=i+mp[num[i].val]-1;
            //cout<<"sum="<<sum<<endl;
            int ji=0,ou=0;
            if(sum%2)
            {
                ou=mp[num[i].val]/2;
                ji=mp[num[i].val]-ou;
            }
            else
            {
                ji=mp[num[i].val]/2;
                ou=mp[num[i].val]-ji;
            }
            //cout<<num[i].val<<"-->"<<' '<<ji<<' '<<ou<<endl;

            if(mp1[num[i].val]!=ji || mp2[num[i].val]!=ou)
            {
                st=false;
                break;
            }
        }

        if(st) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

D.AquaMoon and Chess

题意

一个1*n的棋盘，其中几个方格放了棋子视为1，其他为0，两个1相邻，其中一个1可以跳过1走到另一边0的位置，问有多少种棋盘状态。

思路

很容易（很难）想到只要有两个1相邻就能随便走，所以计算两个1相邻的有x组（连续1的个数/2的总和），多余的1走不动会一直保持这个状态，可以直接无视它。
在计数0的个数y，把这几组11视为都放在一个0的格子中，所以y再加1
因此问题就变成排列组合 把x组11放入y个0中，0中可无11的方法数量
用隔板法 即把x组11划分到y个区域中，需要y-1个隔板，隔板和11一起排列，总共有x+y-1个位置，要选y-1个位置放隔板，所以为C(x+y-1,y-1)
又因为组合数过大需要取模，需要用到乘法逆元处理结果（用拓展欧几里得算法求）。

乘法逆元

类似矩阵的逆，即在取模情况下 除以x，要乘以x的逆元，同时x*x的逆元=1（mod p）。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N=100010;
int t,n,a[N];
int mod=998244353;

void exgcd(LL a,LL b,LL& x,LL& y)
{
    if(b==0)
    {
        x=1,y=0;
        return;
    }

    LL x1,y1;
    exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
    return;
}

LL ni(LL a,LL b)
{
    LL x,y;
    exgcd(a,b,x,y);
    return (x%b+b)%b;
}

LL cal(LL n,LL m)
{
    LL t1=1,t2=1,t3=1;
    for(int i=2;i<=n;i++) t1=(t1*i)%mod;
    for(int i=2;i<=m;i++) t2=(t2*i)%mod;
    for(int i=2;i<=n-m;i++) t3=(t3*i)%mod;
    return ((t1*ni(t2,mod))%mod*ni(t3,mod))%mod;
}

int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        int x=0,y=0;
        string s;
        cin>>s;
        int ans=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='0')
            {
                y++;
                continue;
            }

            while(s[i]=='1')
            {
                ans++;
                i++;
            }
            i--;
            x+=ans/2;
            ans=0;
        }

        cout<<cal(x+y,y)<<endl; 
    }
}