Educational Codeforces Round 167 (Rated for Div. 2)

发表于 分类于 ，

Educational Codeforces Round 167 (Rated for Div. 2)

Complete problemset

A. Catch the Coin

题意

有一个硬币从天而降，位置在(x,y)，你的位置在(0,0)

每秒钟

  • 你可以每秒移动一个单元格。
  • 然后硬币的y减少1。

问是否能抓到硬币

思路

只要你的y位置不小于-1，是可以抓到硬币的。

代码

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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    int x, y;
    cin >> x >> y;
    if (y<-1) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

B. Substring and Subsequence

题意

给您两个字符串 $a$ 和 $b$ ，它们都由小写拉丁字母组成。

您的任务是计算包含作为子字符串的 $a$ 和作为子序列的 $b$ 的字符串的最小可能长度。

思路

枚举b的后缀，在a中的子序列长度。

代码

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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    string s, t;
    cin >> s >> t;
    int m = s.length(), n = t.length();
    int ans = n+m;
    for (int i=0; i<n; i++) {
        int p = 0, j;
        for (j=i; j<n; j++,p++) {
            while (p<m && s[p] != t[j]) p++;
            if (p == m) {
                break;
            }
        }
        // cout << i << " " << j << endl;
        ans = min(ans, n+m-(j-i));
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

C. Two Movies

题意

一个公司发行了 $ 2 $ 部电影。现在有 $ n $ 位观众，你需要给每个人推荐一部公司的电影。已知每位观众对两部电影的评价均为好评、中立和差评中的其中一个。

关于各类评价：
好评：总评分 $ +1 $
中立：总评分不变
差评：总评分 $ -1 $

如何分配给每个观众两部电影中的其中一部从而使总评分最高？

输入

第一行一个整数 $ t (1 ≤ t ≤ 10^4) $ ，代表输入数据的组数。
接下来的每组数据，第一行一个整数 $ n (1 ≤ n ≤ 2 * 10 ^ 5) $ ，含义如题目所示；
第二行 $ n $ 个整数，代表每位观众对第一部电影的评价（ $ -1 ≤ a_i ≤ 1 $ ）；
第三行 $ n $ 个整数，代表每位观众对第二部电影的评价（ $ -1 ≤ a_i ≤ 1 $ ）。

每组数据的 $ n $ 的和不会超过 $ 2 * 10 ^ 5 $ 。

输出

一行一个整数，代表该公司能获得的最高总评分。

思路

对于$a_i \ne b_i$ 选择较大者，为了让二者最小值最大。

否则，对于$a_i = b_i$我们可以得到负/正面评价的个数。

我们需要枚举分配这些个数，然后维护最小值。

代码

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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto& i:a) cin >> i;
    for (auto& i:b) cin >> i;
    int l = 0, r = 0, x = 0, y = 0;
    for (int i=0; i<n; i++) {
        if (a[i] > b[i]) {
            x+=a[i];
        } else if (a[i] < b[i]) {
            y+=b[i];
        } else {
            if (a[i]<0) l--;
            if (a[i]>0) r++;
        }
    }
    int ans = -1e9;
    for (int i=l; i<=r; i++) {
        ans = max(ans, min(x+i, y+(l+r-i)));
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

D. Smithing Skill

题意

您正在玩一款著名的电脑游戏（可以正常运行），在这款游戏中，您可以提升各种技能的等级。今天，你的重点是 “铸造 “技能。你的战术显而易见：用金属锭锻造武器，然后将其熔化，部分返回材料。简单来说，每制造一件物品，你就能获得 $1$ 点经验值，而每熔化一件物品，你也能获得 $1$ 点经验值。

可以锻造的武器有 $n$ 种，金属锭有 $m$ 种。

花费 $a_i$ 个同类金属锭，你可以打造一把 $i$ 类的武器。熔化一件 $i$ （你之前制作的） $i$ （你之前制作的）等级的武器会为你带来 $b_i$ 个金属锭。

你有 $c_j$ 块 $j$ （th）类型的金属锭，而且你知道你可以用任何金属类型制作任何类型的武器。武器等级和金属类型的每种组合都可以使用任意次数。

制作和熔炼武器最多可以获得多少经验值？

输入

第一行包含两个整数 $n$ 和 $m$ （ $1 \le n, m \le 10^6$ ）–武器种类和金属类型的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^6$ )，其中 $a_i$ 是锻造一件 $i$ 类武器所需的金属锭数量。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ （ $0 \le b_i < a_i$ ）。( $0 \le b_i < a_i$ )，其中 $b_i$ 是你熔化一件之前锻造的 $i$ （三）级武器后返回的钢锭数量。

