It has been 956 days since the last update, the content of the article may be outdated.

Codeforces Round #811 (Div. 3)

By xiaruize

A. Everyone Loves to Sleep’

模拟

Code
cpp
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
80
81
82
83
84
85
86
87
// Problem: A. Everyone Loves to Sleep
// Contest: Codeforces Round #811 (Div. 3)
// URL: https://codeforces.com/contest/1714/problem/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int t;
int n;
int h, m;
pii a[15];
// bool en;

bool check(int x, int y)
{
    for (int i = 1; i <= n; i++)
        if (a[i].fir == x && a[i].sec == y)
            return true;
    return false;
}

void solve()
{
    cin >> n >> h >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i].fir >> a[i].sec;
    sort(a + 1, a + n + 1);
    int cnt = 0;
    while (!check(h, m))
    {
        m++;
        cnt++;
        if (m == 60)
        {
            m = 0;
            h++;
        }
        if (h == 24)
            h = 0;
    }
    cout << cnt / 60 << ' ' << cnt % 60 << endl;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    // auto t_1=chrono::high_resolution_clock::now();
    cin >> t;
    while (t--)
        solve();
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

B. Remove Prefix

倒序遍历整个数列，用一个数组记录一下

Code
cpp
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
// Problem: B. Remove Prefix
// Contest: Codeforces Round #811 (Div. 3)
// URL: https://codeforces.com/contest/1714/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int t;
int n;
int a[N];
bool vis[N];
// bool en;

void solve()
{
    memset(vis, 0, sizeof(vis));
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = n; i >= 1; i--)
    {
        if (vis[a[i]])
        {
            cout << i << endl;
            return;
        }
        vis[a[i]] = true;
    }
    cout << "0" << endl;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    // auto t_1=chrono::high_resolution_clock::now();
    cin >> t;
    while (t--)
        solve();
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

C. Minimum Varied Number

明显应该从低位到高位递减放

Code
cpp
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
// Problem: C. Minimum Varied Number
// Contest: Codeforces Round #811 (Div. 3)
// URL: https://codeforces.com/contest/1714/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int t;
int s;
vector<int> res;
// bool en;

void solve()
{
    res.clear();
    cin >> s;
    int x = 9;
    while (s >= x && x)
    {
        res.pb(x);
        s -= x;
        x--;
    }
    if (s != 0)
        res.pb(s);
    reverse(ALL(res));
    for (auto x : res)
        cout << x;
    cout << endl;
}
signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    // auto t_1=chrono::high_resolution_clock::now();
    cin >> t;
    while (t--)
        solve();
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

D. Color with Occurrences

个人认为这题应该往后排。。。

记录一个数组ff，其中fif_i表示从t[i]t[i]或之前开始，通过一次操作最远能到达的位置

然后暴力匹配就行

数据都很小，好似怎么实现都可以AC\color{green}{AC}

Code
cpp
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// Problem: D. Color with Occurrences
// Contest: Codeforces Round #811 (Div. 3)
// URL: https://codeforces.com/contest/1714/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double

int T, n, l[15], f[105], tl;
int ans;
vector<pii> res;
char s[15][15], t[105];

bool check(int i, int j)
{
    if (tl - i + 1 < l[j])
        return false;
    if (i < 1)
        return false;
    for (int k1 = i, k2 = 1; s[j][k2] != '\0'; k1++, k2++)
        if (t[k1] != s[j][k2])
            return false;
    return true;
}

