写在前面
长是绵长的长，春是春天的春
做绿皮长途跋涉 $20$ 多个小时，跨越大半个中国，从南昌 $\to$ 长春，走的最远的一集
第一次出省比赛，巨大的长理（门口还有长理桥，你财什么时候跟进一下），长春的轻轨（和地铁傻傻分不清，打车去坐轻轨哈哈哈），菜量巨大的东北菜，也是吃上锅包肉和雪绵豆沙了
拿到的第一块牌子
和我超强的队友们
还有和我们一起长途跋涉的骆老师
最惊险的一集，还好最后把 $H$ 开了
[补题链接][https://codeforces.com/gym/105924]

# G

# 题目大意

给定一张 $n$ 个点 $m$ 条边的无向图，可能存在重边或自环
问：最少添加多少条边可以使得所有点的度数都为偶数，允许重边、自环

# 数据范围

$1 \le n, m \le 10^5$

# 题解

签到题，输入完之后，把入度是奇数的点存入一个 $vector$ 里（假计为 $poi$ ），需要添加的边就是 poi.size() / 2 条，然后两个两个输出就行

C++

void solve () {
    cin >> n >> m;
    vector<int> d(n + 1);
    vector<int> poi;

    for (int i = 1, u, v; i <= m; i++)
        cin >> u >> v, d[u]++, d[v]++;

    for (int i = 1; i <= n; i++)
        if (d[i] & 1)
            poi.push_back(i);

    cout << poi.size() / 2 << '\n';
    for (int i = 0; i < poi.size(); i += 2)
        cout << poi[i] << " " << poi[i + 1] << '\n';
}

# I

# 题目大意

有一个城市，房子分布在道路两边，编号分别为 $1 \to n$ 和 $n + 1 \to 2n$ ，同一排房子之间没有路可以走，不同排城市间各自都建设了道路
由于一些原因，两排城市有部分城市两两犯冲，那么在走路的时候，路径上则不能有两个互相犯冲的房子
对于 $1 \to n$ 房子，第 $i$ 个房子和 $a_i~(n+1 \le a_i \le 2n)$ 房子犯冲（ $a_i$ 互不相同）
现在有 $q$ 个询问，请问城市 $s$ 是否能到城市 $t$

# 数据范围

$1 \le n \le 2 \times 10^5$
$1 \le s ,t \le 2n$

# 题解

在一个奇怪的地方 $wa$ 了好几发
对题目进行分类讨论有（ $s \le t$ 是前提）：

s == t 时，出发房子和目的房子相同，显然可以到达，没考虑这个 $WA$ 了好几发
$s$ $s$ 和 $t$ $t$ 在同侧时
- $n == 2$ 时，由于 $a_i$ 互不相同，找不到可以满足的路径
- $n \ge 3$ 时，除了两个相冲的房子，必然有第三个中转房子可以走
$s$ $s$ 和 $t$ $t$ 在异侧时
- 只要 $a[s] != t$ 二者不犯冲，那就能走

C++

void solve () {
    cin >> n >> s >> t;
    vector<int> a(2 * n + 10);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    if (s == t) {
        cout << "Yes\n";
        return;
    }

    if (s > t)
        swap(s, t);

    if (n == 1)
        cout << "No\n";
    else {
        if ((s <= n && t <= n) || (s > n && t > n))
            cout << ((n != 2) ? "Yes" : "No") << '\n';
        else
            cout << ((a[s] != t) ? "Yes" : "No") << '\n';
    }
}

只要题目没有明确说，给定的两个点 $s$ 和 $t$ 不能是同一个点，那就要把 $s==t$ 这种情况考虑进去，就算是题目这种，出发点和抵达点的问题，不过要是没想好，不如全部考虑，考虑了相等的情况也没损失

# F

# 题目大意

穿梭时间的画面的钟，从反方向开始转动 T-T

有一对情侣在某一天的 $x_1$ 时 $y1$ 分 $\to$ $x_2$ 时 $y_2$ 分的时间区段约会
现在他们位于 $x_0$ 时 $y_0$ 分，~~也许是真挚的感情感动了上帝吧~~，他们可以独立地拨动时钟和分钟，请你计算一个 $X$ 时 $Y$ 分，要求

$(X, Y)$ 位于他们约会的时间段之间
如果有多个这样的 $(X,Y)$ ，则选择调整代价最小的
如果有多个代价最小的，则好心的你应该找出那个能让他们约会最久的
- 调整代价为时钟、分钟转动的角度和

# 数据范围

$1 \le T \le 10^4$
$0 \le x_i \le 11$
$0 \le y_i \le 59$

# 题解

这题不妨考虑，枚举所有时间组合 $24h \times 60mins$ ，对于每一个 $(h,m)$

check 一下是否在 $(x_1, y_1) \to (x_2, y_2)$ 之内
计算 $(x_0, y_0) \to (h,m)$ 的代价

需要注意的是，如果 $y_0,m$ 不为 $0$ 的话，那么 $x_0,h$ 指向的不是正点，要有一定的偏移，可以通过算角度 + 翻倍来实现整数运算

C++

int x[3], y[3];

bool check(int h, int m) {
    if (h == x[1] && h == x[2])
        return (m >= y[1] && m <= y[2]);
    else if (h == x[1])
        return m >= y[1];
    else if (h == x[2])
        return m <= y[2];
    return true;
}

// 计算小时，传入的是 12，一小时 30 度
// 计算分钟，传入的是 60， 一分钟 6 度
int cal(int a, int b, int c) {
    if (a > b)
        swap(a, b);

    return min(b - a, c - b + a) * (360 / c);
}

void solve () {
    for (int i = 0; i < 3; i++)
        cin >> x[i] >> y[i];

    int resX = 0, resY = 0, cost = 1e18;

    for (int h = x[1]; h <= x[2]; h++)
        for (int m = 0; m <= 59; m++)
            if (check(h, m)) {
                int t = cal(m, y[0], 60) * 2;

                int h1 = h * 60 + m;
                int h2 = x[0] * 60 + y[0];

                if (h1 > h2)    swap(h1, h2);

                t += min(h2 - h1, 720 - h2 + h1);

                if (t < cost)
                    resX = h, resY = m, cost = t;
            }

    cout << resX << " " << resY << '\n';
}

# K

# 题目大意

有一种游戏，游戏中包含由 $m$ 种颜色，每种颜色 $n$ 个方块构成的 $n \times m$ 的矩阵， $c_{i,j}$ 表示矩阵中第 $i$ 行第 $j$ 列的方块颜色
在矩阵之外，有一个初始没有颜色的方块 $d$ ，你可以执行下面的操作：

选择一列，将额外的方块从最上方塞入，这一列被挤出来的方块成为新的额外方块

此外，游戏还提供了 $m$ 个染色道具，每个道具可以将当前的额外方块变成任意颜色，除了无色，游戏最终获胜的条件是，每一列颜色相同，且所有列颜色互不相同，问至少需要多少次操作

# 数据范围

$1 \le n, m \le 2 \times 10^3$
$\forall k \in [1,m], \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[c_{i,j}=k]=n$ ，也就是说，原先 $n \times m$ 的矩阵中，如果进行重排，是可以直接排成满足题目要求的矩阵的

# 题解

对于每一列，用每一列最顶部的颜色作为最终颜色，那么当前这一列的代价便是 $n - len_i$ ， $len_i$ 代表最顶部颜色往下的连续相同颜色的个数，维护 $maxLen_1 \to maxLen_m$ ，计算完每一列后，扫一遍 $1 \to m$ ，计算

$\sum\limits_{i=1}^{m}(n-maxLen_i)$

即为最终答案

C++

void solve () {
    cin >> n >> m;
    vector<vector<int>> a(n + 2, vector<int>(m + 2, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    vector<int> maxLen(m + 1, 0);

    for (int j = 1; j <= m; j++) {
        int num = a[1][j], i = 1;
        // 要么 i = n + 1 要么 a[i][j] != num 终止循环
        while (i <= n && a[i][j] == num)
            i++;
        maxLen[num] = max(maxLen[num], i - 1);
    }

    int res = 0;

    for (int j = 1; j <= m; j++)
        res += n - maxLen[j];

    cout << res << '\n';
}

# H

# 题目大意

还是那个城市，有两排房子，一排 $n$ 个。现在小 $A$ 打算舍弃掉第二排房子，在舍弃之后，有 $n$ 组居民需要安置（标号为 $1 \to n$ ），第 $i$ 组居民有 $b_i$ 人，他们和 $a_i$ 号城市相冲（ $\forall i,j \in [1, n],i \neq j, a_i \neq a_j$ ）
居民们可以被安置到任意不相冲的房子去，但是如果一个房子人太多，原住民就会不满意
第 $i$ 个房子有一个不满意指数 $c_i$ ，如果最后迁入了 $d_i$ 人，那么 $i$ 号城市的不满意度就是 $c_i \times d_i$
请你设计一个迁入方案，使得 $\max_{i=1}^{n} f(i)$ 最小

# 数据范围

$1 \le T \le 10^5$
$1 \le n \le 2 \times 10^5$
$1 \le b_i,c_i \le 10^6$

# 题解

当求最大值的最小值的时候，可以考虑二分答案
通过二分答案 $t$ ，那么每次计算 $sum = \sum\limits_{i=1}^{n}(x / c_i)$

如果 $sum$ 比 $\sum\limits_{i=1}^{n}b_i$ 小的话，显然不行
然后考虑犯冲的情况，枚举 $i = 1 \to n$ $i = 1 \to n$
- 对于每一个 $b_i$ ，如果 $b_i > sum - d_{a_i}$ 的话，代表把犯冲的去掉后， $b_i$ 人放不下了，那显然也不行

C++

int n, sumB = 0;
vector<int> a(N + 1), b(N + 1), c(N + 1);

bool check(int x) {
    vector<int> d(n + 1);
    int sum = 0;
    for (int i = 1; i <= n; i++)
        d[i] = x / c[i], sum += d[i];
    
    if (sum < sumB)
        return false;
    
    for (int i = 1; i <= n; i++)
        // 如果把所有冲突的都去掉了，还是放不下 b_i，那就返回 false
        if (b[i] > sum - d[a[i]])
            return false;

    return true;
}

void solve () {
    cin >> n, sumB = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i], sumB += b[i];
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    
    int l = 0, r = 1e18;

    while (l < r) {
        int mid = l + r >> 1;

        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }

    cout << l << '\n';
}

以上五题是赛时开的题目，下面是赛后补的题

# A

# 题目大意

题目意思很简单，对于 $A=(a_1,...,a_n)$ ，计算满足

$gcd(a_l, ..., a_r) = min(a_l, ..., a_r)$

的 $(l, r)$ 对总数

# 数据范围

$1 \le n \le 10^5$
$1 \le a_i \le 10^6$

# 题解

# 单调栈写法

对于每一个数的，我们不妨视它为最小的那个数，那我们可以维护两个数组

l[i] ：表示第 $i$ 个位置左边第一个不合法的位置
r[i] ：表示第 $i$ 个位置右边第一个不合法的位置

那么我们的答案只需要扫一遍 $1 \to n$ ，然后计算 $\sum\limits_{i=1}^{n}[(i - l_i) \times (r_i - i)]$

那么如何维护单调栈呢？（此处用双端队列实现）

第一次扫描，从 $i=1$ $i = 1$ 到 $i=n$ $i = n$
- while 单调栈空或者当前遍历到的值 % 队列尾端值！= 0 或者当前遍历到的值 == 队列尾端值
  - 令 r[队列尾端值] = i ，然后把尾端值 $pop$ 掉
第二次扫描，从 $i = n$ $i = n$ 到 $i = 1$ $i = 1$
- while 单调栈空或者 当前遍历到的值 % 队列尾端值 !=0
  - 令 l[队列尾端值] = i ，然后把尾端值 $pop$ 掉
  - 注意，第二次扫的时候，不考虑相等的情况，这样才不会漏掉考虑情况
    两次扫描后，都需要做一次
    C++
    1
    2
    while (!q.empty())
    l / r[q.back()] = 0 / n + 1, q.pop_back();
    从而确保所有元素的 $l,r$ $l, r$ 数组都能被正确计算

C++

void solve () {
    cin >> n;
    vector<int> l(n + 1), r(n + 1), a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    deque<int> q;

    for (int i = 1; i <= n; i++) {
        int x = a[i];

        while (!q.empty() && (x % a[q.back()] != 0 || x == a[q.back()]))
            r[q.back()] = i, q.pop_back();

        q.push_back(i);
    }

    while (q.size())
        r[q.back()] = n + 1, q.pop_back();

    for (int i = n; i >= 1; i--) {
        int x = a[i];

        while (!q.empty() && (x % a[q.back()] != 0))
            l[q.back()] = i, q.pop_back();

        q.push_back(i);
    }

    while (q.size())
        l[q.back()] = 0, q.pop_back();

    int res = 0;
    for (int i = 1; i <= n; i++)
        res += (i - l[i]) * (r[i] - i);

    cout << res << endl;
}

# 二分 + ST 表写法

与单调栈思路类似，都是对于每个点 $i$ ，找左右第一个合法 / 不合法的位置

左边界 $L$ $L$ ，需要满足
- min(a[L, ..., i - 1] > a[i]
- gcd(a[L, ..., i] == a[i]
右边界 $R$ $R$ ，需要满足
- min(a[i + 1, ..., R) >= a[i]
- gcd(a[i, ..., R) == a[i]

利用二分实现，为什么可以用二分？

对于 $min$ $m i n$ 有
- 对于一个数列，数越少， $min$ 难说，但是必须满足 getMin <= a[idx] ，所以这是一个与二分无关的条件

对于

gcd

有

对于一个数列，数越少，

gcd

不严格单增，能够二分

C++

int n;

vector<int> lg2(N + 1);
vector<vector<int>> stMin(N, vector<int>(20)), stGcd(N, vector<int>(20));
vector<int> a(N);

void init() {
    for (int i = 1; i < N; i++)
        lg2[i] = log2(i);
    
    for (int i = 1; i <= n; i++)
        stMin[i][0] = stGcd[i][0] = a[i];
    
    for (int i = 1; i < 20; i++) {
        int len = (1 << i);

        for (int j = 1; j + len - 1 <= n; j++) {
            stMin[j][i] = min(stMin[j][i - 1], stMin[j + len / 2][i - 1]);
            stGcd[j][i] = __gcd(stGcd[j][i - 1], stGcd[j + len / 2][i - 1]);
        }
    }
}

int getGcd(int l, int r) {
    int len = r - l + 1, t = lg2[len];
    return __gcd(stGcd[l][t], stGcd[r - (1 << t) + 1][t]);
}

int getMin(int l, int r) {
    int len = r - l + 1, t = lg2[len];
    return min(stMin[l][t], stMin[r - (1 << t) + 1][t]);
}

bool check1(int x, int idx) {
    if (getMin(x, idx - 1) <= a[idx])
        return false;
    if (getGcd(x, idx) != a[idx])
        return false;

    return true;
}

bool check2(int idx, int x) {
    if (getMin(idx + 1, x) < a[idx])
        return false;
    if (getGcd(idx, x) != a[idx])
        return false;

    return true;
}

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    init();

    int res = 0;
    
    for (int i = 1; i <= n; i++) {
        int L, R, l = 1, r = i - 1;

        while (l <= r) {
            int mid = l + r >> 1;
            if (check1(mid, i))
                r = mid - 1;
            else
                l = mid + 1;
        }

        L = l, l = i + 1, r = n;

        while (l <= r) {
            int mid = l + r >> 1;
            if (check2(i, mid))
                l = mid + 1;
            else
                r = mid - 1;
        }

        R = r;
        
        res += (i - L + 1) * (R - i + 1);
    }

    cout << res << '\n';
}

# L

大模拟，不想写，赛时感觉榜有点歪，可能别的队也不想写大模拟，但是前面的题开不出来

单调性二分图论二分图小学数学 ST表栈单调栈

# G

# 题目大意

# 数据范围

# 题解

# I

# 题目大意

# 数据范围

# 题解

# F

# 题目大意

# 数据范围

# 题解

# K

# 题目大意

# 数据范围

# 题解

# H

# 题目大意

# 数据范围

# 题解

# A

# 题目大意

# 数据范围

# 题解

# 单调栈写法

# 二分 + ST 表写法

# L

机器学习

2025CCPC郑州邀请赛