Codeforces Round 927(div3)

A-Thorns and Coins

长度为$n$的单元格路径,每个单元格有空、有金币、荆棘三种可能,人物从最左边开始向右移动,每次步长不多于2格,求能获得的最多金币数。

$t(1≤t≤1000)$

$n(1≤n≤50)$​

.代表空,*代表荆棘,@代表金币

从左往右,寻找第一个含有2个以上*的*连通块,其前的金币都可以达到。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void solve() {
    int n;cin >> n;
    string s;cin >> s;
    int cnt = 0;
    bool f = true;
    for (int i = 0;i < n;i++) {
        if (s[i] == '@')cnt++;
        if (i > 0 && s[i] == '*' && s[i - 1] == '*'){
            break;
        }
    }
    cout << cnt << '\n';
}

B-Chaya Calendar

查亚部落相信世界末日有$n$个征兆,第$i$个征兆每隔$a_i$年出现一次,当观测到第$i-1$个征兆后才会等待第$i$个征兆。给出每个征兆的出现间隔,询问观测到所有$n$个征兆所需要的年数。

ps:当第$i$个征兆在第$x$年被观测,部落会从第$x+1$年开始等待第$i+1$个征兆。

$t(1≤t≤1000)$

$n(1≤n≤100)$​

$a_i(1\le a_i\le 10^6)$

第$i$个征兆间隔$a_i$年出现,若上一个征兆在第$x$年被观测,则下一个征兆将在第$y=k\times a_i$年出现($x\lt y\le x+a_i$)。等待的时间是$y-x$,也就是$a_i-x\text{ }mod\text{ }a_i$年。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void solve() {
    int n;cin >> n;
    vector<ll>a(n);
    ll sum = 0;
    for (int i = 0;i < n;i++) {
        cin >> a[i];
        ll lf = a[i] - sum % a[i];
        sum += lf;
    }
    cout << sum << '\n';
}

C-LR-remainders

有一个数组$a$,一个正整数$m$和长度为$n$的命令(由L和R组成的字符串),每次求数组中剩余数的积模$m$的余数并输出,然后按照命令删数(L删去最左边的数,R删去最右边的数)。

$t(1≤t≤10^4)$

$n,m(1≤n≤2\times 10^5,1\le m\le 10^4)$​

$a_i(1\le a_i\le 10^4)$

反过来考虑,从最后一个删去的数开始,每次对积乘上上一次被删去的数,记录模m的值,逆序输出。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve() {
    int n, m;cin >> n >> m;
    vector<int>a(n);
    for (int i = 0;i < n;i++) { cin >> a[i]; }
    string s;cin >> s;
    vector<int>b;
    int l = 0, r = n - 1;
    for (int i = 0;i < n;i++) {
        if (s[i] == 'L')b.push_back(a[l++]);
        else b.push_back(a[r--]);
    }
    ll ans = 1;
    vector<int>res;
    reverse(b.begin(), b.end());
    for (int i = 0;i < n;i++) {
        ans *= b[i];
        res.push_back(ans % m);
        ans %= m;
    }
    reverse(res.begin(), res.end());
    for (int i = 0;i < n;i++) {
        cout << res[i] << " ";
    }cout << '\n';
}

D-Card Game

纸牌比大小游戏,有四种花色C、D、H、S,同一种花色之间比较数字,数字大的胜出。同时,每局有一个王牌花色,该花色的牌可以比剩余三种花色的牌都大,王牌花色和王牌花色之间比较数字大小。

给出所有已经打出的牌,尝试复现对局情况(第二位玩家击败第一位玩家);如果不能复现,输出IMPOSSIBLE。

$t(1≤t≤100)$

$n(1\le n \le 16)$​

模拟。

先对不同花色的牌分类,然后遍历同花色的牌,排序后,将非王牌花色放入一个序列,王牌花色单独一个序列。

从非王牌花色序列开始遍历,如果当前牌和其后一牌是同一种花色,凑成一对局;如果不是,用一张王牌花色和它凑成一个对局。假如可以凑成所有的对局,输出这些对局,否则不能构成对局。

 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
void solve() {
    int n;cin >> n;
    string w;cin >> w;

    int f = 0;
    switch (w[0]) {
    case 'S':f = 3;break;
    case 'H':f = 2;break;
    case 'D':f = 1;break;
    case 'C':f = 0;break;
    default:break;
    }

    vector<vector<string>>sp(4);
    for (int i = 0;i < 2 * n;i++) {
        string s;cin >> s;
        if (s[1] == 'C')sp[0].push_back(s);
        else if (s[1] == 'D')sp[1].push_back(s);
        else if (s[1] == 'H')sp[2].push_back(s);
        else sp[3].push_back(s);
    }
    vector<string>rk;
    for (int i = 0;i < 4;i++) {
        if (i == f)continue;
        sort(sp[i].begin(), sp[i].end());
        for (int j = 0;j < sp[i].size();j++)
            rk.push_back(sp[i][j]);
    }
    sort(sp[f].begin(), sp[f].end());
    for (int j = 0;j < sp[f].size();j++)
        rk.push_back(sp[f][j]);

    vector<pair<string, string>>ans;
    int cnt = 0;int p = rk.size() - 1;
    for (int i = 0;i < p;i++) {
        if (rk[i][1] == rk[i + 1][1]) {
            ans.push_back({ rk[i],rk[i + 1] });i++;
            cnt++;
        }
        else {
            if (f == 0 && rk[p][1] == 'C') {
                ans.push_back({ rk[i],rk[p] });p--;
            }
            else if (f == 1 && rk[p][1] == 'D') {
                ans.push_back({ rk[i],rk[p] });p--;
            }
            else if (f == 2 && rk[p][1] == 'H') {
                ans.push_back({ rk[i],rk[p] });p--;
            }
            else if (f == 3 && rk[p][1] == 'S') {
                ans.push_back({ rk[i],rk[p] });p--;
            }
            else {
                cout << "IMPOSSIBLE\n";return;
            }
        }
    }
    for (int i = 0;i < n;i++) {
        cout << ans[i].first << " " << ans[i].second << '\n';
    }
}

E-Final Countdown

倒计时,但是每次变化数所需要的秒数等于要变化的数位的数量。

求实际上需要多少秒完成倒计时。

$t(1≤t≤10^4)$

$n(1≤n≤4\times 10^5)$​

$a_i(1\le a_i\le 10^4)$

计数模拟:

1
2
3
4
5
6
7
12345
 1234
  123
   12
    1
-----+
13715

则对从第一位开始做前缀和,对(前缀和+进位)倒着取模,最后输出即可。

 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
void solve() {
    int n;cin >> n;
    string s;cin >> s;
    int x = 0;
    while (s[x] == '0') {
        x++;
    }
    s = s.substr(x);
    vector<ll>v;
    for (int i = 0;i < s.size();i++) {
        if (i != 0)
            v.push_back(v.back() + s[i] - '0');
        else {
            v.push_back(s[i] - '0');
        }
    }
    reverse(v.begin(), v.end());
    ll k = 0;
    vector<int>res;
    for (int i = 0;i < v.size();i++) {
        res.emplace_back((v[i] + k) % 10);
        k = (v[i] + k) / 10;
    }
    while(k > 0) {
        res.emplace_back(k % 10);
        k /= 10;
    }
    reverse(res.begin(), res.end());
    for (int i = 0;i < res.size();i++) {
        cout << res[i];
    }cout << '\n';
}

相关内容