Atcoder Beginner Contest 264

By xiaruize

A - “atcoder”.substr()

模拟题

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
/*
 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;

//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();
 string s="atcoder";
  int l,r;
  cin>>l>>r;
  cout<<s.substr(l-1,r-l+1)<<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 - Nice Grid

很明显，所有的黑色格子距离最近的边界都是奇数

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
// Problem: B - Nice Grid
// Contest: AtCoder - freee Programming Contest 2022（AtCoder Beginner Contest 264）
// URL: https://atcoder.jp/contests/abc264/tasks/abc264_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;
int r, c;
bool a[16][16];
// 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 >> r >> c;
    if (min(min(r, 15 - r + 1), min(c, 15 - c + 1)) & 1)
        cout << "black" << endl;
    else
        cout << "white" << 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 - Matrix Reducing

二进制枚举

二进制枚举

简单来说，就是通过一个数二进制下每一位的数字(0/1)，表示当前为的一种是否状态

例如本题中，每一位就表示当前行、列是否被选中

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
// Problem: C - Matrix Reducing
// Contest: AtCoder - freee Programming Contest 2022（AtCoder Beginner Contest 264）
// URL: https://atcoder.jp/contests/abc264/tasks/abc264_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;
int h, w;
int hh, ww;
int a[15][15];
int b[15][15];
// 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 >> h >> w;
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            cin >> a[i][j];
    cin >> hh >> ww;
    for (int i = 1; i <= hh; i++)
        for (int j = 1; j <= ww; j++)
            cin >> b[i][j];
    for (int mskh = 0; mskh < (1 << h); mskh++)
    {
        int cnt = 0;
        for (int i = 0; i < h; i++)
            if (mskh & (1 << i))
                cnt++;
        if (cnt != h - hh)
            continue;
        for (int mskw = 0; mskw < (1 << w); mskw++)
        {
            int cnt = 0;
            for (int i = 0; i < w; i++)
                if (mskw & (1 << i))
                    cnt++;
            if (cnt != w - ww)
                continue;
            int hp = 1, hw = 1;
            bool f = true;
            for (int i = 1; i <= h; i++)
            {
                for (int j = 1; j <= w; j++)
                {
                    if ((mskh & (1 << (i - 1))) || ((mskw & (1 << (j - 1)))))
                        continue;
                    if (b[hp][hw] != a[i][j])
                    {
                        f = false;
                        break;
                    }
                    hw++;
                    if (hw == ww + 1)
                        hw = 1, hp++;
                }
                if (!f)
                    break;
            }
            if (f)
            {
                Yes;
                return 0;
            }
        }
    }
    No;
    // 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 - “redocta”.swap(i,i+1)

很典型的逆序对题，n2n^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
// Problem: D - "redocta".swap(i,i+1)
// Contest: AtCoder - freee Programming Contest 2022（AtCoder Beginner Contest 264）
// URL: https://atcoder.jp/contests/abc264/tasks/abc264_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;
string s;
map<char, int> mp;
int a[8];
// 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 >> s;
    mp['a'] = 1;
    mp['t'] = 2;
    mp['c'] = 3;
    mp['o'] = 4;
    mp['d'] = 5;
    mp['e'] = 6;
    mp['r'] = 7;
    for (int i = 0; i < 7; i++)
        a[i + 1] = mp[s[i]];
    int res = 0;
    for (int i = 1; i <= 7; i++)
    {
        for (int j = i + 1; j <= 7; j++)
            if (a[j] < a[i])
                res++;
    }
    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 - Blackout 2

显然并不需要在线查询，此时考虑倒序处理，即把删边的操作转化为连边。

此时，分一下情况:

  • 当前两个顶点都没有电,直接连边
  • 当前两个顶点都有电,直接连边
  • 当前两个顶点有且仅有一个有电,向没电的方向搜索，直到都有电

时间复杂度O(E+N)O(E+N)

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
109
110
111
112
// Problem: E - Blackout 2
// Contest: AtCoder - freee Programming Contest 2022（AtCoder Beginner Contest 264）
// URL: https://atcoder.jp/contests/abc264/tasks/abc264_e
// 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 = 2e5 + 10;
const int M = 5e5 + 10;

// bool st;
int n, m, e;
int u[M], v[M];
int q;
int t[M];
bool d[M];
bool ele[N];
int res = 0;
int ans[M];
vector<int> g[N];
// bool en;

void dfs(int x, int fa)
{
    if (ele[x])
        return;
    ele[x] = true;
    res++;
    for (auto v : g[x])
        if (v != fa)
            dfs(v, x);
}

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 >> e;
    for (int i = 1; i <= e; i++)
        cin >> u[i] >> v[i];
    for (int i = n + 1; i <= n + m; i++)
        ele[i] = true;
    cin >> q;
    for (int i = 1; i <= q; i++)
        cin >> t[i], d[t[i]] = true;
    for (int i = 1; i <= e; i++)
    {
        if (d[i])
            continue;
        if (u[i] <= n && v[i] <= n)
        {
            g[u[i]].pb(v[i]);
            g[v[i]].pb(u[i]);
        }
    }
    for (int i = 1; i <= e; i++)
    {
        if (d[i])
            continue;
        if (ele[u[i]])
            dfs(v[i], u[i]);
        else if (ele[v[i]])
            dfs(u[i], v[i]);
        g[u[i]].pb(v[i]);
        g[v[i]].pb(u[i]);
    }
    for (int i = q; i >= 1; i--)
    {
        ans[i] = res;
        if (ele[u[t[i]]])
            dfs(v[t[i]], u[t[i]]);
        if (ele[v[t[i]]])
            dfs(u[t[i]], v[t[i]]);
        g[u[t[i]]].pb(v[t[i]]);
        g[v[t[i]]].pb(u[t[i]]);
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << 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;
}

这个东西其实可以用并查集维护，考场先写的这个，但是调假了。。。

感谢ktq\color{red}{ktq}巨佬写的代码，证明这个思路是真的。。。

速度比对

搜索并查集
998ms102ms

F - Monochromatic Path

dp

dpi,j,0/1,0/1dp_{i,j,0/1,0/1} 分别表示当前的格子为(i,j)(i,j)，行有没有反转过，列有没有反转过

转移很明显(见代码)

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
109
110
111
112
113
114
115
116
117
118
119
120
// Problem: F - Monochromatic Path
// Contest: AtCoder - freee Programming Contest 2022（AtCoder Beginner Contest 264）
// URL: https://atcoder.jp/contests/abc264/tasks/abc264_f
// 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 r[2005], c[2005], ans;
bool a[2005][2005], vis[2005][2005];
int dp[2005][2005][2][2];
// bool en;

void chkmin(int &x, int y)
{
    if (y < x)
        x = y;
}

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 >> r[i];
    for (int i = 1; i <= m; i++)
        cin >> c[i];
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++)
        {
            a[i][j] = s[j - 1] - '0';
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[1][1][0][0] = 0;
    dp[1][1][1][0] = r[1];
    dp[1][1][0][1] = c[1];
    dp[1][1][1][1] = r[1] + c[1];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (i != 1)
            {
                if (a[i][j] == a[i - 1][j])
                {
                    chkmin(dp[i][j][0][0], dp[i - 1][j][0][0]);
                    chkmin(dp[i][j][1][0], dp[i - 1][j][1][0] + r[i]);
                    chkmin(dp[i][j][0][1], dp[i - 1][j][0][1]);
                    chkmin(dp[i][j][1][1], dp[i - 1][j][1][1] + r[i]);
                }
                else
                {
                    chkmin(dp[i][j][0][0], dp[i - 1][j][1][0]);
                    chkmin(dp[i][j][1][0], dp[i - 1][j][0][0] + r[i]);
                    chkmin(dp[i][j][0][1], dp[i - 1][j][1][1]);
                    chkmin(dp[i][j][1][1], dp[i - 1][j][0][1] + r[i]);
                }
            }
            if (j != 1)
            {
                if (a[i][j - 1] == a[i][j])
                {
                    chkmin(dp[i][j][0][0], dp[i][j - 1][0][0]);
                    chkmin(dp[i][j][0][1], dp[i][j - 1][0][1] + c[j]);
                    chkmin(dp[i][j][1][0], dp[i][j - 1][1][0]);
                    chkmin(dp[i][j][1][1], dp[i][j - 1][1][1] + c[j]);
                }
                else
                {
                    chkmin(dp[i][j][0][0], dp[i][j - 1][0][1]);
                    chkmin(dp[i][j][0][1], dp[i][j - 1][0][0] + c[j]);
                    chkmin(dp[i][j][1][0], dp[i][j - 1][1][1]);
                    chkmin(dp[i][j][1][1], dp[i][j - 1][1][0] + c[j]);
                }
            }
        }
    }
    cout << min(min(dp[n][m][0][0], dp[n][m][0][1]), min(dp[n][m][1][0], dp[n][m][1][1])) << 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;
}