Atcoder ABC 396

compaq · 2025-03-10 18:17:33 · 算法·理论

E - Min of Restricted Sum

对于每一组 X_i、Y_i、Z_i，我们建立一条以 X_i 到 Y_i 权值为 Z_i 的双向边。这样可以把条件抽象成一张图，且这张图不一定是联通的，可能会被分为若干个块。

对于每一个块，任选一个点当做起点跑一遍dfs，假设我们确定了这个起点的值，通过边(异或关系)进行传递，这个连通块所有的值都可以确定。

如果某个点被遍历过，且第二次（或更多次)到达该点的异或值，与之前保存的结果不一致，则意味着这个点不能确定，可以直接判定无解的情况。

接下来需要处理\sum a_i的最小值。

每个连通块都是独立的，那么只需要每个连通块的和最小。

在计算某连通块时，每次出发点的值初始值都是0,此时会得到同个连通块剩余点i的值a[i],由于异或计算每一位都是独立的，则我们统计同个连通块内每个数，在二进制下同一位的1的个数，若1的数量超过一半，则这位上的0和1进行翻转。

其他连通块同样处理即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
int n,m,ans[N],vis[N],f,t,w;
vector<pair<int,int> > v[N];
vector<int> q;

void dfs(int x, int sum){
    if(vis[x]) {
        if(ans[x] != sum){ 
            cout << -1; 
            exit(0); 
        } 
        return; 
    }
    vis[x] = 1; ans[x] = sum; q.push_back(x);
    for(int i = 0; i < v[x].size(); i ++){
        int y = v[x][i].first;
        int w = v[x][i].second;
        dfs(y,sum ^ w);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1;i <= m; i ++){ 
        cin >> f >> t >> w;
        v[f].push_back({t, w});
        v[t].push_back({f, w});
    }
    for(int i = 1; i <= n; i ++){
        if(vis[i]) continue;
        dfs(i, 0); // 假设起点为0        
        for(int j = 0; j < 30; j ++){
            int cnt = 0;
            for(int i = 0; i < q.size(); i ++){
                int y = q[i];
                if(ans[y] & (1 << j)) cnt ++;
            }
            // 如果起点第j位取0时的1超过半数，翻转连通块所有j位 
            if(cnt + cnt > q.size()){
                for(int i = 0; i < q.size(); i ++){
                    int y = q[i];
                    ans[y] ^= (1 << j);
                }
            }
        }
        q.clear();
    }
    for(int i = 1;i <= n;i ++) cout << ans[i] << " ";
  return 0;
}

/*
5 4
4 2 6
2 3 10
4 5 0
3 1 9
*/

F - Rotated Inversions

• 当k = 0, 答案就是原数组的逆序对的数量

• 当k = 1时,可以发现影响逆序对的只有 a_i \% m = m−1的值。因为此时(a_i + 1) \% = 0,相当于a_i从最大值变成了最小值，对逆序对的贡献会造成改变。

• 而除了 a_i \% m = m−1的位置，任意两个位置的大小关系都不会变，不会对逆序对造成影响。

• 假设满足 a_i \% m = m−1的位置分别是v = [v_1, v_2, v_3...v_k]，那么对于v_i分析，发现：

• 为了方便计算，我们不枚举下标，而是枚举数值从i = m-1开始计算，即先处理m-1，再处理m-2,m-3...

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int tr[N], a[N];
int n, m;
vector<int>g[N];
vector<pair<int, int> >vec;

int lowbit(int x){
    return x & -x;
}

void update(int x){
    while(x < N){
        tr[x] += 1;
        x += lowbit(x); 
    }
}

int query(int x){
    long long s = 0;
    while(x){
        s += 1ll * tr[x];
        x -= lowbit(x);
    }
    return s;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        vec.push_back({a[i], i});
        g[a[i]].push_back(i);
    }

    sort(vec.begin(), vec.end(), greater<pair<int, int>>() );   
    long long ans = 0;
    for(auto t : vec){
        ans += query(t.second);
        update(t.second); 
    }
    cout << ans << endl; // 原逆序对数量 

    for(int i = m - 1; i >= 1; i--){
        for(int j = 0; j < g[i].size(); j++){
            ans += 1ll * (g[i][j] - j - 1);
            ans -= 1ll * ((n - g[i][j]) - (g[i].size() - j - 1));
        }
        cout << ans << '\n';
    }
    return 0;
}