路人乙の小窝

我若安好，万事大吉

0%

Codeforces Round 996 (Div. 2)

发表于 分类于

前言

寒假的第一场Codeforces，库库掉分……

赛时过了A、B，赛后补了C、D

题目链接

A. Two Frogs

算法标签：games、greedy

题目大意

Alice和Bob是两只青蛙，可以轮流向左或向右跳，谁没有地方可以跳了谁就输了。

题目思路

Alice向右Bob方向跳一步之后，如果他们之间没有空余的荷叶，则Bob只能往一个方向跳，最终被挤下去；如果他们之间还有一个格子，则Bob会反过来朝Alice跳，最终将Alice挤下去……推出结论：当Alice和Bob之间的空余荷叶数为偶数时，Alice获胜，否则Bob获胜

1
2
3
4
5
6
void solve() {
    cin >> n >> a >> b;
    string ans = (a - b) & 1 ? "NO" : "YES";
    cout << ans << '\n';
    return;
}

B. Crafting

算法标签：greedy, sortings

题目大意

你需要n种材料，其中第i种需要b[i]个，你已经有a[i]个。你可以执行操作：对于第i种材料，将除这种材料以外的所有的材料（各一份）置换成这种材料（一份），求执行任意次操作后能否得到足够数量的材料。

题目思路

因为执行操作后会减少其他所有种类的材料，所以若同时有两种或更多的材料不足b[i]，那么永远无法获得足够的材料。

遍历1~n，找到满足a[j] < b[j]的所有j（若j > 1输出NO并return），同时记录所有i（i != j）的a[i] - b[i]的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];
    int value = 0, minn = 1e9 + 2;

    for(int i = 1; i <= n; ++i) {
        if(a[i] < b[i]) {
            if(value != 0) {
                cout << "NO\n";
                return;
            }
            value = b[i] - a[i];
        } else minn = min(minn, a[i] - b[i]);
    }

    if(minn < value) cout << "NO\n";
    else cout << "YES\n";
}

优化

赛后看到标签里有sortings，想到确实将材料按a-b排序后会有更优的时间复杂度

（但是代码没写）

C. The Trail

算法标签：constructive algorithms、greedy、math

题目大意

有一个n*m的矩阵，一条从(1, 1)到(n, m)的只包含向下和向右的路径，修改路径上的数字使得每行、每列的值的和都相等。

题目思路

  1. 赛时思路（赛时没做出来）：根据每行每列值的和为固定值列出线性方程组，用高斯消元求解
  2. 赛后：找到一点神奇的小性质

根据每行每列值的和相等，假设这个和为s，则有ns = ms，观察得到s为0时等式始终成立。

对于路径上的每个结点，如果它下一步向下走，则他所在行除它以外的所有值是已知的，包括他所在的所有值的和是已知的，则可以求出该点的值。同理，如果它向右走，可以根据它所在列的已知条件求出取值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void solve() {
    cin >> n >> m >> path;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            cin >> G[i][j];
        }
    }

    path += 'D';
    for(int i = 0, x = 1, y = 1; i <= n + m - 1; ++i) {
        if(path[i] == 'D') {
            for(int j = 1; j <= m; ++j) {
                if(x == j) continue;
                G[y][x] -= G[y][j];
            }
            ++y;
        } else {
            for(int j = 1; j <= n; ++j) {
                if(y == j) continue;
                G[y][x] -= G[j][x];
            }
            ++x;
        }
    }

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            cout << G[i][j] << ' ';
        }
        cout << '\n';
    }
    return;
}

赛时Gaussian，赛后guess

D. Scarecrow

算法标签：greedy，binary search

题目大意

稻草人可以向左或向右移动（一秒一格），初始位置为0的乌鸦会移动到坐标不大于它的最近的稻草人的右边k个位置，求乌鸦移动到位置l的最短时间的两倍。

题目思路

  1. 最左边的稻草人会向左移动，直到移动到0，乌鸦进行第一次移动。
  2. 稻草人移动到乌鸦左边后稻草人只能向右移动，相当于乌鸦第一次移动之后每秒向右移动一格
  3. 乌鸦每次传送到位置pos后，记录已经经过的时间，对于下一只稻草人：
    1. 如果稻草人初始位置x小于pos，他应该尽量移动到pos的位置，乌鸦下次传送到的位置为min(x+time, pos) + k;
    2. 如果稻草人初始位置x大于pos，他应该尽量移动到pos的位置，若：
      1. 移动之后稻草人位置与pos仍相隔一段距离，则稻草人和乌鸦分别向中靠拢。更新时间与乌鸦位置
      2. 若稻草人可以移动到pos，则直接更新乌鸦位置。
  4. 注意最终输出时间的两倍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void solve() {
    cin >> n >> k >> l;
    double curpos = 0, time = 0;
    int x = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> pos[i];
    }

    curpos = k;
    time = pos[++x] * 2;
    while(curpos < l) {
        if(x == n) {
            time += (l - curpos) * 2;
            break;
        }

        else if(pos[++x] <= curpos) {
            curpos = min(pos[x] + time / 2, curpos) + k;
        }
        
        else if(pos[x] - time / 2 <= curpos) {
            curpos += k;
        }

        else {
            double dis = pos[x] - time / 2 - curpos;
            time += dis;
            curpos = curpos + dis / 2 + k;
        }
    }

    cout << (int)time << '\n';
}

优化

题目标签里有二分查找，但是我没有想到二分的方法(咕咕咕)

我很可爱，请给我钱qwq