KYOCERA Programming Contest 2022 (AtCoder Beginner Contest 271)

By xiaruize

D - Flip and Adjust

很明显，贪心容易有反例 ⇒\rArr 考虑 dpdp

dp[i][j][0/1]dp[i][j][0/1] 表示当前考虑到第i位，和为j，正/反面朝上是否可行

可以O(NS)O(NS)的完成转移

如果可行，根据dp状态就可以找到序列

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
/*
    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, s;
int a[105], b[105];
bool dp[105][10005][2];
// 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 >> s;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
    }
    dp[0][0][0] = dp[0][0][1] = true;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= s; j++)
        {
            if (j + a[i] <= s)
                dp[i][j + a[i]][0] = dp[i - 1][j][0] | dp[i - 1][j][1];
            if (j + b[i] <= s)
                dp[i][j + b[i]][1] = dp[i - 1][j][1] | dp[i - 1][j][0];
        }
    }
    if (!(dp[n][s][0] | dp[n][s][1]))
        No;
    else
    {
        Yes;
        vector<char> res;
        for (int i = n; i >= 1; i--)
        {
            if (dp[i][s][0])
            {
                res.pb('H');
                s -= a[i];
            }
            else
            {
                res.pb('T');
                s -= b[i];
            }
        }
        reverse(ALL(res));
        for (auto v : res)
            cout << v;
    }
    // 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 - Subsequence Path

考虑 dpk,idp_{k,i} 表示考虑前 kk 条边到 ii 的距离的最小值

按照 EE 的顺序转移

看似这个算法是 O(NK)O(NK) 的

但是其实每一次转移都只会检查一条边，所以可以把第一维省略，进而将 dpdp 搞成 O(K)O(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
/*
 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 = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int n, m, k;
int dis[N];
int a[N], b[N], c[N];
int e[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();
    memset(dis, 0x3f, sizeof(dis));
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
        cin >> a[i] >> b[i] >> c[i];
    for (int i = 1; i <= k; i++)
        cin >> e[i];
    dis[1] = 0;
    for (int i = 1; i <= k; i++)
    {
        dis[b[e[i]]] = min(dis[b[e[i]]], dis[a[e[i]]] + c[e[i]]);
    }
    if (dis[n] >= INF)
        cout << "-1" << endl;
    else
        cout << dis[n] << 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;
}

F - XOR on Grid Path

2402^{40} 如果枚举肯定会超时，那么可以考虑怎么优化?

容易发现，到达对角线上每个点所需要的决策步数是相同的，所以可以 meet in the middle

具体来说

就是先枚举由起点 nn 步到达的所有位置 ⇒\rArr O(2N)O(2^N)

再枚举从终点起 nn 步到达的位置，统计答案 ⇒\rArr O(2N)O(2^N)

总时间复杂度 O(2N+1)O(2^{N+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
/*
    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;
int a[25][25];
map<int, int> mp[25];
// 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 >> a[i][j];
    int h = n - 1;
    for (int i = 0; i < (1 << h); i++)
    {
        int x = 1, y = 1, st = a[1][1];
        for (int j = 0; j < h; j++)
        {
            if (i & (1 << j))
                x++;
            else
                y++;
            st ^= a[x][y];
        }
        mp[x][st]++;
        // cerr << x << ' ' << st << endl;
    }
    int res = 0;
    for (int i = 0; i < (1 << h); i++)
    {
        int x = n, y = n, st = a[n][n];
        for (int j = 0; j < h; j++)
        {
            if (i & (1 << j))
                x--;
            else
                y--;
            st ^= a[x][y];
        }
        st ^= a[x][y];
        // cerr << st << endl;
        res += mp[x][st];
    }
    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;
}