Codeforces Round 797 Div.3

By xiaruize

A. Print a Pedestal (Codeforces logo?)

分三类讨论，即nn模33的值

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
// Problem: Print a Pedestal (Codeforces logo?)
// Contest: Codeforces
// URL: https://m3.codeforces.com/contest/1690/problem/A
// 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 = 1e5 + 10;

// bool st;
int t;
int n;

// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> t;
    while (t--)
    {
        cin >> n;
        int x = n / 3;
        if (n % 3 == 0)
            cout << n / 3 << ' ' << n / 3 + 1 << ' ' << n / 3 - 1 << endl;
        else if (n % 3 == 1)
            cout << x << ' ' << x + 2 << ' ' << x - 1 << endl;
        else
            cout << x + 1 << ' ' << x + 2 << ' ' << x - 1 << endl;
    }
    return 0;
}
英文不好，痛吃罚时

B. Array Decrements

模拟即可，没什么难度

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: Array Decrements
// Contest: Codeforces
// URL: https://m1.codeforces.com/contest/1690/problem/B
// 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 = 5e4 + 10;

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

void solve()
{
    cin >> n;
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int dif = -1;
    bool f = false;
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
        if (b[i] > a[i])
        {
            f = 1;
        }
        if (b[i] != 0)
            dif = a[i] - b[i];
    }
    if (f)
    {
        NO;
        return;
    }
    if (dif == -1)
    {
        YES;
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] -= dif;
        // cerr << i << ' ' << a[i] << ' ' << b[i] << endl;
        if (a[i] <= 0 && b[i] != 0)
        {
            NO;
            return;
        }
        if (a[i] > 0 && a[i] != b[i])
        {
            NO;
            return;
        }
    }
    YES;
    return;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C. Restoring the Duration of Tasks

似乎还是模拟，循环一遍就可以了

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
// Problem: Restoring the Duration of Tasks
// Contest: Codeforces
// URL: https://m1.codeforces.com/contest/1690/problem/C
// 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 s[N], f[N];
// bool en;

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    for (int i = 1; i <= n; i++)
        cin >> f[i];
    int now = 0;
    for (int i = 1; i <= n; i++)
    {
        now = max(now, s[i]);
        cout << f[i] - now << ' ';
        now = f[i];
    }
    cout << endl;
    return;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

D. Black and White Stripe

滑动窗口，或者前缀和预处理都可以过，时间复杂度O(n)O(n)

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
// Problem: Black and White Stripe
// Contest: Codeforces
// URL: https://m1.codeforces.com/contest/1690/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
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int n, t, k;
string s;
int sum[N];
// bool en;

void solve()
{
    cin >> n >> k;
    cin >> s;
    sum[0] = 0;
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + (s[i - 1] == 'W' ? 1 : 0);
    int res = k;
    for (int i = k; i <= n; i++)
    {
        res = min(res, sum[i] - sum[i - k]);
    }
    cout << res << endl;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

E. Price Maximization

注意！！！ k在1000​以内，不代表总和不超过1000 qwq

所以枚举差值是会TLE的。。。

考虑可以贪心，即可以按模k的余数排序，每次取收尾两个数组合。

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
// Problem: Price Maximization
// Contest: Codeforces
// URL: https://m1.codeforces.com/contest/1690/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, k, x;
int cnt[1005];
int sum = 0, res = 0;
// bool en;

void solve()
{
    memset(cnt, 0, sizeof(cnt));
    scanf("%lld%lld", &n, &k);
    sum = res = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &x);
        cnt[x % k]++;
        res += x / k;
    }
    int l = 0, r = k - 1;
    while (l <= r)
    {
        if (l + r < k)
            l++;
        if (l > r)
            break;
        if (l == r && l + r >= k)
        {
            sum += cnt[l] / 2;
            cnt[l] &= 1;
            break;
        }
        if (cnt[l] < cnt[r])
        {
            sum += cnt[l];
            cnt[r] -= cnt[l++];
        }
        else
        {
            sum += cnt[r];
            cnt[l] -= cnt[r--];
        }
    }
    printf("%lld\n", res + sum);
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    scanf("%lld", &t);
    while (t--)
        solve();
    return 0;
}

Summary

网速太慢力qwq

前两题连续脑抽吃罚时

题目编号AC时间用时
A22:4813min
B22:5911min
C23:034min
D23:096min
E00:1667min

A,B题不吃罚时应该就不会掉分了qwq