暑假集训 Nowcoder 多校 Round 4

比赛链接

---

F 「Election of the King」

签到题，每次淘汰的候选人要么是最左的，要么是最右的，因此用两个变量维护两端的索引，逐步向中间移动。

每一轮选举使用二分查找来得到两人的票数，将得票高的一方淘汰即可。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

每一轮循环也可以只看中间的人来判断谁被淘汰，可以将时间复杂度优化到 \(O(n)\)

#include <iostream>
#include <algorithm>

#define MAX_N 1000005

using i64 = long long;

struct {
    i64 v;
    int idx;
} a[MAX_N];


void solve() {
    int n;
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i].v;
        a[i].idx = i;
    }
    std::sort(a, a + n, [](auto& a1, auto& a2) {
        return a1.v < a2.v;
    });

    int left = 0, right = n - 1;
    while (left < right) {
        int l = left, r = right;
        // 2 * a[l].v <= a[left].v + a[right].v
        // 2 * a[r].v > a[left].v + a[right].v
        i64 x = a[left].v + a[right].v;
        if (2 * a[r].v <= x) {
            right--;
            continue;
        }
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (2 * a[mid].v <= x) {
                l = mid;
            }
            else {
                r = mid;
            }
        }

        if (right - r + 1 > r - left) {
            left++;
        }
        else {
            right--;
        }
    }

    std::cout << a[left].idx + 1 << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    solve();

    return 0;
}

L 「We are the Lights」

因为后续的操作会覆盖之前的操作，所以从后往前遍历所有操作，操作过的行和列会被锁住且后续无法再修改，同时用两个变量 r 、c 分别维护未被锁住的行数和列数，若当前操作为 row x on 且 x 行未上锁，则当前开灯总数增加 c ，r 自减 1，对于其他三种情况，同理分析即可。

时间复杂度：\(O(q)\)

空间复杂度：\(O(m + n + q)\)

#include <iostream>

#define MAX_NUM 1000005

using i64 = long long;

struct {
    std::string pos;    
    int val;
    std::string kind;
} op[MAX_NUM];

bool lockRow[MAX_NUM];
bool lockCol[MAX_NUM];

void solve() {
    int n, m, q;
    std::cin >> n >> m >> q;
    for (int i = 0; i < q; i++) {
        std::cin >> op[i].pos >> op[i].val >> op[i].kind;
    }
    int r = n, c = m; // 未被锁住的行列数
    i64 res = 0;
    for (int i = q - 1; i >= 0; i--) {
        if (op[i].kind == "on") {
            if (op[i].pos == "row") {
                if (lockRow[op[i].val]) continue;
                res += c;
                r--;
                lockRow[op[i].val] = true;
            }
            else {
                if (lockCol[op[i].val]) continue;
                res += r;
                c--;
                lockCol[op[i].val] = true;
            }
        }
        else {
            if (op[i].pos == "row") {
                if (lockRow[op[i].val]) continue;
                r--;
                lockRow[op[i].val] = true;
            }
            else {
                if (lockCol[op[i].val]) continue;
                c--;
                lockCol[op[i].val] = true;
            }
        }
    }

    std::cout << res << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    solve();

    return 0;
}

J 「Qu'est-ce Que C'est?」

假设 \(dp[i][s]\) 表示 \([0, i]\) 序列中最小后缀和为 \(s\) 的合法情况有多少种，可以得到状态转移方程： \[ \begin{equation} dp[i][s] = \begin{cases} \ \sum_{k = s - m} ^ m dp[i - 1][k] & s \geq 0 \\ \\ \ \sum_{k = - s} ^ m dp[i - 1][k] & s < 0 \end{cases} \end{equation} \] 根据状态转移方程，我们需要定义一个后缀数组来维护后缀和来优化时间，同时注意到 \(dp[i]\) 只与 \(dp[i - 1]\) 有关，所以可以使用滚动数组优化空间。

时间复杂度：\(O(nm)\)

空间复杂度：\(O(m)\)

#include <iostream>

#define MAX_M 5005

using i64 = long long;
const int mod = 998244353;

i64 dp[2][2 * MAX_M];
i64 sum[2][2 * MAX_M];

void solve() {
    int n, m;
    std::cin >> n >> m;
    for (int s = m; s >= -m; s--) {
        dp[0][m + s] = 1;
        sum[0][m + s] = (sum[0][m + s + 1] + dp[0][m + s]) % mod;
    }
    for (int i = 1; i < n; i++) {
        for (int s = m; s >= -m; s--) {
            if (s >= 0) {
                dp[i & 1][m + s] = sum[(i - 1) & 1][m + s - m];
            }
            else {
                dp[i & 1][m + s] = sum[(i - 1) & 1][m - s];
            }
            sum[i & 1][m + s] = (sum[i & 1][m + s + 1] + dp[i & 1][m + s]) % mod;
        }
    }

    std::cout << sum[(n - 1) & 1][0] << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    solve();

    return 0;
}

H 「Merge the squares!」

对于任意一个 \(n \times n\) 的正方形，如果 \(n < 8\) ，则可以一次性合并，若 \(n \geq 8\) ，我们考虑如下分割方式：

即将一个正方形分割为两个正方形与两个矩形，两个正方形的边长分别为 \(j\) 和 \(n - j\) ，通过枚举 \(j\) ，若两个 \((n - j) \times j\) 的矩形可以分割为不超过 24 个正方形，则总的正方形合并数不超过 50。经计算，发现对任意 \(n\) 满足 \(8 \leq n \leq 1000\) 都可以找到合法的 \(j\) 满足题意。

我们使用一个数组来维护每一个 \(n\) 的合法分割方案，然后使用递归来记录答案即可。

#include <iostream>
#include <functional>
#include <vector>
#include <array>

int splitGrid[1001];

void init() {
    // 得到所有可行的分割方案
    for (int i = 8; i <= 1000; i++) {
        for (int j = (i + 1) / 2; j < i; j++) {
            int a = j, b = i - j;
            int cnt = 0;
            while (b) {
                cnt += (a / b);
                a %= b;
                std::swap(a, b);
            }
            if (cnt <= 24) {
                splitGrid[i] = j;
                break;
            }
        }
        assert(splitGrid[i] > 0);
    }
}

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<std::array<int, 3>> ans;
    std::function<void(int, int, int, int)> merge = [&merge, &ans](int x1, int y1, int x2, int y2) -> void {
        if (x2 - x1 == y2 - y1) {
            int len = x2 - x1 + 1;
            if (len == 1) return;
            if (len <= 7) {
                ans.push_back({x1, y1, len});
                return;
            }
            int k = splitGrid[len];
            merge(x1, y1, x1 + k - 1, y1 + k - 1);
            merge(x1 + k, y1 + k, x2, y2);
            merge(x1, y1 + k, x1 + k - 1, y2);
            merge(x1 + k, y1, x2, y1 + k - 1);
            ans.push_back({x1, y1, len});
        }
        else {
            int len1 = x2 - x1 + 1, len2 = y2 - y1 + 1;
            if (len1 > len2) {
                merge(x1, y1, x1 + len2 - 1, y1 + len2 - 1);
                x1 += len2;
            }
            else {
                merge(x1, y1, x1 + len1 - 1, y1 + len1 - 1);
                y1 += len1;
            }
            merge(x1, y1, x2, y2);
        }
    };
    merge(1, 1, n, n);
    std::cout << ans.size() << '\n';
    for (const auto& [x, y, len] : ans) {
        std::cout << x << ' ' << y << ' ' << len << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    init();

    solve();

    return 0;
}