343

A - Wrong Answer

给你两个整数 $A$ 和 $B$ ，它们分别介于 $0$ 和 $9$ 之间。

请打印出不等于 $A + B$ 的、介于 $0$ 和 $9$ 之间的整数。

void solve() {
    int a, b;cin >> a >> b;
    for (int i = 0;i <= 9;i++) {
        if (i != a + b) {
            cout << i << '\n';return;
        }
    }
}

B - Adjacency Matrix

有一个简单的无向图 $G$ ，其中有 $N$ 个顶点，顶点上标有数字 $1, 2, \dots, N$ 。

给你 $G$ 的邻接矩阵 $(A_{i, j})$ 。也就是说，当且仅当 $A_{i, j} = 1$ 时， $G$ 有一条边连接顶点 $i$ 和 $j$ 。

对于每个 $i = 1, 2, \dots, N$ ，按升序打印与顶点 $i$ 直接相连的顶点的编号。

这里，当且仅当顶点 $i$ 和 $j$ 之间有一条边相连时，顶点 $i$ 和 $j$ 才被认为是直接相连的。

int a[110][110];
void solve() {
    int n;cin >> n;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            cin >> a[i][j];
            if (a[i][j]) {
                cout << j + 1 << ' ';
            }
        }
        cout << '\n';
    }
}

C - 343

给你一个正整数 $N$ 。

求一个不大于 $N$ 的回折立方数的最大值。

这里，正整数 $K$ 只有在满足以下两个条件时才被定义为回折立方数：

有一个正整数 $x$ ，使得 $x^{3} = K$ .
$K$ 的十进制表示不含前导零，是一个宫调立方数。更确切地说，如果用介于 $0$ 和 $9$ （含）之间的整数 $A_{0}, A_{1}, \dots, A_{L - 2}$ 和介于 $1$ 和 $9$ （含）之间的整数 $A_{L - 1}$ 将 $K$ 表示为 $K = \sum_{i = 0}^{L - 1} A_{i} 10^{i}$ ，则所有 $i = 0, 1, \dots, L - 1$ 都是 $A_{i} = A_{L - 1 - i}$ 。

#define int long long
void solve() {
    vector<int> cu;
    for (int i = 0;i <= 1e6;i++) {
        bool ok = true;
        string s = to_string(i * i * i);
        for (int j = 0;j < s.size();j++) {
            if (s[j] != s[s.size() - 1 - j])ok = false;
        }
        if (ok)
            cu.push_back(i * i * i);
    }
    int n;cin >> n;
    int pos = upper_bound(cu.begin(), cu.end(), n) - cu.begin();
    cout << cu[pos - 1] << '\n';
}

D - Diversity of Scores

高桥正在举办一场有 $N$ 名选手参加的比赛，选手编号为 $1$ 至 $N$ 。选手们将争夺积分。目前，所有棋手的积分都是零。

高桥的预知能力让他知道选手们的分数将如何变化。具体来说，对于 $i = 1, 2, \dots, T$ ， $A_{i}$ 选手的分数将在 $i$ 秒后增加 $B_{i}$ 分。分数不会有其他变化。

高桥希望分数多样化，他想知道在每个时刻棋手的分数中会出现多少个不同的分数值。对于每个 $i = 1, 2, \dots, T$ ，求从现在起 $i + 0.5$ 秒钟后玩家分数中不同分值的数量。

例如，如果在某一时刻球员的得分分别为 $10$ 、 $20$ 、 $30$ 和 $20$ ，那么在该时刻球员的得分中有三个不同的分值。

Solution

map 的使用

在这个问题中，只需将玩家的当前分数用作索引，并为每个索引 $x$ 维护具有分数 $x$ 的玩家数量。具体来说，算法如下：

准备一个关联数组 $M$ 。
添加索引 $0$ 到 $M$ ，令 $M [0] = N$ 。
准备一个数组 $C = (C_{1}, C_{2}, \dots, C_{N})$ ，存储玩家的分数，将每个元素初始化为 $0$ 。
对于每个 $i = 1, 2, \dots, T$ ，执行以下操作：
1. 减少 $M [C_{A_{i}}]$ 的值。
2. 如果 $M [C_{A_{i}}]$ 变为 $0$ ，则从 $M$ 中删除索引 $C_{A_{i}}$ 。
3. 将 $B_{i}$ 添加到 $C_{A_{i}}$ 。
4. 如果 $M$ 不包含索引 $C_{A_{i}}$ ，则插入它，并令 $M [C_{A_{i}}] = 0$ 。
5. 增加 $M [C_{A_{i}}]$ 的值。
6. 打印 $M$ 的当前大小（元素数量）。

