A. Catch the Coin

不难发现，只有硬币的 \(y\) 坐标大于等于 \(-1\) 时，\(Monocarp\) 才有可能收集到该硬币

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int x, y;

signed main()
{
    cin >> T;
    while (T--)
    {	
        cin >> x >> y;
        
        if (y >= -1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

B. Substring and Subsequence

转化题意，只需计算出 \(b\) 中 能够作为 \(a\) 的子序列的最长子串 \(k\)，包含 $ $ 作为子字符串和 \(b\) 作为子序列的字符串的最小可能长度即为 \(a.size()+k.size()\)

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
string a, b;

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> a >> b;
        
        int res = 0;
        for (int i = 0; i < b.size(); i++)
            for (int j = 0, k = i; j < a.size() && k < b.size(); j++)
            {
                if (a[j] == b[k]) k++;
                if (j == a.size() - 1 || k == b.size()) res = max(res, k - i);
            }
            
        cout << a.size() + b.size() - res << endl;
    }

    return 0;
}

C. Two Movies

对于 \(a[i]\) 和 \(b[i]\)，它们的组合有以下几种情况：

  • \(a[i]=1,b[i]\neq1\)，该观众给第一步电影留下评价最佳
  • \(a[i]\neq1,b[i]=1\)，该观众给第二部电影留下评价最佳
  • \(a[i]=1,b[i]=1\)，该观众留下的评价一定是正面评价，先不做选择，记为 \(cnt++\)
  • \(a[i]=-1,b[i]=-1\)，该观众留下的评价一定是负面评价，先不做选择，记为 \(cnt--\)

\(cnt\) 即为可以让两个电影的评价增加的值

每个观众都操作过后，为了使两部电影的最低评分最大，需要使用 \(cnt\) 对两部电影的评分进行操作，使得两个评分最接近，这时两部电影的最低评分最大

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

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

signed main()
{
    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 r1 = 0, r2 = 0, c1 = 0, c2 = 0;
        for (int i = 0; i < n; i++)
        {
            if (a[i] == 1 && b[i] == -1) r1++;
            if (a[i] == -1 && b[i] == 1) r2++;
            if (a[i] == 1 && b[i] == 1) c1++;
            if (a[i] == -1 && b[i] == -1) c2++;
        }
        
        for (int i = 0; i < c1; i++)
        {
            if (r1 <= r2) r1++;
            else r2++;
        }
        for (int i = 0; i < c2; i++)
        {
            if (r1 >= r2) r1--;
            else r2--;
        }
        
        cout << min(r1, r2) << endl;
    }

    return 0;
}

D. Smithing Skill

最优策略显然是制造完一件武器后立刻熔化，每操作一次贡献 \(+2\)

设\(best[i]\) 表示为用最多 \(i\) 块金属锭 制作并熔化一个武器所消耗金属锭的最小值，可以用双指针维护

设\(f[i]\) 为 用 \(i\) 块金属锭能够获得的最大经验值，考虑用 \(dp\)，递推公式为： \(f[i]=f[i-best[i]]+2\)

接下来遍历数组 \(c\)：

  • \(c[i]<=1e6\)，对答案的贡献就是 \(f[c[i]]\)
  • \(c[i]>1e6\)，对于大于\(1e6\)的部分，不难发现，每制作并熔化一个武器所消耗的金属锭最小值为 \(best[1e6]\)，因此，可以先处理大于\(1e6\) 的部分对答案的贡献，为 \((\frac{c[i]-1e6-1}{best[1e6]}+1)\times 2\)，再使用\(f\)数组处理小于等于 \(1e6\) 的部分即可

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

#define int long long
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1000010;

int T;
int n, m;
int a[N], b[N], c[N];
int best[N], f[N];

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < m; i++) cin >> c[i];

    map<int, int> p;
    for (int i = 0; i < n; i++)
    {
        if (!p.count(a[i])) p[a[i]] = 1e9;
        p[a[i]] = min(p[a[i]], a[i] - b[i]);
    }

    int last = 0;
    auto it = p.begin();
    for (int i = 1; i < N; i++)
    {
        if (it != p.end() && it -> x == i) 
        {
            if (it -> y < last || !last) last = it -> y;
            it++;
        }
        best[i] = last;
    }
    for (int i = 1; i < N; i++) 
        if (best[i]) f[i] = f[i - best[i]] + 2;

    int res = 0;
    for (int i = 0; i < m; i++)
    {
        if (c[i] >= N)
        {
            res += ((c[i] - N) / last + 1) * 2;
            c[i] = N + (c[i] - N) % last - last;
        }
        res += f[c[i]];
    }

    cout << res << endl;

    return 0;
}

E. Distance to Different

通过观察发现

当序列中间有两个相同元素相邻时，例如 \(1,2,2,3\)，将这两个相同的元素替换成两个不同的元素不影响答案，只有两个相同元素出现在头或尾，才不能被替换，因此，序列中间连续相同的元素块长度大于 \(2\) 时，对答案才有意义

对于序列中间每个块，里面的值是什么并不影响答案，因此，可以把题意转化为把数组分为 \(k\) 块，并且中间连续相同元素块长度大于 \(2\)，可以用 \(dp\) 来完成操作

设 \(f[i][j]\) 为 前 \(i\) 个元素，分割成 \(j\) 个块的方案数，\(sum[i][j]\)，为不超过 \(i\) 个元素，分割成 \(j\) 块的方案数

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

#define int long long

using namespace std;

const int N = 200010, mod = 998244353;

int n, k;
int f[N][15], sum[15];

signed main()
{
    cin >> n >> k;

    sum[0] = f[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            f[i][min(j + 1, k)] = (f[i][min(j + 1, k)] + sum[j]) % mod;
            if (i > 2 && i < n) f[i][min(j + 1, k)] = (f[i][min(j + 1, k)] - f[i - 2][j] + mod) % mod;
        }
        for (int j = 0; j <= k; j++) sum[j] = (sum[j] + f[i][j]) % mod;
    }

    cout << f[n][k] << endl;

    return 0;
}