第四行包含 $m$ 个整数 $c_1, c_2, \dots, c_m$ （ $1 \le c_j \le 10^9$ ）–你拥有的相应金属类型的金属锭数量。

输出

打印一个整数 - 通过反复锻造和熔化武器可以获得的最高经验值。

注

在第一个示例中，您可以执行以下操作：

  1. 用 $1$ -st金属类型制作一件 $1$ -st类武器，花费 $9$ 块金属锭；
  2. 熔化该武器，返回 $8$ 块 $1$ （st）金属类型的金属锭；
    再次，用 $1$ （st）金属类型制作并熔化一件 $1$ （st）类武器；
    从 $1$ （st）金属类型中制作并熔化一件 $3$ （rd）类武器；
    从 $3$ （rd）金属类型中制作并熔化一件 $3$ （rd）类武器
    从 $1$ -st金属类型中制作并熔化一件 $4$ -th类武器
    用 $3$ -rd金属类型制作并熔化一件 $5$ -th类武器；

最后，你会剩下 $c = [2, 4, 2]$ 块金属锭。总共制作了 $6$ 件武器，熔炼了 $6$ 件武器，获得了 $12$ 点经验值。

思路

每种金属锭的计算是独立的。

设$f_x$为金属锭个数为x时，损失的的最小金属锭个数。

$mx = \max a_i \le 1e6$
我们预处理$f_{a_i} = a_i - b_i$，其余$\infty$。
花费$O(mx)$时间可以得到$f$

对于某种金属锭有x个。在$x\le mx$个数时，每一次可以得到最优决策$x$个变为$x-f_x$个，并获取2点经验。否则，$x$始终迭代为$x-f_{mx}$直到$x<mx$。
如果暴力计算会超时，需要公式计算迭代次数，设迭代k次，那么$x-k\times f_{mx} \le mx \Rightarrow k \ge \frac{x-mx}{ f_{mx} }$
k为整数，所以需要$k \ge \lceil \frac{x-mx}{ f_{mx} }\rceil$，k次迭代共计2k经验值。

代码

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
73
74
75
76
77
78
79
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    int n, m;
    cin >> n >> m;
    vector<ll> a(n), b(n), c(m);
    for (auto& i:a) cin >> i;
    for (auto& i:b) cin >> i;
    for (auto& i:c) cin >> i;
    int mx = *max_element(a.begin(), a.end());
    vector<ll> f(mx+1, 1e9), v(mx+1);
    for (int i=0; i<n; i++) {
        f[a[i]] = min(f[a[i]], a[i]-b[i]);
    }
    for (int i=1; i<=mx; i++) {
        f[i] = min(f[i], f[i-1]);
    }
    for (int i=1; i<=mx; i++) {
        if (i>=f[i])
        v[i] = v[i-f[i]]+2;
    }
    // cout << a << b << c << f << v << endl;
    ll ans = 0;
    for (int i:c) {
        if (i > mx) {
            // i - k*f[mx] <= mx
            // ceil( (i-mx)/f[mx] ) <=k
            ll k = (i-mx+f[mx]-1)/f[mx];
            ans += 2*k;
            i -= k*f[mx];
        }
        ans += v[i];
    }
    cout << ans << '\n';
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}