Phantom Bird

外观

CF2131

约 1726 字大约 6 分钟

OI

2025-8-18

CF2131A. Lever

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

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n, ans=1;
        cin >> n;
        
        for (int i=1; i<=n; i++) {
            cin >> a[i];
        }
        
        for (int i=1; i<=n; i++) {
            int b;
            cin >> b;
            ans += max(a[i]-b, 0);
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}

CF2131B. Alternating Series

安排字典序最小就是奔着目光短浅去的。
于是负值贪心地取 −1-1，但是正值由于抽子序列的最坏情况是 −1 a −1-1 \ a \ -1，所以非尾部的 aa 必须为 33。

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        for (int i=1; i<=n; i++) {
            cout << ((i&1)? -1: 3-(i==n)) << ' '; 
        }
        cout << '\n';
    }
    
    return 0;
}

CF2131C. Make it Equal

一次操作改变的数的空间是有限的，
且这个数可以到达所在空间中的所有点。

于是考虑把空间内的所有数视为等价，
然后比较两个多重集即可。

最后，这个空间是什么？
是 (±x) mod k(\pm x) \bmod k。

因此，一个数所在的空间序号可以表示成 space⁡(x)=min⁡(x mod k,(−x) mod k)\operatorname{space}(x) = \min(x \bmod k, (-x) \bmod k)

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

int n, k;
map<int, int> S, T; 

inline int space(int a) {
//  printf("space(%d) = %d\n", a, min(a%k, k-a%k));
    return min(a%k, k-a%k);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        S.clear();
        T.clear();
        // 多测不清空，赛后两行泪 
        
        cin >> n >> k;
        
        for (int i=1; i<=n; i++) {
            int x;
            cin >> x;
            S[space(x)]++;
        }
        
        bool ans = true;
        for (int i=1; i<=n; i++) {
            int x;
            cin >> x;
            int sx = space(x);
            
            T[sx]++;
            if (T[sx] > S[sx]) { 
                ans = false;
                // 要输入完，不能 break 
            }
        }
        
        cout << (ans? "YES\n" : "NO\n");
    }
    
    return 0;
}

CF2131D. Arboris Contractio

一棵树直径最小的形态是菊花图。

设它的花蕊为 rr，
设原树的非花叶节点数 cc 为不与花蕊直接相连且不为花蕊的叶节点数。

引理

将一张图收缩为花蕊为 rr 的菊花图至少需要 cc 次操作。

证明 对于一次操作，非花叶节点的个数最多减少 11。

  • 对于仅经过一个非花叶节点的路径
    显然。
  • 对于经过两个非花叶节点的路径 一个非花叶节点会连到另一个非花叶节点上，仍为非花叶节点。

引理

将一张图收缩为花蕊为 rr 的菊花图只需 cc 次操作。

证明 对于每一个非花叶节点，做一次 r 到这个节点的操作即可。
由于每个节点至少是一个叶节点自身或祖先，它总能被做一次操作，然后直接连到 rr 上。

因此，ans=#leaf−max⁡r(#{(leaf,r)∈E}+[r∈leaf])\mathrm{ans} = \#\mathrm{leaf} - \displaystyle\max_r\bigl( \#\{(\mathrm{leaf}, r) \in E\} + [r \in \mathrm{leaf}] \bigr)。

如何统计？每个叶节点向自己以及它所连的节点打一个标记。
时间复杂度 O(n)O(n)。

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

const int maxn=2e5+100;
vector<int> G[maxn];
int leaves;
int sub[maxn];

inline void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        leaves = 0;
        for (int i=1; i<=n; i++) {
            sub[i] = 0;
            G[i].clear();
        }
        
        for (int i=1; i<=n-1; i++) {
            int u, v;
            cin >> u >> v;
            add_edge(u, v);
        }
        
        for (int i=1; i<=n; i++) {
            if (G[i].size() == 1) {
                leaves++;
                sub[G[i][0]]++;
                sub[i]++;
            }
        }
        
        int msub=0;
        for (int i=1; i<=n; i++) {
            msub = max(msub, sub[i]);
        }
        
        cout << leaves - msub << '\n';
    }
    
    return 0;
}

CF2131E. Adjacent XOR

由于每个数最多操作一次，可以知道：

若能够变换，每个数异或的不是 ai+1a_{i+1}（下一个数操作前）就是 bi+1b_{i+1}（下一个数操作后，或者下一个数不操作）
（也可以不异或）

直接模拟即可。

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

const int maxn=2e5+100;
int a[maxn], b[maxn];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        a[n+1] = b[n+1] = 0;  // 多测___，_____ 
        
        for (int i=1; i<=n; i++) {
            cin >> a[i];
        }
        
        for (int i=1; i<=n; i++) {
            cin >> b[i];
        }
        
        bool ans = true;
        for (int i=1; i<=n; i++) {
            ans &= a[i] == b[i]
                    || ((a[i]^a[i+1])==b[i]) 
                    || ((a[i]^b[i+1])==b[i]);
        }
        
        cout << (ans? "YES\n" : "NO\n");
    }
    
    return 0;
}

CF2131F. Unjust Binary Life

注意到

A=x⊕yB=x⊕wC=z⊕yD=z⊕w\begin{matrix} A=x \oplus y & B=x \oplus w \\ C=z \oplus y & D=z \oplus w \end{matrix}

满足 A⊕B⊕C⊕D=0A \oplus B \oplus C \oplus D = 0，如果其中三个为 00，那么剩下一个也一定为 00。

因此如果存在一条全 00 的路径，它的最小矩形包围盒一定全为 00。