#define int long long
void solve() {
    int n, t;cin >> n >> t;
    vector<int> a(n + 1);
    map<int, int> m;
    m[0] = n;
    while (t--) {
        int x, y;cin >> x >> y;
        if (--m[a[x]] == 0)m.erase(a[x]);
        a[x] += y;
        m[a[x]]++;
        cout << m.size() << '\n';
    }
}

E - 7 x 7 x 7

在一个坐标空间中，我们想放置三个边长为 $7$ 的立方体，这样正好一个、两个、三个立方体所包含区域的体积分别为 $V_{1}$ 、 $V_{2}$ 、 $V_{3}$ 。

对于三个整数 $a$ 、 $b$ 、 $c$ ，让 $C (a, b, c)$ 表示由 $(a \leq x \leq a + 7) \land (b \leq y \leq b + 7) \land (c \leq z \leq c + 7)$ 代表的立方体区域。

请判断是否有满足下列所有条件的九个整数 $a_{1}, b_{1}, c_{1}, a_{2}, b_{2}, c_{2}, a_{3}, b_{3}, c_{3}$ ，如果存在，请找出一个这样的元组。

$| a_{1} |, | b_{1} |, | c_{1} |, | a_{2} |, | b_{2} |, | c_{2} |, | a_{3} |, | b_{3} |, | c_{3} | \leq 100$
设 $C_{i} = C (a_{i}, b_{i}, c_{i}) (i = 1, 2, 3)$ .
- 恰好包含 $C_{1}, C_{2}, C_{3}$ 中一个的区域的体积为 $V_{1}$ 。
- 恰好包含两个 $C_{1}, C_{2}, C_{3}$ 的区域的体积是 $V_{2}$ 。
- 所有 $C_{1}, C_{2}, C_{3}$ 所包含的区域的体积是 $V_{3}$ 。

Solution

容斥原理

官方题解：

只有各个区域之间的相对位置才是重要的，因此可以固定其中一个区域。在此后，我们将 $C_{1}$ 的位置固定为 $a_{1} = b_{1} = c_{1} = 0$ 。

现在我们有以下事实：

事实：可以加入额外的约束条件，使得 $C_{1}$ 和 $C_{i} (i = 2, 3)$ 有交集，即它们分享一个正体积、边或顶点的区域，而不影响解的存在。换句话说，如果原问题有解，那么在加入这个条件后仍然有解。

这是因为，如果 $C_{1}$ 和 $C_{i}$ 没有交集，那么可以平移 $C_{i}$ 而不改变 $V_{1}, V_{2}$ 和 $V_{3}$ 的值，使其与 $C_{1}$ 接触。当 $C_{1}$ 和 $C_{2}$ 有交集， $C_{2}$ 和 $C_{3}$ 也有交集，但 $C_{1}$ 和 $C_{3}$ 没有时，可能会认为 $C_{3}$ 无法移动；但在这种情况下，可以交换 $C_{1}$ 和 $C_{2}$ ，然后平移所有的立方体，使得 $a_{1} = b_{1} = c_{1} = 0$ 。

根据这个事实，我们可以假设 $a_{2}, b_{2}, c_{2}, a_{3}, b_{3}, c_{3}$ 的绝对值不大于 $7$ ，这样可以将候选数量减少到 $15^{6} \approx 10^{7}$ 。剩下的就是对于给定的 $a_{2}, b_{2}, c_{2}, a_{3}, b_{3}, c_{3}$ ，找到恰好包含在一个、两个或三个立方体中的区域的体积。

