Atcoder Beginner Contest 261

By xiaruize

A - Intersection

签到题，强烈推荐写暴力，

不要问我怎么知道的qwq
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
// Problem: A - Intersection
// Contest: AtCoder - AtCoder Beginner Contest 261
// URL: https://atcoder.jp/contests/abc261/tasks/abc261_a
// Memory Limit: 1024 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 x, y, xx, yy;
bool vis[105];
// bool en;

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 >> x >> y >> xx >> yy;
    for (int i = x; i <= y; i++)
        vis[i] = 1;
    int cnt = 0;
    for (int i = xx; i <= yy; i++)
        if (vis[i])
            cnt++;
    cout << max(cnt - 1, 0ll) << endl;
    // 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 - Tournament Result

个人感觉这个更适合A题

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// Problem: B - Tournament Result
// Contest: AtCoder - AtCoder Beginner Contest 261
// URL: https://atcoder.jp/contests/abc261/tasks/abc261_b
// Memory Limit: 1024 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;
char c[1005][1005];
int n;
// bool en;

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 >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> c[i][j];
            if (i <= j)
                continue;
            if (c[i][j] == 'W' && c[j][i] != 'L')
            {
                cout << "incorrect" << endl;
                return 0;
            }
            if (c[i][j] == 'L' && c[j][i] != 'W')
            {
                cout << "incorrect" << endl;
                return 0;
            }
            if (c[i][j] == 'D' && c[j][i] != 'D')
            {
                cout << "incorrect" << endl;
                return 0;
            }
        }
    }
    cout << "correct" << endl;
    // 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 - NewFolder(1)

实现题，用个map就行，当然也可以哈希

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
64
65
66
// Problem: C - NewFolder(1)
// Contest: AtCoder - AtCoder Beginner Contest 261
// URL: https://atcoder.jp/contests/abc261/tasks/abc261_c
// Memory Limit: 1024 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;
string s;
int n;
map<string, int> mp;
// bool en;

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 >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        cout << s;
        mp[s]++;
        if (mp[s] != 1)
        {
            cout << "(" << mp[s] - 1 << ")" << endl;
        }
        else
            cout << endl;
    }
    // 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 - Flipping and Bonus

挺明显的dp题

令dpi,jdp_{i,j} 表示第ii次抛硬币后counter的值为jj时的最大值

转移如下:

  • dp[i][j]=dp[i−1][j−1]+Xi+∑Ck=jYkdp[i][j]=dp[i-1][j-1]+X_i+\sum_{C_k=j}{Y_k}
  • dp[i][0]=max0ndp[i−1][j]dp[i][0]=max_{0}^{n} dp[i-1][j]

而第一个转移可以预处理每个j对应的值，所以总时间复杂度为O(n2)O(n^2)

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// Problem: D - Flipping and Bonus
// Contest: AtCoder - AtCoder Beginner Contest 261
// URL: https://atcoder.jp/contests/abc261/tasks/abc261_d
// Memory Limit: 1024 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, m;
int x[5005];
int c[5005];
int y[5005];
int p[5005];
int dp[5005][5005];
// bool en;

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 >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 1; i <= m; i++)
    {
        cin >> c[i] >> y[i];
        p[c[i]] += y[i];
    }
    for (int i = 1; i <= n; i++)
    {
        int mx = 0;
        for (int j = 1; j <= i; j++)
        {
            dp[i][j] = dp[i - 1][j - 1] + p[j] + x[i];
            mx = max(mx, dp[i - 1][j]);
        }
        dp[i][0] = mx + p[0];
        dp[i][0] = max(dp[i][0], dp[i - 1][0] + p[0]);
    }
    int res = 0;
    for (int i = 0; i <= n; i++)
        res = max(res, dp[n][i]);
    cout << res << endl;
    // 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 - Many Operations

这题卡了好久qwq

