CF732

交互题到底是个啥啊

A

#include<iostream>
#include<vector>
using namespace std;

typedef pair<int, int> PII;
void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1), c(n + 1);
    vector<PII> ans;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> b[i];
    int sum = 0;
    for(int i = 1; i <= n; i ++){
        c[i] = a[i] - b[i];
        sum += c[i];
    }
    if(sum != 0) {cout << -1 << endl; return;}
    int cnt = 0;
    for(int i = 1; i <= n; i ++){
        if(c[i] < 0){
            for(int j = i + 1; j <= n; j ++){
                if(c[j] > 0){
                    while(c[i] != 0 && c[j] != 0){cnt ++, ans.push_back({j, i});c[j] --, c[i] ++;}
                    if(c[i] == 0) break;
                } 
            }
        }
        else if(c[i] > 0){
            for(int j = i + 1; j <= n; j ++){
                if(c[j] < 0){
                    while(c[i] != 0 && c[j] != 0) {cnt ++, ans.push_back({i, j});c[i] --, c[j] ++;}
                    if(c[i] == 0) break;
                } 
            }
        }
    }
    cout << cnt << endl;
    for(auto t : ans){
        cout << t.first << ' ' << t.second << endl;
    }

}

int main(){
    int T;
    cin >> T;
    while(T --){
        solve();
    }

    return 0;
}

C

思路

每个数从原始状态移到最终状态的 移动的步数一定为偶数。

则转化为
一个数在原始位置的奇数位置数 等于 最终状态的奇数位置数。
一个数在原始位置的偶数位置数 等于 最终状态的偶数位置数。

 #include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;
int a[N];
unordered_map<int, PII> Hash1;
unordered_map<int, PII> Hash2;

void solve(){
    int n;
    cin >> n;
    Hash2.clear(), Hash1.clear();
    for(int i = 0; i < n; i ++){
        cin >> a[i];
        if(i % 2) Hash1[a[i]].first ++;
        else Hash1[a[i]].second ++;
    }

    sort(a, a + n);

    for(int i = 0; i < n; i ++){
        if(i % 2) Hash2[a[i]].first ++;
        else Hash2[a[i]].second ++;
    }
    bool flag = true;
    for(auto t : Hash1){
        int num = t.first;
        if(Hash2[num].first != Hash1[num].first || Hash2[num].second != Hash1[num].second)
            {flag = false; break;}
    }
    if(flag) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T --){
        solve();
    }
}

D

思路

将连续的两个1的位置当成1个物品 和1个空位置 ，3个1只能算1个。
所有的0全部当成空位置
输出所有物品放入 空位置的方案数即可

#include<iostream>
#include<string>

using namespace std;

typedef long long LL;
const int N = 100010, mod = 998244353;

char str[N];
int fact[N], infact[N];

LL qmi(int a, int b, int mod){
    LL res = 1;
    while(b){
        if(b & 1) res = (LL) res * a % mod;
        a = (LL)a * a % mod;
        b >>= 1;
    }

    return res;
}

void init(){
    fact[0] = infact[0] = 1;
    for(int i = 1; i < N; i ++){
        fact[i] = (LL)i * fact[i - 1] % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

LL C(int a, int b){
    return (LL) fact[a] * infact[a - b] % mod * infact[b] % mod;
}

void solve(){
    int n;
    cin >> n;
    cin >> str;

    int one, zero;
    one = zero = 0;
    for(int i = 0; i < n; i ++){
        if(str[i] == '1' && str[i + 1] == '1') one ++, i ++;
        else if(str[i] == '0') zero ++;
    }

    cout << C(one + zero, one) << endl;

}

int main(){
    init();
    int T;
    cin >> T;
    while(T --){
        solve();
    }
}