首先，可以通过以下方式找到立方体 $C_{i}$ 和 $C_{j}$ 的交集的体积 $V (C_{i} \cap C_{j})$ ，即 $max {0, min {a_{i}, a_{j}} + 7 - max {a_{i}, a_{j}}} \times max {0, min {b_{i}, b_{j}} + 7 - max {b_{i}, b_{j}} \times max {0, min {c_{i}, c_{j}} + 7 - max {c_{i}, c_{j}}}$ ，因为交集可以表示为：

$max {a_{i}, a_{j}} \leq x \leq min {a_{i} + 7, a_{j} + 7}$

$max {b_{i}, b_{j}} \leq y \leq min {b_{i} + 7, b_{j} + 7}$

$max {c_{i}, c_{j}} \leq z \leq min {c_{i} + 7, c_{j} + 7}$ 。

同样适用于三个立方体 $C_{i}$ 、 $C_{j}$ 和 $C_{k}$ 的交集的体积 $V (C_{i} \cap C_{j} \cap C_{k})$ 。

接下来，用包含-排斥原理的思想，定义 $v_{i}$ 为恰好包含 $i$ 个立方体的区域，可以如下找到 $v_{1}, v_{2}$ 和 $v_{3}$ ：

$v_{3} = V (C_{1} \cap C_{2} \cap C_{3})$

$v_{2} = V (C_{1} \cap C_{2}) + V (C_{1} \cap C_{3}) + V (C_{2} \cap C_{3}) - 3 v_{3}$

$v_{1} = 3 \times 7^{3} - 2 v_{2} - 3 v_{3}$

因此，可以对所有的 $a_{2}, b_{2}, c_{2}, a_{3}, b_{3}, c_{3}$ 的候选值找到 $v_{1}, v_{2}, v_{3}$ ，并检查它们是否与 $V_{1}, V_{2}, V_{3}$ 一致来解决问题。

附加内容

事实上，可以实验性地将 $a_{2}, b_{2}, c_{2}, a_{3}, b_{3}, c_{3}$ 的范围限定为 $[- 1, 7]$ 。但尚未证明这一点，也不清楚与立方体边长的独立性。

对于一条线段，坐标分别为 $[l_{1}, r_{1}], [l_{2}, r_{2}]$ 则相交部分是 $[max (l_{1}, l_{2}), min (r_{1}, r_{2})]$

同理，对于一个三维的物体，则需要对于每个维度查看相交的部分，再依次相乘即可。

$v_{3} = V (C_{1} \cap C_{2} \cap C_{3})$
$v_{2} = V (C_{1} \cap C_{2}) + V (C_{1} \cap C_{3}) + V (C_{2} \cap C_{3}) - 3 v_{3}$
$v_{1} = 3 \times 7^{3} - 2 v_{2} - 3 v_{3}$

#include<bits/stdc++.h>
using namespace std;
int f(int a1, int b1, int c1, int a2, int b2, int c2) {
    int res = 1;
    res *= max(0, min(a1, a2) + 7 - max(a1, a2));
    res *= max(0, min(b1, b2) + 7 - max(b1, b2));
    res *= max(0, min(c1, c2) + 7 - max(c1, c2));
    return res;
}
int f(int a1, int b1, int c1, int a2, int b2, int c2, int a3, int b3, int c3) {
    int res = 1;
    res *= max(0, min({a1, a2, a3}) + 7 - max({a1, a2, a3}));
    res *= max(0, min({b1, b2, b3}) + 7 - max({b1, b2, b3}));
    res *= max(0, min({c1, c2, c3}) + 7 - max({c1, c2, c3}));
    return res;
}
int main() {
    int v1, v2, v3;
    cin >> v1 >> v2 >> v3;
    for (int a2 = -7; a2 <= 7; a2++) {
        for (int b2 = -7; b2 <= 7; b2++) {
            for (int c2 = -7; c2 <= 7; c2++) {
                for (int a3 = -7; a3 <= 7; a3++) {
                    for (int b3 = -7; b3 <= 7; b3++) {
                        for (int c3 = -7; c3 <= 7; c3++) {
                            int nv3 = f(0, 0, 0, a2, b2, c2, a3, b3, c3);
                            int nv2 = f(0, 0, 0, a2, b2, c2) + f(0, 0, 0, a3, b3, c3) + f(a2, b2, c2, a3, b3, c3) - nv3 * 3;
                            int nv1 = 3 * 7 * 7 * 7 - nv2 * 2 - nv3 * 3;
                            if (v1 != nv1 or v2 != nv2 or v3 != nv3) continue;
                            printf("Yes\n0 0 0 %d %d %d %d %d %d\n", a2, b2, c2, a3, b3, c3);
                            return 0;
                        }
                    }
                }
            }
        }
    }
    cout << "No" << endl;
}

F - Second Largest Query

给你一个长度为 $N$ 的序列 $A = (A_{1}, A_{2}, \dots, A_{N})$ 。

请按照给出的顺序处理 $Q$ 个查询。每个查询属于以下两种类型之一：

类型 $1$ ：以 1 p x 的形式给出。将 $A_{p}$ 的值改为 $x$ 。
类型 $2$ ：以 2 l r 的形式给出，打印 $(A_{l}, A_{l + 1}, \dots, A_{r})$ 中第二大数值的出现次数。更准确地说，打印满足 $l \leq i \leq r$ 的整数 $i$ 的个数，即在 $A_{l}, A_{l + 1}, \dots, A_{r}$ 中正好有一个大于 $A_{i}$ 的不同值。

Solution

线段树(待更 $\dots$ )