得分情况

预计得分：\(100 + 100 + 0 \sim 100 = 200 \sim 300\)。

实际得分：\(100 + 100 + 60 = 260\)。

考场上

开 T1，题目有点难读懂，读了一遍放过去了。

开 T2，读了一遍题感觉需要的用到二分答案，这是一个 log，check 里可能需要用到 upper_bound 或者 lower_bound，共两个 log，没思路了，过。

开 T3，严格次短路，不会，写玄学算法希望多骗点分。

回去看 T1，看懂了题，发现是个 sb 题。写完 T1，在想暴力怎么写，写出来了暴力，拍上了。去想 T2。

感觉需要个 DP，想 DP 怎么写，大样例来了，T1 过了大样例就不拍了，T2 想了一个不知道对错的 DP，过了大样例。

写了个暴力，然后对拍，出了两次锅，一次是造数据的锅了，一次是暴力输入顺序反了。。

T1咒语

每一位是独立的，我们要让每一位的差异尽量小，那么就判断这一位 \(0\) 和 \(1\) 的个数关系即可。

时间复杂度：\(O(nL)\)。

Code：

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 1001

int n, len, num[MAXN][2];
std::string s;

int main() {
    //freopen("curse.in", "r", stdin);
    //freopen("curse.out", "w", stdout);
    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        std::cin >> s;
        len = s.length();
        for (int j = 0; j < len; ++j) {
            ++num[j][s[j] - '0'];
        }
    }
    for (int i = 0; i < len; ++i) {
        if (num[i][0] >= num[i][1]) putchar('0');
        else putchar('1');
    }
    puts("");
    //fclose(stdin), fclose(stdout);
    return 0;
}

T2 神光

由

使得 \(L\) 最小

感觉需要用二分答案。

遇到了怎么 check 的难题。

不知道怎么就想到 DP 上了。

设 \(f_{i,j}\) 表示用了 \(i\) 次红光，\(j\) 次绿光，下一次在使用某一种光的最远的左端点是哪里。

伪代码：

f[0][0] = 最左边的法坛

在已知左端点的时候能够很容易推出下次的左端点。

伪代码:

f[i][j] = max(upper_bound(排好序的法坛，f[i - 1][j] + x - 1)，upper_bound(排好序的法坛，f[i][j - 1] + 2 * x - 1)

时间复杂度：\(O(n^2log^2n)\)。

Code：

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 2222

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int n, r, g, a[MAXN];
int f[MAXN][MAXN];

bool check(int x) {
    int s1 = min(n, r), s2 = min(n, g);
    f[0][0] = a[1];
    int stp = min(n, s1 + s2);
    for (int k = 1; k <= stp; ++k) {
        int stop = min(s1, k);
        for (int i = 0; i <= stop; ++i) {
            int j = k - i;
            if (j > s2) continue;
            if (i == 0) {
                int pos = std::upper_bound(a + 1, a + n + 1, f[i][j - 1] + 2 * x - 1) - a;
                if (pos > n) { f[i][j] = a[n + 1]; return true; }
                else f[i][j] = a[pos];
            }
            else if (j == 0) {
                int pos = std::upper_bound(a + 1, a + n + 1, f[i - 1][j] + x - 1) - a;
                if (pos > n) { f[i][j] = a[n + 1]; return true; }
                else f[i][j] = a[pos];
            }
            else {
                int pos = max(std::upper_bound(a + 1, a + n + 1, f[i][j - 1] + 2 * x - 1) - a, std::upper_bound(a + 1, a + n + 1, f[i - 1][j] + x - 1) - a);
                if (pos > n) { f[i][j] = a[n + 1]; return true; }
                else f[i][j] = a[pos];
            }
        }
    }
    bool okay = false;
    for (int i = 0; i <= s1; ++i) {
        if (i > stp) break;
        if (stp - i > s2) continue;
        if (f[i][stp - i] > a[n]) okay = true;
    }
    return okay;
}

int main() {
    scanf("%d %d %d", &n, &r, &g);
    for (int i = 1; i <= n ; ++i) scanf("%d", &a[i]);
    std::sort(a + 1, a + n + 1);
    a[n + 1] = 2147483647;
    if (r + g >= n) {
        puts("1");
        fclose(stdin), fclose(stdout);
        return 0;
    }
    int lft = 1, rght = a[n];
    while (lft <= rght) {
        int mid = (lft + rght) >> 1;
        if (check(mid)) rght = mid - 1;
        else lft = mid + 1;
    }
    std::cout << lft << '\n';
    return 0;
}

T3 迷宫