A. Access Denied

先问若干次，问出长度，然后再一位一位的问即可。

#include <bits/stdc++.h>

using namespace std;

int input() {
    string s;
    getline(cin, s);
    if (s == "ACCESS GRANTED")
        exit(0);
    int t = 0;
    for (auto i: s) {
        if (i >= '0' and i <= '9')
            t = t * 10 + i - '0';
    }
    return t;
}

int32_t main() {
    int len = -1;
    for (int i = 1, t; len == -1 and i <= 20; i++) {
        cout << string(i, '0') << endl << flush;
        t = input();
        if (t != 5) len = i;
    }
    vector<char> ans(len), ch;
    for (char i = '0'; i <= '9'; i++) ch.push_back(i);
    for (auto i = 'a'; i <= 'z'; i++) ch.push_back(i);
    for (auto i = 'A'; i <= 'Z'; i++) ch.push_back(i);

    for (int i = 0, t; i < len; i++) {
        for (auto c: ch) {
            for (int j = 0; j < i; j++)
                cout << ans[j];
            for (int j = i; j < len; j++)
                cout << c;
            cout << endl << flush;
            t = input();
            if (t == 5 + (i + 1) * 9) continue;
            ans[i] = c;
            break;
        }
    }
    for( auto i : ans )
        cout << i;
    cout << endl << flush;
    return 0;
}

D. Dyson Circle

首先按照题目的要求，我们可以把戴森环的凹陷部分展开，这样的戴森环就变成了一个矩形。那么对于矩形，我们让边全部在对角线方向最优，所以就要找到主副对角线的边界。如果某对角线方向长度只有 1 的话不符合题目的要求，因为题目要求内点的连通是有边相邻。

#include<bits/stdc++.h>

using namespace std;


int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, a = INT_MIN, b = INT_MIN, c = INT_MAX, d = INT_MAX;
    cin >> n;
    if (n == 1) cout << "4\n", exit(0);
    for (int x, y; n; n--) {
        cin >> x >> y;
        a = max(a, x + y);
        b = max(b, x - y);
        c = min(c, x + y);
        d = min(d, x - y);
    }
    cout << 4 + a + b - c - d + (a == c) + (b == d) << "\n";
    return 0;
}

G. Glossary Arrangement

#include<bits/stdc++.h>

using namespace std;

using vi = vector<int>;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, w;
    cin >> n >> w;
    vector<string> s(n);
    for (auto &i: s) cin >> i;
    vector<int> f(n + 1);

    auto dp = [n, w, s, &f](int h) {
        f.assign(n + 1, w + 1);
        f[0] = -1;
        for (int i = 0, mx; i < n; i++) {
            mx = 0;
            for (int j = i; j < n and j < i + h; j++) {
                mx = max(mx, int(s[j].size()));
                f[j + 1] = min(f[j + 1], f[i] + mx + 1);
            }
        }
        return f[n];
    };

    int l = 1, r = n, h = -1;
    for (int mid; l <= r;) {
        mid = (l + r) / 2;
        if (dp(mid) <= w) h = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << h << " ";
    vi v;
    dp(h);
    for (int i = n, j, mx; i;) {
        j = i, mx = 0;
        do {
            j--;
            mx = max(mx, int(s[j].size()));
        } while (f[i] != f[j] + mx + 1);
        v.push_back(mx), i = j;
    }
    reverse(v.begin(), v.end());
    cout << v.size() << "\n";
    for (auto i: v) cout << i << " ";
    cout << "\n";
    vector<string> res(h);
    for (int i = 0, k = 0; i < v.size(); i++) {
        for (int j = 0; j < h; j++) {
            if (i) res[j] += " ";
            string t;
            if (k < n and s[k].size() <= v[i]) t = s[k++];
            t.resize(v[i], ' ');
            res[j] += t;
        }
    }
    for (auto i: res)
        cout << i << "\n";
    return 0;
}