用pre[i][0/1][j]pre[i][0/1][j]表示二进制下的第ii位为0/10/1时，进行前jj个计算后这一位的值，可以O(n)O(n)预处理

剩下的就是统计答案qwq

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
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
// Problem: E - Many Operations
// Contest: AtCoder - AtCoder Beginner Contest 261
// URL: https://atcoder.jp/contests/abc261/tasks/abc261_e
// Memory Limit: 1024 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, c;
int t[N], a[N];
int pre[30][2][N];
// bool en;

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 >> n >> c;
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i] >> a[i];
    }
    for (int i = 0; i < 30; i++)
    {
        int z = 0, o = 1;
        pre[i][0][0] = 0;
        pre[i][1][0] = 1;
        for (int j = 1; j <= n; j++)
        {
            if (t[j] == 1)
            {
                z &= (a[j] >> i) & 1;
                o &= (a[j] >> i) & 1;
            }
            if (t[j] == 2)
            {
                z |= (a[j] >> i) & 1;
                o |= (a[j] >> i) & 1;
            }
            if (t[j] == 3)
            {
                z ^= (a[j] >> i) & 1;
                o ^= (a[j] >> i) & 1;
            }
            pre[i][0][j] = z;
            pre[i][1][j] = o;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        int tmp = 0;
        for (int j = 0; j < 30; j++)
        {
            tmp |= ((pre[j][c & 1][i - 1]) << j);
            c >>= 1;
        }
        // cerr << tmp << endl;
        if (t[i] == 1)
        {
            tmp &= a[i];
        }
        if (t[i] == 2)
        {
            tmp |= a[i];
        }
        if (t[i] == 3)
        {
            tmp ^= a[i];
        }
        cout << tmp << endl;
        c = tmp;
    }
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

F - Sorting Color Balls

先上结论

把每个颜色单独拉出来组成一个相对位置不变的新的序列

答案为((原序列的逆序对数量)−∑)-\sum新序列的逆序对数量

证明
有一点感性
不确定对不对qwq

先考虑没有颜色这个限制，那么答案就是原来的序列的逆序对个数

对于上面结论的证明

如果当前序列不存在一个逆序对相邻，那么当前序列一定有序

否则必然存在一对相邻的逆序对，交换它

每次操作必然会减少一对逆序对，所以答案为逆序对个数

下面回到这道题，可以发现，当一对逆序对的颜色相同时，它们的前后关系一定不可能发生改变，因为不允许颜色一样的互相交换

所以这些逆序对是不会被调整的，所以应该在原先的次数上将它们减去

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
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
// Problem: F - Sorting Color Balls
// Contest: AtCoder - AtCoder Beginner Contest 261
// URL: https://atcoder.jp/contests/abc261/tasks/abc261_f
// Memory Limit: 1024 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 = 3e5 + 10;

// bool st;
int n;
int c[N];
int tmp[N];
vector<int> a;
vector<int> v[N];
int cnt = 0;
// bool en;

int p(vector<int> &w, int l, int r)
{
    if (l >= r)
        return 0;
    int mid = (l + r) / 2;
    int res = p(w, l, mid) + p(w, mid + 1, r);

    for (int i = l, j = mid + 1, k = l; k <= r; k++)
    {
        if (j > r || (i <= mid && w[i] <= w[j]))
            tmp[k] = w[i++];
        else
            res += mid - i + 1, tmp[k] = w[j++];
    }
    rep(i, l, r) w[i] = tmp[i];
    return res;
}

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 >> n;
    for (int i = 0; i < n; i++)
        cin >> c[i];
    a.clear();
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        a.pb(x);
    }
    for (int i = 0; i < n; i++)
        v[c[i]].pb(a[i]);
    int res = p(a, 0, n - 1);
    for (int i = 1; i <= n; i++)
    {
        if (!v[i].empty())
            res -= p(v[i], 0, v[i].size() - 1);
    }
    cout << res << endl;
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

未完待更