void solve()
{
    res.clear();
    cin >> (t + 1);
    cin >> n;
    memset(f, 0, sizeof(f));
    tl = strlen(t + 1);
    ans = 0;
    f[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> (s[i] + 1);
        l[i] = strlen(s[i] + 1);
        for (int j = 1; j <= tl; j++)
        {
            if (check(j, i))
            {
                f[j] = max(f[j], j + l[i] - 1);
            }
        }
    }
    for (int i = 1; i <= tl; i++)
    {
        f[i] = max(f[i], f[i - 1]);
    }
    for (int i = 1; i <= tl; i++)
    {
        if (f[i] < i)
        {
            cout << "-1" << endl;
            return;
        }
        else
        {
            int tmp = i;
            i = f[i];
            ans++;
            for (int j = 1; j <= n; j++)
            {
                if (check(i - l[j] + 1, j) && i - l[j] + 1 <= tmp)
                {
                    res.pb({j, i - l[j] + 1});
                    break;
                }
            }
        }
    }
    cout << ans << endl;
    for (auto [l, r] : res)
        cout << l << ' ' << r << endl;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    // auto t_1=chrono::high_resolution_clock::now();
    cin >> T;
    while (T--)
        solve();
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

E. Add Modulo 10

挺好的数学题，难度不大

根据个位先枚举一下，会发现一定的规律

  • 0,0,0,0…
  • 1,2,4,8,6,2,4,8,6
  • 3,6,2,4,8,6
  • 4,8,6,2,4,8,6
  • 5,0,0,…
  • 6,2,4,8,6,2
  • 7,4,8,6,2,4,8,6
  • 8,6,2.4.8.6
  • 9,8,6,2,4,8,6

发现除了0,5其他的都会有循环节2,4,8,6

先特判0,5，其他情况则把个位转为一个统一的数，设操作完为bb

如果对于1≤i≤n1\leq i \leq n, ⌊bi10⌋mod  2\lfloor \frac{b_i}{10} \rfloor \mod 2均相等Yes,否则No

Code
cpp
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// Problem: E. Add Modulo 10
// Contest: Codeforces Round #811 (Div. 3)
// URL: https://codeforces.com/contest/1714/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int t;
int n;
int a[N];
int cnt = 0;
int mi = INF, mx = 0;
// bool en;

void solve()
{
    cin >> n;
    cnt = 0;
    mi = INF;
    mx = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] % 10 == 5)
            a[i] += 5;
        if (a[i] % 10 == 0)
        {
            cnt++;
            mi = min(mi, a[i]);
            mx = max(mx, a[i]);
        }
    }
    if (cnt && (cnt != n || mx != mi))
    {
        No;
        return;
    }
    if (cnt == n)
    {
        Yes;
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        while (a[i] % 10 != 2)
            a[i] += a[i] % 10;
    }
    for (int i = 2; i <= n; i++)
    {
        if ((abs((a[i] / 10) - (a[i - 1] / 10)) % 2) != 0)
        {
            No;
            return;
        }
    }
    Yes;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    // auto t_1=chrono::high_resolution_clock::now();
    cin >> t;
    while (t--)
        solve();
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

G. Path Prefixes

dfs, 用个set记录一下来的路径上的bb，时间复杂度O(nlogn)O(nlogn)

Code
cpp
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// Problem: G. Path Prefixes
// Contest: Codeforces Round #811 (Div. 3)
// URL: https://codeforces.com/contest/1714/problem/G
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int t;
int n;
vector<pair<int, pii>> g[N];
int fa[N];
int v[N], p[N];
int res[N];
map<int, int> pos;
multiset<pii> s;
// bool en;

void dfs(int x, int fa, int dep)
{
    pos[x] = dep;
    for (auto k : g[x])
    {
        v[k.fir] = v[x] + k.sec.fir;
        p[k.fir] = p[x] + k.sec.sec;
        dfs(k.fir, x, dep + 1);
    }
    return;
}

void calc(int x)
{
    s.insert({p[x], x});
    auto tmp = s.upper_bound({v[x], INF});
    tmp--;
    res[x] = pos[(*tmp).sec];
    for (auto k : g[x])
        calc(k.fir);
    s.erase({p[x], x});
    return;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        g[i].clear();
    for (int i = 2; i <= n; i++)
    {
        int fa, x, y;
        cin >> fa >> x >> y;
        g[fa].pb({i, {x, y}});
    }
    dfs(1, 0, 0);
    calc(1);
    for (int i = 2; i <= n; i++)
        cout << res[i] << ' ';
    cout << endl;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    // auto t_1=chrono::high_resolution_clock::now();
    cin >> t;
    while (t--)
        solve();
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}