vp了一下，感觉还是很难在两小时内全部想到再写出来

1282A Temporarily unavailable

a.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int a, b, c, r;
        cin >> a >> b >> c >> r;
        if (a > b) swap(a, b);
        int ans = 0;
        if (c - r > a)
            ans += min(b, c - r) - a;
        if (c + r < b)
            ans += b - max(a, c + r);
        cout << ans << endl;
    }
    return 0;
}

1282B K for the Price of One

可以算简单$dp$吧

b.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, p, k;
        cin >> n >> p >> k;
        vector<int> a(n + 1), dp(n + 1);
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        sort(a.begin() + 1, a.end());
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1] + a[i];
            if (i >= k) dp[i] = min(dp[i], dp[i - k] + a[i]);
            if (dp[i] <= p) ans = i;
        }
        cout << ans << endl;
    }
    return 0;
}

1282C Petya and Exam

按时间要求从小到大枚举可行，再计算剩余时间能多做几道题。

c.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
46
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, ti, p[2], cnt[2] = {};
        cin >> n >> ti >> p[0] >> p[1];
        vector<pii> a(n);
        for (int i = 0; i < n; ++i) {
            auto&[t, v] = a[i];
            cin >> v;
            ++cnt[v];
            v = p[v];
        }
        for (int i = 0; i < n; ++i) {
            auto&[t, v] = a[i];
            cin >> t;
        }
        a.emplace_back(ti + 1, 0);
        a.emplace_back(0, 0);
        sort(a.begin(), a.end(), [](auto a, auto b) { return a.first < b.first; });

        int ans = 0;
        ll cost = 0;
        for (int i = 0; i <= n; ++i) {
            auto[t, v] = a[i];
            cost += v;
            t = a[i + 1].first - 1;
            if (v == p[0]) --cnt[0];
            if (v == p[1]) --cnt[1];
            if (cost > t) continue;
            int tt = t - cost;
            int easy = min(tt / p[0], cnt[0]);
            tt -= easy * p[0];
            int hard = min(tt / p[1], cnt[1]);
            ans = max(ans, easy + hard + i);
        }

        cout << ans << endl;
    }
    return 0;
}

1282D Enchanted Artifact

比较脑筋急转弯吧
先问一个$a$，设回答是$ans_1$，如果 $ans_1$ 是 $300$ 那一定全是$b$；
如果不是的话，询问 $ans_1+1$ 个$a$，设回答是$ans_2$，如果 $ans_2 > ans_1$ 的话，那么一定是 $ans_1$ 个$b$；否则是$ab$混合的，长度为$n=ans_1$。
对于每一位，由于我们询问了全$a$的串，我们将当前位字母取 $b$ 询问，如果不匹配的数目增加了，那么这个更改就反了；反之则正确，依次询问 $n$ 位，一定能得到答案。

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

int main() {
    int t1, t2;
    cout << 'a' << endl;
    cin >> t1;
    if (t1 == 0)
        return 0;
    if (t1 == 300) {
        cout << string(300, 'b') << endl;
        return 0;
    }
    string s(t1 + 1, 'a');
    cout << s << endl;
    cin >> t2;
    if (t2 == 0)
        return 0;
    if (t2 > t1) {
        cout << string(t1, 'b') << endl;
        return 0;
    }
    int n = t1 + 1;
    for (int i = 0; i < n; ++i) {
        s[i] = 'b';
        cout << s << endl;
        cin >> t1;
        if (t1 == 0)
            break;
        if (t1 < t2) t2 = t1;
        else s[i] = 'a';
    }
    return 0;
}

1282E The Cake Is a Lie

将所以三角形纳入一个图中（也就是蛋糕被拼起来一样），那么被切产生的边一定是出现了偶数次，原来边界的边一定只出现了 $1$ 次，那么将所有出现一次的边连起来，就可以得到原来的多边形的环。
现在将所有的三角形和其中点关联起来，将一个点出现在几个三角形的个数作为度数，可以想到每次被切掉的点一定是某个度数为 $1$ 的点，那么做一次拓扑排序即可。

e.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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 1e5 + 5;

struct tri {
    int a[3];
} cc[N];

map<pii, int> mp;
set<int> st[N];

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i)
            st[i].clear();
        mp.clear();
        for (int i = 1; i <= n - 2; ++i) {
            auto&[a] = cc[i];
            cin >> a[0] >> a[1] >> a[2];
            sort(a, a + 3);
            for (int j = 0; j < 3; ++j)
                st[a[j]].emplace(i);
            ++mp[{a[0], a[1]}];
            ++mp[{a[0], a[2]}];
            ++mp[{a[1], a[2]}];
        }
        vector<vi> g(n + 1);
        for (auto &i : mp) {
            if (i.second & 1) {
                const pii &t = i.first;
                g[t.first].emplace_back(t.second);
                g[t.second].emplace_back(t.first);
            }
        }
        vector<int> vis(n + 1);
        function<void(int, int)> dfs = [&](int s, int fa) {
            cout << s << ' ';
            vis[s] = 1;
            for (int u : g[s]) {
                if (!vis[u]) {
                    dfs(u, s);
                }
            }
        };
        dfs(1, 0);
        cout << endl;

        queue<int> Q;
        for (int i = 1; i <= n; ++i) {
            if (st[i].size() == 1) {
                Q.emplace(i);
            }
        }
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            if (st[u].empty())break;
            int tt = *st[u].begin();
            cout << tt << ' ';
            auto&[a]= cc[tt];
            for (int i : a) {
                st[i].erase(tt);
                if (st[i].size() == 1)
                    Q.emplace(i);
            }
        }
        cout << endl;
    }
    return 0;
}