Atcoder Beginner Contest 244

By xiaruize 20220320

A - Last Letter

Method & 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
/*
	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 ll long long
#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 multitest(t) while(t--) solve();
#define double long double
const int INF=0x3f3f3f3f;
const int Mod=1000000007;
const int N=1e5+10;

inline int rd() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9'){if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + (ch - '0');ch = getchar();}return x * w;}
inline void wt(int x) {static int sta[35];int top = 0;do {sta[top++] = x % 10, x /= 10;} while (x);while (top) putchar(sta[--top] + 48);}

//bool st;

//bool en;

signed main()
{
 	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	//cerr<<(&en-&st)/1024.0/1024.0<<endl;
	int n;
  	string s;
  	cin>>n>>s;
  	cout<<s[n-1]<<endl;
	return 0;
}

B - Go Straight and Turn Right

Method

模拟

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
// Problem: B - Go Straight and Turn Right
// Contest: AtCoder - AtCoder Beginner Contest 244
// URL: https://atcoder.jp/contests/abc244/tasks/abc244_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// TestType: single
//
// 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 ll long long
#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 multitest(t)                                                                                                   \
    while (t--)                                                                                                        \
        solve();
#define double long double
const int INF = 0x3f3f3f3f;
const int Mod = 1000000007;
const int N = 1e5 + 10;


// bool st;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, -1, 0, 1};
int n;
string s;
int now = 0;
// bool en;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> s;
    int x, y;
    x = y = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'R')
        {
            now = (now + 1) % 4;
        }
        else
        {
            x += dx[now];
            y += dy[now];
        }
    }
    cout << x << ' ' << y << endl;
    return 0;
}

C - Yamanote Line Game

Before Method

此生仅能见到Atcoder出交互题！！！

Method

似乎还是暴力模拟。。。

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
// Problem: C - Yamanote Line Game
// Contest: AtCoder - AtCoder Beginner Contest 244
// URL: https://atcoder.jp/contests/abc244/tasks/abc244_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// TestType: single
//
// 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 ll long long
#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 multitest(t)                                                                                                   \
    while (t--)                                                                                                        \
        solve();
#define double long double
const int INF = 0x3f3f3f3f;
const int Mod = 1000000007;
const int N = 1e5 + 10;


// bool st;
int n;
bool vis[2005];
// bool en;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n;
    for (int j = 1; j <= n; j++)
    {
        for (int i = 1; i <= 2 * n + 1; i++)
        {
            if (!vis[i])
            {
                cout << i << endl;
                vis[i] = true;
                break;
            }
        }
        int x;
        cin >> x;
        vis[x] = true;
    }

    for (int i = 1; i <= 2 * n + 1; i++)
    {
        if (!vis[i])
        {
            cout << i << endl;
            vis[i] = true;
            break;
        }
    }
    return 0;
}

D - Swap Hats

Method

手动模拟一下,当原始为123123时，只有123,312,231123,312,231可行

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
// Problem: D - Swap Hats
// Contest: AtCoder - AtCoder Beginner Contest 244
// URL: https://atcoder.jp/contests/abc244/tasks/abc244_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// TestType: single
//
// 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 ll long long
#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 multitest(t)                                                                                                   \
    while (t--)                                                                                                        \
        solve();
#define double long double
const int INF = 0x3f3f3f3f;
const int Mod = 1000000007;
const int N = 1e5 + 10;


// bool st;
char a[4];
char b[4];
int res[4];
int ans[3][3] = {{1, 2, 3}, {3, 1, 2}, {2, 3, 1}};
// bool en;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    for (int i = 1; i <= 3; i++)
        cin >> a[i];
    for (int i = 1; i <= 3; i++)
        cin >> b[i];
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            if (b[i] == a[j])
            {
                res[i] = j;
            }
        }
    }
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if (res[j + 1] != ans[i][j])
                break;
            if (j == 2)
            {
                Yes;
                return 0;
            }
        }
    }
    No;
    return 0;
}

E - King Bombee

Method

dp题 dpi,j,0/1dp_{i,j,0/1}表示当前考虑第ii条边，到点jj，xx被经过了奇数/偶数次

dp0,j,0={0 (j≠s)1 (j=s)dp0,j,1=0dpi+1,j,x=∑k∈adj(j)dpi,k,x(j≠x)dpi+1,X,x=∑k∈adj(X)dpi,k,1−xdp_{0,j,0}=\lbrace^{1~(j=s)}_{0~(j\neq s)}\\ dp_{0,j,1}=0\\ dp_{i+1,j,x}=\sum_{k\in adj(j)}{dp_{i,k,x}(j\neq x)}\\ dp_{i+1,X,x}=\sum_{k_\in adj(X)}{dp_{i,k,1-x}}

答案：dpK,T,0dp_{K,T,0}

时间复杂度: O((N+M)K)O((N+M)K)

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
// Problem: E - King Bombee
// Contest: AtCoder - AtCoder Beginner Contest 244
// URL: https://atcoder.jp/contests/abc244/tasks/abc244_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// TestType: single
//
// 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 ll long long
#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 multitest(t)                                                                                                   \
    while (t--)                                                                                                        \
        solve();
#define double long double
const int INF = 0x3f3f3f3f;
const int Mod = 1000000007;
const int MOD = 998244353;
const int N = 2010;

// bool st;
int n, m, k, s, t, x;
vector<pii> edge;
int dp[2005][2005][2];
// bool en;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> m >> k >> s >> t >> x;
    s--;
    t--;
    x--;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        edge.pb(mk(u, v));
    }
    dp[0][s][0] = 1;
    for (int i = 0; i < k; i++)
    {
        for (auto [u, v] : edge)
        {
            (dp[i + 1][v][0 ^ (v == x)] += dp[i][u][0]) %= MOD;
            (dp[i + 1][u][0 ^ (u == x)] += dp[i][v][0]) %= MOD;
            (dp[i + 1][v][1 ^ (v == x)] += dp[i][u][1]) %= MOD;
            (dp[i + 1][u][1 ^ (u == x)] += dp[i][v][1]) %= MOD;
        }
    }
    cout << dp[k][t][0] << endl;
    return 0;
}