Personal solution.

A. A Mistaken Input

题意

输出字符串中有多少个 \(1\)。

思路

签到题。

如题。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    for(auto e : s){
        if(e == '1') cnt ++;
    }
    cout << cnt << '\n';
}

取材于现实（

B. Backpack of Capoo

题意

给定 \(n\) 个物品，每个物品具有体积 \(v_i\) 和价值 \(w_i\)。

对于每个物品，输出需要将其价值提高多少，才能让其成为 \(01\) 背包中的必选物品。

思路

对 \(01\) 背包的理解。

把除了第 \(i\) 个物品以外的物品做一下 \(01\) 背包，然后判断第 \(i\) 个物品是否必须取（取这个物品后答案更优）即可。

不选这个物品的代价是 \(p = dp[m]\)，选这个的代价是 \(q = dp[m - w_i] + v_i\)。

注意需要严格大于，从而 \(ans = p - q + 1\)。注意 \(ans\) 可能为负。

时间复杂度：\(O(n^2m)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> w(n + 1), v(n + 1);
    for(int i=1;i<=n;i++) cin >> w[i] >> v[i];
    for (int i = 1; i <= n; i++) {
        vector<int> dp(m + 1);
        for(int j=1;j<=n;j++){
            if(i == j) continue;
            for (int k = m; k >= w[j]; k--) {
                dp[k] = max(dp[k], dp[k - w[j]] + v[j]);
            }
        }
        cout << max(0ll, dp[m] - (dp[m - w[i]] + v[i]) + 1) << '\n';
    }
}

别爆 int 了

C. Construction, I am a Master of it!

题意

给定一个序列，任意排序后，输出 \(\text{MEX}(a_1 + a_2, a_2 + a_3, \ldots, a_{n - 1} + a_n)\) 的最小值。

思路

思维，分类讨论。

不难发现，将 \(0\) 穿插在非 \(0\) 元素之间是最优的。比如说 \(0, 1, 0, 2, 0\)。

那么，我们考虑对 \(0\) 个数的分讨：

\(0\) 的个数 \(\leq \frac{n + 1}{2}\)，此时 \(0\) 是不会有多余的，从而 \(\min(a_{i - 1}, a_i) \geq 1\)，有 \(\text{MEX} = 0\)；
\(a_{\max} = 0\)，此时 \(\text{MEX} = 1\)；
\(a_{\max} = 1\)，此时无论如何 \(0\) 和 \(1\) 一定会相邻，我们将 \(0\) 穿插在 \(1\) 之间，然后多余的随便放即可，从而 \(\text{MEX} = 2\)；
其他情况下，我们只要先将 \(0\) 放在开头或末尾，然后将非 \(1\) 元素和 \(0\) 相邻，即可让序列中不包含 \(1\)，从而 \(\text{MEX} = 1\)

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    map<int, int> cnt;
    int mx = 0;
    for(int i=0;i<n;i++) {
        int cur;
        cin >> cur;
        mx = max(mx, cur);
        cnt[cur] ++;
    }
    if(cnt[0] <= (n + 1) / 2) cout << 0 << '\n';
    else if(cnt[0] == n) cout << 1 << '\n';
    else cout << (mx == 1 ? 2 : 1) << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

有意思的构造题

D. Darkest Night, I Confront you here...

题意

给定一个正整数 \(n\) ，双方轮流操作，每次取 \(n\) 的一个因子 \(x\)，并将 \(n\) 减去 \(x\)。

游戏判定谁先将 \(n\) 减到 \(0\) 谁输，输出胜者。

思路

思维，博弈。

注意不是减到 \(0\) 后对方输，如果这样的话后手一定输了。

首先，\(1\) 是必输态，那么相应地，\(2\) 是必胜态。

可以发现，\(3\) 是必败态，因为我们只能减掉 \(1, 3\)，而两者都是必输的。

同样地，\(4\) 是必胜态，因为我们可以减掉 \(2\)，达到必胜态。

从而，简单归纳可得：\(n\) 为奇数必败，偶数必胜。

下面是牛客官方题解的证明：

显然 \(1\) 是先手必输。我们证明所有奇数都是先手必输：由于奇数只包含奇数的因子，那么只能取一个奇数变成偶数（或者变成 \(0\) 直接输掉），然后对方就可以直接取 \(1\) 变成奇数，仍然到必输的状态。因此奇数先手必输，偶数先手必胜。

时间复杂度：\(O(1)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    cout << (n % 2 == 0 ? "Hikari" : "Tairitsu");
}

博弈可以乱猜！（

E. Emm, my Milky Tea is Leaking

题意

给定一个不一定连通的无向图，定义操作如下：

移动到相邻没有被标记的结点；
位于任意结点时，可以在该结点上做一个标记

