A. Two Frogs

当两个青蛙之间的距离为 \(1\) 时，此时先跳的青蛙最终会被逼到角落。

不难发现，两个青蛙跳跃的次数相同时，它们之间距离的奇偶性是不变的。因此，若两青蛙初始距离为奇数，则它们距离为 \(1\) 时 \(Alice\) 先跳。若两青蛙初始距离为偶数，此时 \(Alice\)，先跳一次，情况转变成 \(Bob\) 先手，并且它们之间的距离为奇数，所以当距离为 \(1\)，时，\(Bob\) 先跳。

code:

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
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n, a, b;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n >> a >> b;
        
        int x = abs(a - b);
        if (x % 2) cout << "NO" << endl;
        else cout << "YES" << endl;
    }

    return 0;
}

B. Crafting

对于两个不同的元素 \(a[i],a[j]\)，经过若干次操作后，它们不可能同时增加。因此，只需要找到其中一个 \(i\) 满足\(a[i] < b[i]\)，让 \(a[i] = b[i]\)，并且其他元素加上 \(b[i]-a[i]\)，此时判断整个数组是否满足所有的 \(a[i] >= b[i]\) 即可。

时间复杂度 \(O(n)\)

code:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n;
int a[N], b[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];
        
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (a[i] < b[i])
            {
                cnt = b[i] - a[i];
                a[i] = b[i] + cnt;
                break;
            }
        
        bool flag = false;
        for (int i = 0; i < n; i++)
        {
            if (a[i] - cnt < b[i])
            {
                flag = true;
                break;
            }
        }
        
        if (!flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

C. The Trail

题目要求矩阵的每一行以及每一列的和都相等，设和为 \(x\)，则整个矩阵的和可以表示为 \(n*x\)，也可以表示成 \(m*x\)，可以列出等式 \(n*x=m*x\)，解得 \(x=0\)。

对于路径填空，可以先统计出每一行和每一列的暂时的和，接下来跟着路径走。若 \(s[i]='D'\)，则下一步要往下走，此时当前行只剩下脚下方格就填满了，若 \(s[i]='R'\)，则下一步要往右走，此时当前列只剩下脚下方格。计算出脚下方格的值后，更新当前行和列的和。

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

code:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int T;
int n, m;
int a[N][N];
string s;
int row[N], col[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n >> m >> s;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cin >> a[i][j];
        
        for (int i = 1; i <= n; i++) 
        {
            row[i] = 0;
            for (int j = 1; j <= m; j++) row[i] += a[i][j];
        }
        for (int i = 1; i <= m; i++)
        {
            col[i] = 0;
            for (int j = 1; j <= n; j++) col[i] += a[j][i];
        }
        
        int r = 1, c = 1, x = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == 'D')
            {
                a[r][c] = x - row[r];
                row[r] += a[r][c];
                col[c] += a[r][c];
                r++;
            }
            else
            {
                a[r][c] = x - col[c];
                row[r] += a[r][c];
                col[c] += a[r][c];
                c++;
            }
        }
        a[r][c] = x - col[c];
        
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++) cout << a[i][j] << ' ';
            cout << endl;
        }
    }

    return 0;
}

D. Scarecrow

模拟。

由于答案一定是整数，因此为了避免小数点，可以把所有的距离长度都乘 \(2\)，这样每走 \(1\) 距离相当于走 \(0.5\)。

首先计算出乌鸦的真正初始位置，即第一个稻草人移动到位置 \(0\)，使乌鸦传送到 \(t\)。

接下来对于之后的每个稻草人，都需要分类讨论，假设花费 \(time\) 的时间，乌鸦的最大位置是 \(pos\)。

  • 若 \(a[i] <= pos\)，代表当前稻草人在乌鸦左边，可以把稻草人的位置更新为 \(a[i] = min(a[i]+time,pos)\)，此时稻草人的位置才是真正的位置，为了让乌鸦能够被稻草人传送，可以让乌鸦往左 \(pos-a[i]\) 个单位，乌鸦最终将会被传送到 \(a[i] + k\)。
  • 若 \(a[i] > pos\)，代表当前稻草人在乌鸦右边，可以把稻草人的位置更新为 \(a[i] = max(a[i] - time, pos)\)，为了让乌鸦能够被传送，需要乌鸦和稻草人彼此向对方靠近，需要花费 \((a[i]-pos)/2\)的时间，乌鸦会被传送到 \(pos + (a[i] - pos) / 2 + k\)。

当乌鸦的最终距离小于目的地时，可以不断地让最后一个稻草人向右推着乌鸦走。

时间复杂度 \(O(n)\)

code:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 200010;

int T;
int n, k, p;
int a[N];

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> k >> p;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        k *= 2, p *= 2;
        for (int i = 0; i < n; i++) a[i] *= 2;
        
        int res = a[0], idx = k;
        for (int i = 1; i < n; i++) 
        {
            if (a[i] > idx) 
            {
                a[i] = max(idx, a[i] - res);
                int t = (a[i] - idx) / 2;
                res += t;
                idx += t + k;
            } 
            else 
            {
                a[i] = min(idx, a[i] + res);
                idx = a[i] + k;
            }
        }

    if (idx < p) res += p - idx;
        
        cout << res << endl;
    }

    return 0;	
}