Credit Cards

队友查了一下，是 IMO 原题的改编（原题是证明 { 2,3,…,3n+1 }\set{2,3,\dots,3n+1} 一定可以划分出 nn 个钝角三角形，这题是构造）.

思路是递归构造，假设当前的集合为 { 2,3,…,3n+1 }\set{2,3,\dots, 3n+1}. 令 k=⌊n2⌋k=\lfloor \frac{n}{2}\rfloor，且 solve(n)\texttt{solve}(n) 返回 { 2,3,…,3n+1 }\set{2,3,\dots, 3n+1} 可以构造出来的解.

算法是，对于每个 solve(k)\texttt{solve}(k) 的解 { a,b,c },a<b<c\set{a,b,c},a\lt b\lt c，映射到 { a,b+n−k,c+n−k }\set{a,b+n-k,c+n-k}. 除此之外，对于 i∈[k+2,n+1]i\in[k+2,n+1]，构造 { i,i+n+k,i+2n }\set{i, i+n+k, i+2n}.

证明

我们分两步. 第一步，证明这样构造可以把值域选满；第二步，证明每一个三角形都是钝角三角形

先进行第一步，我们用归纳法证明：对于 solve(n)=\texttt{solve}(n)= 可以从 { 2,3,…,3n+1 }\set{2,3,\dots,3n+1} 得到的所有解 { (a,b,c) },a<b<c\set{(a,b,c)},a\lt b\lt c，我们有 { a }=[2,n+1],{ b,c }=[n+2,3n+1]\set{a}=[2,n+1],\set{b,c}=[n+2,3n+1]

一、当 n=1n=1 时，合法的解是 { (2,3,4) }\set{(2,3,4)}，显然满足.

考虑 nn，令 k=⌊n2⌋k=\lfloor\frac{n}{2}\rfloor，假设 solve(k)\texttt{solve}(k) 满足，则所有 aa 的值域范围是 [2,k+1]∪[k+2,n+1]=[2,n+1][2,k+1]\cup [k+2,n+1]=[2,n+1]，所有 b,cb,c 的值域范围是 ([k+2,3k+1]+n−k)∪[k+2+n+k,3n+1]=[n+2,n+2k+1]∪[n+2k+2,3n+1]=[n+2,3n+1]([k+2, 3k+1]+n-k)\cup [k+2+n+k, 3n+1]=[n+2,n+2k+1]\cup [n+2k+2, 3n+1]=[n+2,3n+1]. 可以发现新构造的解集与 solve(t)\texttt{solve}(t) 的值域是不重复的.

二、接着证明每一个都是顿觉三角形. 我们还是用归纳法. 当 n=1n=1 是，解集为 { (2,3,4) }\set{(2,3,4)} 显然是钝角三角形.

接着，假设 solve(k),k≥1\texttt{solve}(k), k\ge 1 合法（k=⌊n2⌋k=\lfloor\frac{n}{2}\rfloor），对于 (a,b,c)∈solve(k)(a,b,c)\in\texttt{solve}(k) 有 a2+b2<c2a^2+b^2\lt c^2，于是考虑 (a,b+n−k,c+n−k)(a,b+n-k,c+n-k)

(c+n−k)2−(b+n−k)2−a2=c2+2c(n−k)+(n−k)2−b2−2b(n−k)−(n−k)2−a2=(c2−b2−a2)+2(n−k)(c−b)>0 \begin{aligned} &(c+n-k)^2-(b+n-k)^2-a^2\\ =\quad&c^2+2c(n-k)+\cancel{(n-k)^2}-b^2-2b(n-k)-\cancel{(n-k)^2}-a^2\\ =\quad&(c^2-b^2-a^2)+2(n-k)(c-b)\gt 0 \end{aligned}

接着证明，对于 i∈[k+2,n+1]i\in[k+2,n+1]，(i,i+n+k,i+2n)(i,i+n+k,i+2n) 也是合法的

(i+2n)2−(i+n+k)2−i2=i2+4in+4n2−i2−2i(n+k)−(n+k)2−i2=−i2+2i(n−k)+4n2−(n+k)2=−(i2−2i(n−k)+(n−k)2)+4n2−4nk=−(i−n+k)2+4n(n−k) \begin{aligned} &(i+2n)^2-(i+n+k)^2-i^2\\ =\quad &i^2+4in+4n^2-i^2-2i(n+k)-(n+k)^2-i^2\\ =\quad &-i^2+2i(n-k)+4n^2-(n+k)^2\\ =\quad &-(i^2-2i(n-k)+(n-k)^2)+4n^2-4nk\\ =\quad &-(i-n+k)^2+4n(n-k) \end{aligned}

因为 i>k+1i\gt k+1，所以 i+k−n>2k+1−n≥0i+k-n\gt 2k+1-n\ge 0 故函数单调递减，所以当 i=n+1i=n+1 时，原式 =4n2−4nk−(k+1)2=4n^2-4nk-(k+1)^2.

若 n=2kn=2k，则 =16k2−8k2−k2−2k−1=7k2−2k−1=7(k−17)2−87=16k^2-8k^2-k^2-2k-1=7k^2-2k-1=7(k-\frac{1}{7})^2-\frac{8}{7} 在 k∈[1,∞]k\in [1,\infin] 上严增，因此最小值为 4>04\gt 0

若 n=2k+1n=2k+1，则 =16k2+16k+4−8k2−4k−k2−2k−1=7k2+10k+3>0=16k^2+16k+4-8k^2-4k-k^2-2k-1=7k^2+10k+3\gt 0. 于是得证.

综上，这样的构造法一定是合法的.

时间复杂度 O(nlog⁡n)O(n\log n).

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using tup = std::tuple<int, int, int>;
using vtup = std::vector<tup>;