按任意顺序操作后，给定操作后每个点被标记的个数，输出合法的由起点和终点构成的二元组的个数。

思路

图论，思维，\(\mathtt{dfs}\) / 并查集。

首先，我们不可能从一个连通块移动到另一个连通块上，从而我们考虑对每一个连通块进行计算。

可以发现，我们可以任意做标记，次数是不限的，从而我们可以无视次数，将其视为移动时有经过过该点即可。

其次，操作顺序是无所谓的，从而我们可以直接在最后一次离开该结点后再做标记。

那么，可以发现，在同一个连通块上，我们可以访问到所有结点，无论起点和终点如何选择。

因而，对于一个结点数为 \(cnt\) 的连通块，起点和终点的选择总共有 \(cnt^2\) 种。

从而，我们只需检查哪些连通块有标记即可：

如果没有一个连通块被标记，那么起点和终点可以任意选，答案为 \(\sum cnt_i^2\)，\(cnt_i\) 为第 \(i\) 个连通块的结点数；
如果只有一个连通块被标记，那么我们只能在该连通块选择起点终点，从而答案为 \(cnt ^ 2\)；
如果有多个连通块被标记，显然此时是无解的，输出 \(0\) 即可。

至于遍历的方式，\(\mathtt{dfs}\) 和 \(\mathtt{dsu}\) (并查集) 都是可以的，但是后者更好写，而且时间复杂度更优。

时间复杂度：\(O(n + m)\)

对应AC代码 (dfs)

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> e(n + 1);
    while(m --){
        int u, v;
        cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    int ans = 0, cnt = 0, egg = 0, cur = 0;
    vector<bool> st(n + 1);
    bool have = false;
    auto dfs = [&](auto dfs, int x) -> void{
        if(st[x]) return;
        st[x] = true;
        cur ++;
        if(a[x] > 0) have = true;
        for(auto it : e[x]){
            dfs(dfs, it);
        }
    };
    for(int i=1;i<=n;i++){
        if(st[i]) continue;
        cur = 0;
        have = false;
        dfs(dfs, i);
        ans += cur * cur;
        if(have) {
            egg ++;
            cnt = cur * cur;
        }
    }
    if(egg == 0) cout << ans << '\n';
    else if(egg == 1) cout << cnt << '\n';
    else cout << 0 << '\n';
}

对应AC代码 (dsu)

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> pa(n + 1), siz(n + 1, 1);
    iota(pa.begin(), pa.end(), 0);
    auto find = [&](auto find, int x) -> int {
        return pa[x] == x ? x : pa[x] = find(find, pa[x]);
    };
    auto unite = [&](int u, int v) {
        int f1 = find(find, u), f2 = find(find, v);
        if (f1 > f2) swap(f1, f2);
        if (f1 != f2) {
            pa[f2] = pa[f1];
            siz[f1] += siz[f2];
        }
    };
    while (m --) {
        int u, v;
        cin >> u >> v;
        unite(u, v);
    }
    map<int, int> cnt;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x > 0) cnt[find(find, i)] ++;
    }
    if (cnt.size() > 1) cout << 0 << '\n';
    else if (cnt.empty()) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (find(find, i) == i) ans += siz[i] * siz[i];
        }
        cout << ans << '\n';
    } else {
        int x = (*cnt.begin()).first;
        cout << siz[x] * siz[x] << '\n';
    }
}

别爆 int 了

F. Form a Larger Knapsack

题意

对于一个序列，定义每一轮操作为将相邻数相加，构成一个新的长度减一的序列。

在若干次操作后，序列将变为一个数。

构造一个长为 \(n\) 的排列，使最后的数尽可能大。

思路

构造，思维。

显然是越靠中间的数被累加的次数越多，或者更具体地：

\(\begin{array}{l}\ldots[a, b, c, d, e] \\ \rightarrow [a + b, b + c, c + d, d + e] \\ \rightarrow [a + 2b + c, b + 2c + d, c + 2d + e] \\ \rightarrow [a + 3b + 3c + d, b + 3c + 3d + e] \\ \rightarrow [a + 4b + 6c + 4d + e] \\ \rightarrow \ldots\end{array}\)

是不是有点眼熟？是的，这是杨辉三角。

当然，你可以发现，预处理杨辉三角的复杂度和直接暴力合并的复杂度相当，而后者更好实现。

从而，我们只需在中间放最大的数，然后依次向两边递减放数字即可。

比如说，\(1\ 3\ 5\ 4\ 2\) 就是一个合法的构造。

然后，我们暴力合并，计算结果即可。

