The 19th Zhejiang Provincial Collegiate Programming Contest VP记录+补题

现在有两个数字$a$和$b$，你选择一个奇数$x$和偶数$y$，每次可以给$a$加$x$或减$y$，问最小操作次数$a$变为$b$。

分类讨论差值。

#include  #define int long long #define endl '\n' using namespace std;  inline void span class="token function">solve(){ 
        
    int a, b; cin >> a >> b;
    int det = abs(a - b);
    if(a == b) cout << 0 << endl;
    else if(a > b && (det & 1 == 0) || a < b && det & 1) cout << 1 << endl;
    else if(a < b && (det / 2) & 1 || a > b) cout << 2 << endl;
    else cout << 3 << endl;
}


signed main(){ 
        
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}

找到cjb然后加个逗号就可以了，样例2好评

#include 
#define int long long
#define endl '\n'
using namespace std;

inline void solve(){ 
        
    string str; cin >> str;
    for(int i = 0; i < str.size(); i++){ 
        
        if(i >= 2 && str[i] == 'b' && str[i - 1] == 'j' && str[i - 2] == 'c') cout << str[i] << ',';
        else cout << str[i];
    }
}

signed main(){ 
        
    solve();
    return 0;
}

直接按照题意模拟，统计两类数量即可。

#include 
#define int long long
#define endl '\n'
using namespace std;

inline void solve(){ 
        
    int n, m, X; cin >> n >> m >> X;
    int ans = 0;
    for(int i = 1; i <= n; i++){ 
        
        int s; cin >> s;
        if(s >= X) ans++;
    }
    for(int i = 1; i <= m; i++){ 
        
        int s; cin >> s;
        if(s <= X) ans++;
    }
    cout << ans << endl;
}

signed main(){ 
        
    ios_base::sync_with_stdio(false), cin.tie(0);
    solve();
    return 0;
}

主席树写挂了，赛时没调出来，我是菜狗

给定排列$p_1,p_2,p_3,\dots ,p_n$，定义$A_i$表示在$p_i$左侧并比$p_i$小的数字个数，$B_i$表示在$p_i$右侧并比$p_i$小的数字个数，$C_i=\min (A_i,B_i)$。现在给定多个操作$(l,r)$，求每个操作，交换$(p_i,p_j)$后的$\sum C_i$。

首先考虑如何处理初始时的$C_i$值，观察到以下性质：

• 对于$A_i$值的求解过程类似求逆序对的思想，可以直接上树状数组维护，$O(n\log n)$求得全部的$A_i$
• 由于是排列，$B_i=p_i-1-A_i$可以$O(1)$求得
• 那么$C_i=\min (A_i,B_i)$也是$O(1)$得到的

由于每个询问相互独立，那么考虑交换$(p_l,p_r)$操作对$C_i$的影响：