补一下题解（有机会写完的 🐦）

Vestigium

没啥可分析的

Vestigium.cpp
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
#include <bits/stdc++.h>
using namespace std;

int mat[105][105];

int main() {
    int T;
    cin >> T;
    for (int cas = 1; cas <= T; ++cas) {
        int n;
        cin >> n;

        int sum, cnt1, cnt2;
        sum = cnt1 = cnt2 = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                cin >> mat[i][j];
                if (i == j)
                    sum += mat[i][j];
            }
        
        for (int i = 1; i <= n; ++i) {
            vector<int> has(105);
            for (int j = 1; j <= n; ++j) {
                if (has[mat[i][j]]) {
                    ++cnt1;
                    break;
                }
                has[mat[i][j]] = 1;
            }
        }
        for (int i = 1; i <= n; ++i) {
            vector<int> has(105);
            for (int j = 1; j <= n; ++j) {
                if (has[mat[j][i]]) {
                    ++cnt2;
                    break;
                }
                has[mat[j][i]] = 1;
            }
        }
        printf("Case #%d: %d %d %d\n", cas, sum, cnt1, cnt2);
    }
    return 0;
}

Nesting Depth

类似$dfs$序列，有种判断树同构的算法$(AHU)$也是利用这个思路的。

Nesting Depth.cpp
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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    string s;
    for (int cas = 1; cas <= T; ++cas) {
        cin >> s;
        string ans;
        char la = '0';
        for (char c : s) {
            while (la < c) {
                ans.push_back('(');
                ++la;
            }
            while (la > c) {
                ans.push_back(')');
                --la;
            }
            ans.push_back(c);
        }
        while (la > '0') {
            ans.push_back(')');
            --la;
        }
        printf("Case #%d: %s\n", cas, ans.c_str());
    }
    return 0;
}

Parenting Partnering Returns

贪心，排序直接做就行了。

Parenting Partnering Returns.cpp
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
#include <bits/stdc++.h>
using namespace std;

struct rec {
    int l, r, id;
} act[1005];

bool cmp(rec &x, rec &y) {
    if (x.l != y.l)
        return x.l < y.l;
    return x.r < y.r;
};

int main() {
    int T;
    cin >> T;
    string s;
    for (int cas = 1; cas <= T; ++cas) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> act[i].l >> act[i].r;
            act[i].id = i;
        }
        sort(act, act + n, cmp);

        string ans(n, 0);
        int c = 0, j = 0;
        for (int i = 0; i < n; ++i) {
            if (act[i].l >= c) {
                ans[act[i].id] = 'C';
                c = act[i].r;
            } else if (act[i].l >= j) {
                ans[act[i].id] = 'J';
                j = act[i].r;
            } else {
                ans = "IMPOSSIBLE";
                break;
            }
        }
        printf("Case #%d: %s\n", cas, ans.c_str());
    }
    return 0;
}

ESAb ATAd

有一个$01$串，每次可以询问一个位置是$1$还是$0$，每$10$次询问可能发生$01$反转、前后翻转、都发生、都未发生，要求在$150$次询问内得到当前的串。

可以把前后对应的位置分为$4$种情况：

  • $00$、$11$，前后相同组，只会被 $01$反转、都发生 影响；
  • $01$、$10$，前后不同组，只会被 前后翻转、$01$反转 影响。
    那么每$10$次询问当作一组，从第二组开始后，每组开始都先从相同组和不同组分别取一个，询问一下，判断发生了什么事件，再继续询问未操作的对，直到全部询问完。
1
交互还没调好..

Indicium

看起来有点复杂，还没研究