本场链接

A. Find K Distinct Points with Fixed Center

• 当 \( k \) 为奇数时, 先输出 \( x_c \) , \( y_c \) , 转换为 \( k \) 为偶数的情况.
• 当 \( k \) 为偶数时, 输出 \( k/2 \) 对在 \( (x_c,y_c) \) 两侧的对称的点即可, exp: \( (x_c + 1,y_c), (x_c – 1, y_c), \dots , (x_c + k / 2,y_c), (x_c – k / 2,y_c) \) .

B. Minimize Equal Sum Subarrays

我们对于每一个小于 \( n \) 的 \( p_i \) 加一, 然后对于 \( n \) , 设为 \( 1 \) .

考虑对于 \( p, q \) 的区间和的差值, 对于任意一不为 \( 1\sim n \) 的区间, 区间内每个 \( p_i \neq n \) 的值贡献了 \( +1 \) , 而 \( p_i = n \) 的值贡献了 \( -n + 1 \) , 故只有 \( 1\sim n \) 的区间才能满足相等.

C. Perform Operations to Maximize Score

显然, 每次 \( a_i = a_i + 1 \) 最多会让结果 \( +1 \), 故可以尽可能的让最大的可 \( +1 \) 的值 \( +1 \), 然后加上剩下的中位数.

考虑使得中位数最大的情况, 那我们首先一定会选择 \( a \) 中最大的数先拿出来, 然后中位数的最大值可以二分, check 能有多少数最后 \( \geq \) 你要的中位数.

D. Determine Winning Islands in Race

Bessie 一次只能向前走一, 而 Elsie 可以通过 alternative bridges 来实现跳跃.

我们考虑什么情况 Bessie 是稳赢的:

• Bessie 一开始就在 \( 1 \), 先手直接把 Elsie 搞淘汰了.
• Bessie 在 \( n – 1 \), 比赛刚开始就结束了.
• Bessie 到 \( s \sim n – 1 \) 的时间都早于 Elsie.

第一和第二种情况很好搞, 那我们思考如何表示第三种情况呢?

首先 Bessie 在 \( s \) 时, 我们可以 dp 求出 Elsie 在用 \( s \) 之前的点能走到 \( i \) 的最短时间 \( dp[i] \) , 那么 Bessie 输就得有 \( dp[i] < i – s \), 转换一下就是 \( i – dp[i] > s \). 那我们维护 \( i – dp[i] \) 最大值, 然后每次判断一下和 \( s \) 的大小关系即可.

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> gra(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        gra[u].push_back(v);
    }
    vector<int> dp(n + 1, INF);
    vector<int> ans(n);
    dp[1] = 0;
    ans[1] = 1;
    ans[n - 1] = 1;
    int maxx = 0;
    for (int i = 1; i < n - 1; i++) {
        if (dp[i + 1] > dp[i] + 1) {
            dp[i + 1] = dp[i] + 1;
            maxx = max(maxx, i + 1 - dp[i + 1]);
        }
        for (auto v : gra[i]) {
            if (dp[v] > dp[i] + 1) {
                dp[v] = dp[i] + 1;
                maxx = max(maxx, v - dp[v]);
            }
        }
        // s == i + 1
        if (maxx > i + 1)
            ans[i + 1] = 0;
        else
            ans[i + 1] = 1;
    }
    for (int i = 1; i < n; i++) cout << ans[i];
    cout << '\n';
}