H. Heating Up

初始的辣度满足单调性，因此我们可以用二分答案。

有了初始辣度后，要考虑的就是如何把所有的披萨吃完，首先破环成链，然后从头开始枚举，如果可以吃就直接吃，否则就把这片披萨放进栈里，并且还原耐辣值。同时每次耐辣值上升后，都重新判断一下栈顶的披萨是否可以被吃下。

#include <bits/stdc++.h>

using namespace std;

#define int __int128
using ll = long long;
using pii = pair<int, int>;

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

constexpr int inf = 1e15;

int32_t main() {
    int n = read();
    vector<int> a(n + n + 1);
    for (int i = 1; i <= n; i++)
        a[i + n] = a[i] = read();
    n = n * 2;
    auto check = [a, n](int x) -> bool {
        int tot = x;
        stack<pii> stk;
        for (int i = 1; i <= n; i++) {
            if (a[i] <= tot) {
                tot += a[i];
                while (!stk.empty() and stk.top().first <= tot) {
                    tot += stk.top().second;
                    stk.pop();
                }
            } else {
                stk.emplace(a[i], tot - x + a[i]);
                tot = x;
            }
        }
        return stk.empty();
    };

    int l = 0, r = inf, res = -1;
    for (int mid; l <= r;) {
        mid = (l + r) / 2;
        if (check(mid)) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << (ll) res << "\n";
    return 0;
}

J. Jet Set

维度是没有用的。

如果在单次飞行中跨过的180 度，则一定是可行的。

否则，根据题目的要求，飞行过程中经过的经度实际上是确定的。我们只要标记即可。

最后判断有无没有被标记的点的即可。

#include <bits/stdc++.h>

using namespace std;


int32_t main() {
    int n;
    cin >> n;
    vector<int> a(n + 2), v(720);
    for (int i = 1, x; i <= n; i++) {
        cin >> x >> a[i];
        a[i] = (a[i] + 180) * 2;
    }
    a[n+1] = a[1];
    for (int i = 2, x, y; i <= n+1; i++) {
        x = a[i - 1], y = a[i];
        if (x > y) swap(x, y);
        if (y - x == 360) cout << "yes\n", exit(0);
        if (y - x < 360) {
            for (int j = x; j <= y; j++) v[j] = 1;
        } else {
            for (int j = 0; j <= x; j++) v[j] = 1;
            for (int j = y; j < 720; j++) v[j] = 1;
        }
    }
    for( int i = 0 ; i < 720 ; i ++ )
        if( v[i] == 0 ) cout << "no " << fixed << setprecision(1) << (0.5*i) - 180.0 << "\n", exit(0);
    cout << "yes\n";

    return 0;
}

K. Knitpicking

我们先尽可能的按照无法配对的情况去选择，最后在任意选一个即可配对，除非已经把所有的袜子全部选完。

如果袜子是任意的，则只有当无左无右的情况下，才能选择一个。否则要选择左右的较大值。

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const int N = 110;

void solve() {
    int n;
    cin >> n;
    map<string, array<int, 3> > mp;
    int z = 0;
    for (int i = 0; i < n; ++i) {
        string a, b;
        int x;
        cin >> a >> b >> x;

        if (b == "left") {
            mp[a][0] += x;
        } else if (b == "right") {
            mp[a][1] += x;
        } else {
            mp[a][2] += x;
        }
    }

    int res = 0, mark = 0;
    for (auto X: mp) {
        string a = X.first;
        z += mp[a][0] + mp[a][1] + mp[a][2];

        if (mp[a][0] == 0 && mp[a][1] == 0 && mp[a][2] > 0) res += 1;
        else res += max(mp[a][0], mp[a][1]);
    }

    if (res != z) {
        cout << res + 1 << '\n';
    } else cout << "impossible\n";

}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    while (_--) {
        solve();
    }
    return 0;
}