因此 f(x,y)f(x, y) 即为将任意的 i≤x,j≤yi \le x, j \le y 的 ai⊕bja_i \oplus b_j 变为 00 的最小操作数。
等价地，此时 a1,…,ax,b1,…,bya_1, \dots, a_x, b_1, \dots, b_y 都相同。此时最少的操作次数为其中 0/10/1 最少的一个的个数。

根据 min⁡⟷∣⋅∣\min \longleftrightarrow |\cdot| 互化公式

min⁡{x,y}=x+y2−∣x−y2∣\min\{x,y\} = \dfrac{x+y}{2} - \left| \dfrac{x-y}{2} \right|

有

∑x=1n∑y=1nf(x,y)=∑x=1n∑y=1nmin⁡{(∑i=1xai)+(∑i=1ybi),x+y−((∑i=1xai)+(∑i=1ybi))}=前缀和预处理∑x=1n∑y=1nmin⁡{Ax+By,x+y−Ax−By}=最小值-绝对值互化∑x=1n∑y=1n12[x+y−∣2Ax−x+2By−y∣]=分离变量, 换元∑x=1n∑y=1n12[x+y−∣Cx−Dy∣]=提取12[∑x=1n∑y=1nx+∑x=1n∑y=1ny−∑x=1n∑y=1n∣Cx−Dy∣]=n2(n+1)2−12∑x=1n∑y=1n∣Cx−Dy∣=对 Cx,Dy 排序预处理n2(n+1)2−12∑x=1n(∑y=1y0(x)Cx′−Dy′)+(∑y=y0(x)+1nDy′−Cx′)其中 y0(x)=max⁡({0}∪{y∣Cx′≥Dy′})=n2(n+1)2−12∑x=1nCx′(2y0(x)−n)−(∑y=1y0Dy′)+(∑y=y0+1nDy′)=前缀和预处理n2(n+1)2−12∑x=1nCx′(2y0(x)−n)+En−2Ey0(x)\begin{aligned} & \sum_{x=1}^{n} \sum_{y=1}^{n} f(x, y)\\ =&\sum_{x=1}^{n} \sum_{y=1}^{n} \min\left\{ \left(\sum_{i=1}^{x} a_i\right) + \left(\sum_{i=1}^{y} b_i\right), x+y - \left( \left(\sum_{i=1}^{x} a_i\right) + \left(\sum_{i=1}^{y} b_i\right) \right) \right\} \\ \xlongequal[\text{前缀和}]{\text{预处理}}& \sum_{x=1}^{n} \sum_{y=1}^{n} \min\left\{ A_x+B_y, x+y-A_x-B_y \right\} \\ \xlongequal{\text{最小值-绝对值互化}}& \sum_{x=1}^{n} \sum_{y=1}^{n} \dfrac{1}{2}\left[ x+y - |2A_x-x + 2B_y-y| \right] \\ \xlongequal{\text{分离变量, 换元}}& \sum_{x=1}^{n} \sum_{y=1}^{n} \dfrac{1}{2}\left[ x+y - |C_x - D_y| \right] \\ \xlongequal{\text{提取}}& \frac{1}{2} \left[\sum_{x=1}^{n} \sum_{y=1}^{n} x + \sum_{x=1}^{n} \sum_{y=1}^{n} y - \sum_{x=1}^{n} \sum_{y=1}^{n} |C_x - D_y| \right]\\ =& \dfrac{n^2 (n+1)}{2} - \frac{1}{2} \sum_{x=1}^{n} \sum_{y=1}^{n} |C_x-D_y|\\ \xlongequal[\text{对 } C_x,D_y \text{ 排序}]{\text{预处理}}& \dfrac{n^2 (n+1)}{2} - \frac{1}{2} \sum_{x=1}^{n} \left(\sum_{y=1}^{y_0(x)} C'_x-D'_y\right) + \left(\sum_{y=y_0(x)+1}^{n} D'_y-C'_x\right) \\ &\text{其中 } y_0(x) = \max \bigl( \{0\} \cup \{y \mid C'_x \ge D'_y\} \bigr)\\ =& \dfrac{n^2 (n+1)}{2} - \frac{1}{2} \sum_{x=1}^{n} C'_x \bigl(2y_0(x)-n\bigr) - \left(\sum_{y=1}^{y_0} D'_y\right) + \left(\sum_{y=y_0+1}^{n} D'_y\right) \\ \xlongequal[\text{前缀和}]{\text{预处理}} &\dfrac{n^2 (n+1)}{2} - \frac{1}{2} \sum_{x=1}^{n} C'_x \bigl(2y_0(x)-n\bigr) + E_n - 2E_{y_0(x)} \end{aligned}

其中 y0(x)y_0(x) 可以用二分查找或双指针算出，时间复杂度瓶颈在排序，O(nlog⁡n)O(n \log n)。

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

#define int long long

const int maxn=2e5+100;
int A[maxn], B[maxn], C[maxn], D[maxn], E[maxn];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        
        A[0] = B[0] = E[0] = 0;
        
        for (int i=1; i<=n; i++) {
            char a;
            cin >> a;
            A[i] = A[i-1] + a - '0';
            C[i] = 2 * A[i] - i;
        }
        
        for (int i=1; i<=n; i++) {
            char b;
            cin >> b;
            B[i] = B[i-1] + b - '0';
            D[i] = i - 2 * B[i];
        }
        
        sort(C+1, C+n+1);
        sort(D+1, D+n+1);
        
        for (int i=1; i<=n; i++) {
            E[i] = E[i-1] + D[i];
        }
        
        int x, y=0, sum=0;
        for (x=1; x<=n; x++) {
            while (y<n && C[x]>=D[y+1]) {
                y++;
            }
            
            sum += C[x] * (2*y - n) + E[n] - 2*E[y];
        }
        
        cout << (n*n*(n+1) - sum) / 2 << '\n';
    }
    
    return 0;
}