int m;
vtup v;

int main() {
    std::cin >> m;

    auto dfs = [&](auto self, int n) -> void {
        if (n <= 0) return;
        if (n == 1) {
            v.push_back({2, 3, 4});
            return;
        }
        int k = n / 2;

        self(self, k);
        for (auto &[a, b, c] : v) b += n - k, c += n - k;
        for (int i = k + 2; i <= n + 1; i++) v.push_back({i, i + n + k, i + n * 2});
    };
    dfs(dfs, (m - 1) / 3);

    std::cout << v.size() << "\n";
    for (auto [a, b, c] : v) std::cout << a << " " << b << " " << c << "\n";
}

Brackets

贪心题. 先将字符串划分成 加号、字母、加号…… 的交替序列，对于每个字母变量，先贪心地从左侧的加号段拿两个加号过来，再贪心地从右侧的加号段拿两个加号过来. 时间复杂度 O(n)O(n).

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>

std::vector<int> f;
std::vector<int> ind;
std::string a;

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    std::cin >> a;
    for (int i = 0; i < a.length();) {
        int j = i;
        while (j < a.length() && a[j] == '+') j++;
        if (i == j) {
            j++;
            f.push_back(-i);
            i = j;
            continue;
        }

        f.push_back(j - i);
        i = j;
    }
    
    ind.assign(f.size(), 0);
    int s = f[0] <= 0 ? 0 : 1;

    for (int i = s; i < f.size(); i += 2) {
        if (f[i] > 0) continue;
        if (i > 0 && f[i - 1] >= 2) {
            f[i - 1] -= 2;
            ind[i] |= 1 << 2;
        }
        if (i + 1 < f.size() && f[i + 1] >= 2) {
            f[i + 1] -= 2;
            ind[i] |= 1 << 3;
        }
    }

    for (int i = 1 - s; i < f.size(); i += 2) assert(f[i] <= 1);
    std::string ans = "";
    for (int i = 0; i < f.size(); i++) {
        if ((i - s) % 2 == 0) {
            if (ind[i] == 0) ans += a[-f[i]];
            else if (ind[i] == 8) {
                ans.push_back('(');
                ans.push_back(a[-f[i]]);
                ans += "++)";
            } else if (ind[i] == 4) {
                ans += "(++";
                ans.push_back(a[-f[i]]);
                ans += ")";
            } else {
                ans += "(++";
                ans.push_back(a[-f[i]]);
                ans += "++)";
            }
        } else {
            for (int j = 0; j < f[i]; j++) ans += "+";
        }
    }

    std::cout << ans << "\n";
}

E

Jeopardized Betting

这道题从比分开始倒着推就很容易了. 题目的条件就是说，假设现在 aa 元，下注 bb 元，赢了则变为 a+ba+b 输了则变为 a−ba-b. 目标是在所有比赛结束后，如果己方队伍赢了，那么最终钱是初始的两倍；否则为 00. 以下假设初始钱财数量为 11 unit.

假设当前比分为 (n−1,n−1)(n-1,n-1)（以下，前者为己方队伍），那么这时候我们必须持有 11 然后下注 11（以下简记为 1@11@1）.

倒一步，假设比分为 (n−1,n−2)(n-1,n-2)，且此时“持有@下注”为 a+ba+b。如果赢了，那么 a+b=2a+b=2；否则会回到 (n−1,n−1)(n-1,n-1) 的局面，即 a−b=1a-b=1. 可以解得 a=1.5,b=0.5a=1.5, b=0.5. 对称的，(n−2,n−1)(n-2,n-1) 也是同理.

所以我们发现，当比分为 (x,y)(x,y) 时，“持有@下注” 可以通过 (x+1,y)(x+1,y) 和 (x,y+1)(x,y+1) 两个状态得到，类似于杨辉三角的形状. 所以，由此，我们可以计算出 (0,0)(0,0) 的状态，并且根据交互器的输出在杨辉三角上移动.

预处理的时间复杂度为 O(n2)O(n^2)

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>

using ll = long long;
using score = std::pair<int, int>;
using bet_at = std::pair<ll, ll>;
std::map<score, bet_at> mp;

int n, win{0}, lose{0};
ll hold;

void construct() {
    ll init = 1ll << (n * 2);
    for (ll i = n - 1, step = init, t = init; i >= 0; i--, step >>= 1, t += step) {
        mp[{n - 1, i}] = {t, step};
        mp[{i, n - 1}] = {step, step};
    }
    for (int sum = 2 * n - 2; sum >= 0; sum--) {
        for (int my = n - 1; my >= 0; my--) {
            if (sum - my < 0 || sum - my >= n - 1 || my >= n - 1) continue;
            int op = sum - my;
            auto [hold1, bet1] = mp[{my, op + 1}];
            auto [hold2, bet2] = mp[{my + 1, op}];

            mp[{my, op}] = {(hold1 + hold2) / 2, (bet1 + bet2) / 2};
        }
    }
}

void bet() {
    std::cout << mp[{win, lose}].second << std::endl;
    std::string t;
    std::cin >> t;

    if (t == "Won") win++;
    else lose++;
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    std::cin >> n;
    hold = 1ll << (n * 2);
    construct();

    while (win < n && lose < n) bet();

    return 0;
}

KPI Calculation

简单的模拟题.

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

int main() {
    std::string a;
    int ans = 0;

    while ((std::getline(std::cin, a))) {
        int t = 0, printable = false;
        for (int i = 0; i < a.length(); i++) {
            if (a[i] == ' ') t++;
            else if (a[i] != '\n') {
                printable = true;
                break;
            }
        }

        if(printable) ans += t;
    }

    std::cout << ans << "\n";
}
ICPC/NTU Training
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。