时间复杂度：\(O(n ^ 2)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n/2;i++) a[i] = i * 2 - 1;
    if(n % 2 == 1) a[n / 2 + 1] = n;
    for(int i=1;i<=n/2;i++) a[n - i + 1] = i * 2;
    vector<int> ans(a);
    for(int i=n;i>1;i--){
        vector<int> now(i);
        for(int j=1;j<i;j++){
            now[j] = (ans[j] + ans[j + 1]) % mod;
        }
        ans = now;
    }
    cout << ans[1] << '\n';
    for(int i=1;i<=n;i++) cout << a[i] << ' ';
    cout << '\n';
}

预处理杨辉三角还是有点抽象的

G. Go Shopping! Target Tilenn's Shop!

题意

给定 \(n\) 个物品，每个物品具有价值 \(a_i\)。

对于 \(q\) 个询问，每个询问给定 \(k, x\)，输出挑选最多 \(k\) 个价值不大于 \(x\) 的物品后，价值和的最大值。

思路

签到，前缀和，二分。

首先，既然是要让价值和尽可能大，数量尽可能不超过上限，那么我们直接降序拿即可。

然后，我们需要确定当前能拿的最大的物品在哪个位置，从而可以从这个物品开始降序拿。

从而，我们考虑升序排序，然后进行二分。

接着，我们需要高效计算从这个物品开始降序取最多 \(k\) 个物品的价值和。

从而，我们考虑预处理前缀和。

注意边界的判断。

时间复杂度：\(O(n + q \log n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(all(a));
    vector<int> sum(n + 1);
    for(int i=1;i<=n;i++) sum[i] = sum[i - 1] + a[i];
    while(q --){
        int k, x;
        cin >> k >> x;
        int r = upper_bound(a.begin(), a.end(), x) - a.begin() - 1;
        if(r >= k) cout << sum[r] - sum[r - k] << '\n';
        else cout << sum[r] << '\n';
    }
}

二分可以用 stl 的 upper_bound，与之对应的还有一个 lower_bound

H. Heaps of Chrysanthemum

题意

给定一棵无根树，定义操作如下：

选择一条边 \(u - v\)，将和 \(u\) 相连的所有点（除了 \(v\)）和 \(u\) 断开连接，并重新和 \(v\) 连接。

输出最小操作数，使其变为菊花图。

思路

图论签到，思维，度。

可以发现，如果操作的边中，有一个点是叶节点，那么操作之后两棵树是同构的，等价于没操作。

从而，我们考虑对所有非叶节点之间的边进行操作。

可以发现，有价值的操作能使叶节点的数量增加 \(1\)，而叶节点最多也就 \(n - 1\) 个。

那么，我们统一 非叶节点 的个数 \(cnt\)，最后操作数就是 \(cnt - 1\)。

显然，我们只需统计度大于 \(1\) 的结点数即可，甚至没必要建图。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<int> du(n + 1);
    for(int i=1;i<n;i++){
        int u, v;
        cin >> u >> v;
        du[u] ++, du[v] ++;
    }
    int cnt = 0;
    for(int i=1;i<=n;i++){
        if(du[i] > 1) cnt ++;
    }
    cout << max(0ll, cnt - 1) << '\n';
}

题面的图我手画的（x

I. Integer Triple

题意

给定一个长为 \(n\) 的序列 \(a\)，统计三元组 \([i, j, k]\) 的个数，满足：

\(i \neq j, i \neq k, j \neq k\)；
\((a_i \cdot a_j+a_k) \equiv x \pmod p\)

思路

数论，暴力。

首先，我们进行移项：\(a_i \cdot a_j \equiv x - a_k \pmod p\)。

那么，我们只需先 \(n ^ 2\) 暴力预处理 \(a_i \cdot a_j \bmod p\) 所有值的出现次数，然后遍历 \(a_k\)，统计答案即可。

注意，我们需要去掉 \(i, j, k\) 中任意两个出现相同的情况。

至于怎么去掉，有下面的策略：

统计答案时不要让 \(i = j\)；
最后再 \(n ^ 2\) 暴力枚举 \(<i, j>\)，将所有答案都减掉 \(2\)，因为对于每个三元组，都有 \(i = k, j = k\) 的情况出现。

时间复杂度：\(O(n ^ 2)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, p;
    cin >> n >> p;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<int> cnt(p);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            cnt[a[i] * a[j] % p] += 2;
        }
    }
    vector<int> ans(p);
    for (int x = 0; x < p; x++) {
        for (int k = 1; k <= n; k++) {
            ans[x] += cnt[((x - a[k]) % p + p) % p];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            ans[(a[i] * a[j] + a[i]) % p] -= 2;
            ans[(a[i] * a[j] + a[j]) % p] -= 2;
        }
    }
    for(auto e : ans) cout << e << ' ';
    cout << '\n';
}

注意，\(O(n ^ 2)\) 的常数已经很大了，不要尝试写 \(map\)。