查看源代码：
ABC396.md

---
title: 氵ABC396
createTime: 2025/3/15
categories:
    - IT
tags:
    - OI
---

## [ABC396A - Triple Four](https://atcoder.jp/contests/abc396/tasks/abc396_a)

```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=128;
int a[maxn];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    for (int i=1; i<=n; i++){
        cin >> a[i];
    }
    
    bool ans = false;
    for (int i=1; i<=n-2; i++){
        ans = ans || (a[i]==a[i+1] && a[i+1]==a[i+2]);
    }
    
    cout << (ans? "Yes": "No");
    
    return 0;
}
```

## [ABC396B - Card Pile](https://atcoder.jp/contests/abc396/tasks/abc396_b)

```cpp
#include <bits/stdc++.h>
using namespace std;


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    stack<int> sta;
    for (int i=1; i<=100; i++){
        sta.push(0);
    }
    
    int q;
    cin >> q;
    
    while (q--){
        int op;
        cin >> op;
        
        if (op == 1){
            int x;
            cin >> x;
            sta.push(x);
        } else {
            cout << sta.top() << '\n';
            sta.pop();
        }
    }
    
    return 0;
}
```

## [ABC396C - Buy Balls](https://atcoder.jp/contests/abc396/tasks/abc396_c)

没有代价，贪心即可。 
排序后只有三种选择：

1. 选 B 不选 W 
2. 都选
3. 都不选

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=2e5+10;
int b[maxn], w[maxn];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    for (int i=1; i<=n; i++){
        cin >> b[i];
    }
    
    for (int i=1; i<=m; i++){
        cin >> w[i];
    }
    
    sort(b+1, b+n+1, greater<int>());
    sort(w+1, w+m+1, greater<int>());
    
    int ans = 0;
    for (int i=1; i<=n&&i<=m; i++){
        ans += max(max(b[i], b[i]+w[i]), 0ll);
    }
    
    for (int i=m+1; i<=n; i++){
        ans += max(b[i], 0ll); 
    }
    
    cout << ans;
    
    return 0;
}
```

## [ABC396D - Minimum XOR Path](https://atcoder.jp/contests/abc396/tasks/abc396_d)

必须知道的是，$10! = 3628800$

因此 $O(n!)$ 是完全够的 

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=12;

struct edge{
    int v, w;
};

int n, m;
vector<edge> G[maxn];
bool vis[maxn];
int ans;

void dfs(int u, int xw){
    if (u == n){
        ans = min(ans, xw);
        return;
    }
    
    vis[u] = true;
    for (edge &e: G[u]){
        if (!vis[e.v]){
            dfs(e.v, xw^e.w);
        }
    }
    vis[u] = false;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    
    for (int i=1; i<=m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    
    ans = 0x3f3f3f3f3f3f3f3f;
    
    dfs(1, 0);
    
    cout << ans;
    
    return 0;
}
```

## [ABC396E - Min of Restricted Sum](https://atcoder.jp/contests/abc396/tasks/abc396_e)

对付异或，拆位处理？   
拆位后变为 2-SAT.  
需要找出和最小的解。  
每个联通块处理即可。  
具体处理方法：统计同于/异于联通块老大的数量，最小的为0即可  
时间复杂度 $n \alpha(n) \log{z}$  

**居然一次就把代码打对了，可喜可贺！！！**

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=2e5+10;
int n, m;
int x[maxn], y[maxn];
int z[maxn];
int bit[maxn]; 

struct Dsu{
    int fa[2*maxn], rk[2*maxn];
    
    void init(int siz){
        for (int i=1; i<=siz; i++){
            fa[i] = i;
            rk[i] = 0;
        }
    }
    
    void unify(int x, int y){
        int fx = find(x),
            fy = find(y);
        if (rk[fx] < rk[fy]){
            swap(fx, fy);
        }
        fa[fy] = fx;
        rk[fx]++;
    }
    
    int find(int x){
        if (fa[x] == x){
            return x;
        }
        return fa[x] = find(fa[x]);
    }
} dsu;

int samecnt[maxn], diffcnt[maxn];
int samebit[maxn], diffbit[maxn];
int ans[maxn];

