赛后vp，碰到\(C\)想半天没想出来，直接昏了（x

A. Two Frogs

博弈，Alice和Bob在长为\(n\)的地方玩，每回合可以向左/向右跳，不能跳出范围或者跳到有人的地方，且不能不动，Alice先手，谁不能跳了谁就输了。

很显然和两人间距离奇偶性有关：当两人一开始距离偶数时，Alice向Bob方向走，那无论Bob怎么走接下来还是回到距离为偶数，Alice总可以继续走。所以这样Alice必胜；同理距离奇数先手必败。

Code：

void solve() {
    int n;
    cin >> n;
    int a, b;
    cin >> a >> b;
    if ((a - b) % 2 == 0) {
        cout << "YES" << '\n';
    } else {
        cout << "NO" << '\n';
    }
}

B. Crafting

有\(n\)种材料，每种材料有\(a_i\)个。

有种操作可以将某一种材料数量\(+1\)，但其他材料数量\(-1\)。

现在问是否可以通过任意次操作使得每种材料不少于\(b_i\)个。

很显然，我们先让\(a + 1\)然后让\(b + 1\)，得到的结果是一定劣于啥也不干的。也就是说我们最多将一种材料数量增加，且最多增加的数量就是其他材料多的数量的最小值。

Code：

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &i : a) cin >> i;
    for (auto &i : b) cin >> i;
    int needtoadd = -1, maxtocut = INF;
    for (int i = 0; i < n; i++) {
        if (a[i] < b[i]) {
            if (needtoadd == -1) {
                needtoadd = b[i] - a[i];
            } else {
                cout << "NO" << '\n';
                return;
            }
        } else {
            maxtocut = min(maxtocut, a[i] - b[i]);
        }
    }
    if (needtoadd > maxtocut) {
        cout << "NO" << '\n';
    } else {
        cout << "YES" << '\n';
    }
}

C. The Trail

有\(n \times m\)的一个图，有一条给定的从左上角到右下角的路径的权值未指定，其他每个点都有一个权值。

现在要求给路径填数，使得每行每列的和都为同一个数。

不妨设这个数为\(x\)，那整个图的和可以表示为\(x \times n\)或者\(x \times m\)，那么\(x \times n = x \times m\)，也就是\(x\)应该等于\(0\)（\(n \neq m\)）。

那我们就钦定每行每列都是\(0\)。

发现当走一步后，一定有一行/一列是只剩一个未知量的，根据行/列和为\(0\)求出来即可。

对于最后一个未知量，则根据行或者列来确定，可以证明这样之后行和列一定满足条件：

不妨保证列的和为\(0\)，那么总和为\(0\)，其他行的和也为\(0\)，那么最后一行为\(0\)。

Code:

void solve() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<vector<LL>> gra(n, vector<LL>(m));
    for (auto &i : gra) {
        for (auto &j : i) cin >> j;
    }
    int nowx = 0, nowy = 0;
    s += 'D';
    for (auto i : s) {
        if (i == 'D') {
            LL sum = 0;
            for (int i = 0; i < m; i++) {
                sum -= gra[nowx][i];
            }
            gra[nowx][nowy] = sum;
            nowx++;
        } else {
            LL sum = 0;
            for (int i = 0; i < n; i++) {
                sum -= gra[i][nowy];
            }
            gra[nowx][nowy] = sum;
            nowy++;
        }
    }
    for (auto i : gra) {
        for (auto j : i) {
            cout << j << ' ';
        }
        cout << '\n';
    }
}

D. Scarecrow

题意有点长不想翻译了，直接写题解罢（

可以贪心的想：

从前到后一个个考虑稻草人，维护一个值\(now\)表示现在时刻。

第一个稻草人一定得先到\(0\)然后乌鸦到\(k\)。

然后考虑其他稻草人，当这个稻草人在乌鸦当前地点的右面时，一定会向左移动来接乌鸦，这个花费的时间易得，用这个更新\(now\)和乌鸦地点。

要不然就是稻草人在乌鸦当前地点的左面，那么就向右移动最多到乌鸦所在地，根据这个更新乌鸦地点。

最后是没有稻草人了，就根据剩下距离更新\(now\)即可。

遍历稻草人的时候时刻注意乌鸦位置，到终点记得break。

Code：

void solve() {
    int n, k, p;
    cin >> n >> k >> p;
    p *= 2;
    k *= 2;
    int now = 0;
    int pp = 0;
    vector<int> arr(n);
    for (auto &i : arr) cin >> i;
    for (int i = 0; i < n; i++) {
        auto x = arr[i];
        x *= 2;
        if (i == 0) {
            now = x;
            pp = k;
        } else {
            if (x > pp) {
                if (x - now > pp) {
                    int add = (x - now - pp) / 2;
                    now += add;
                    pp += add;
                }
                pp += k;
            } else {
                int maxx = min(pp, x + now);
                pp = max(maxx + k, pp);
            }
        }
        if (pp >= p)
            break;
        if (i == n - 1) {
            now += p - pp;
        }
    }
    cout << now << '\n';
}