inline int solvedigit(int shift){
    dsu.init(n*2+1);
    memset(samecnt, 0, sizeof samecnt);
    memset(diffcnt, 0, sizeof diffcnt);
    memset(samebit, 0, sizeof samebit);
    memset(diffbit, 0, sizeof diffbit);
    
    for (int i=1; i<=m; i++){
        dsu.unify(x[i]<<1, (y[i]<<1)^bit[i]);
        dsu.unify(x[i]<<1|1, (y[i]<<1|1)^bit[i]);
    }
    
    for (int i=1; i<=n; i++){
        if (dsu.find(i<<1) == dsu.find(i<<1|1)){
            return -1;
        }
        int f0 = dsu.find(i<<1);
        if (f0 & 1){
            diffcnt[f0>>1]++;
        } else {
            samecnt[f0>>1]++;
        }
    }
    
    int res = 0;
    for (int i=1; i<=n; i++){
        if (diffcnt[i] < samecnt[i]){
            diffbit[i] = 1;
            samebit[i] = 0;
        } else {
            diffbit[i] = 0;
            samebit[i] = 1;
        }
    }
    
    for (int i=1; i<=n; i++){
        int f0 = dsu.find(i<<1);
        if (f0 & 1){
            ans[i] |= diffbit[f0>>1] << shift;
        } else {
            ans[i] |= samebit[f0>>1] << shift;
        }
    }
    
    return 0;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i=1; i<=m; i++){
        cin >> x[i] >> y[i] >> z[i];
    }
    
    for (int i=0; i<=30; i++){
        for (int j=1; j<=m; j++){
            bit[j] = (z[j] >> i) & 1;
        }
        
        int res = solvedigit(i);
        
        if (res == -1){
            cout << "-1";
            return 0;
        }
    }
    
    for (int i=1; i<=n; i++){
        cout << ans[i] << ' ';
    }
    
    return 0;
}
```

## [ABC396F - Rotated Inversions](https://atcoder.jp/contests/abc396/tasks/abc396_f)

> 对于所有 k，求 $B_i=(A_i+k)%M$ 的逆序对数。  

`k++ 时`，相对位置改变的仅有 $M-1 \to 0$  
$I$ 处增加的逆序对数：$\sum\limits_{i<I}Bi<M-1$  
$I$ 处减少的逆序对数：$\sum\limits_{i>I}Bi<M-1$   
没什么用，只是好看的式子：  
$\sum\limits_{1\le i\le N}\operatorname{sgn}(I-i)[B_i<M-1]$   
对于一个 $i<M-1$，它的贡献是左右 $M-1$ 数之差。有用吗？!!（注：没用!!   
总之就是这样。  
不想写了（躺  

[1h 后] 现在写吧。  
其实可以直接对 $A_i=M-1$ 统计的。均摊很小。  
$O(n)$?   
加上求逆序对的是 $O(n\log n)$.  

感觉比 E 题简单。

```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;

#define int long long

int n, m;
int a[maxn];
int ans[maxn];
vector<int> vv[maxn];

struct Bit {
    int tree[maxn];
    
    inline int lowbit(int x){
        return x&-x;
    }
    
    void add(int i, int a){
        for (; i<=m; i+=lowbit(i)){
            tree[i] += a;
        }
    }
    
    int query(int i){
        int ans=0;
        for (; i>0; i-=lowbit(i)){
            ans += tree[i];
        }
        return ans;
    }
} bit;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    
    for (int i=1; i<=n; i++){
        cin >> a[i];
        vv[a[i]].push_back(i);
    }
    
    for (int i=n; i>=1; i--){
        ans[0] += bit.query(a[i]);
        bit.add(a[i]+1, 1);
    }
    
    for (int k=1; k<m; k++){
        ans[k] = ans[k-1];
        int jumpv = m-k;
        for (int i=0; i<vv[jumpv].size(); i++){
            int index = vv[jumpv][i];
//            printf("%d jumped\n", index);
            ans[k] += index-1 - i;
            ans[k] -= n-index - (vv[jumpv].size()-i-1);
//            printf("+%d -%d\n", index-1 - i, n-index - (vv[jumpv].size()-i));
        }
    }
    
    for (int i=0; i<m; i++){
        cout << ans[i] << '\n';
    }
    
    return 0;
}
```