传送门

A Mocha 上小班啦

签到，交换$01$位置输出即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e9 + 7, MAXN = 2e5 + 10, mod = 998244353;
string tab = "1023456789";
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    if(n > tab.size()) {
        cout << "-1\n";
    } else {
        for(int i = 0; i < n; i ++) {
            cout << tab[i];
        }
        cout << '\n';
    }
}

B Hash

考虑子串的长度不大于$15$的情况(官方题解说只要考虑这种情况就行了)，然后dp就行了。只需证明长度为$16$的字串必然会存在一个划分使得产生的价值大于不划分产生的价值。具体看官方题解吧，这个证明我也说不太清（现场的话应该可以猜字串长度不会太大来做）。

 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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e9 + 7, MAXN = 2e5 + 10, mod = 998244353;
int mp(char x) {
    int res = 0;
    if(x == 'a') res = 1;
    else if(x == 'e') res = 2;
    else if(x == 'h') res = 3;
    else if(x == 'n') res = 4;
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    s = s + s;
    vector<ll> d(16);
    for(int i = 0; i < 16; i ++) {
        if(!i) d[i] = 1;
        else d[i] = 31 * d[i - 1];
        d[i] %= mod;
    }
    ll res = 0;
    for(int l = 1; l <= 15; l ++) {
        int r = l + n;
        vector<ll> dp (n + 1);
        for(int i = 1; i <= n; i ++) {
            ll t = 0;
            for(int j = i, x = 0; j > max(0, i - 15); j --, x ++) {
                t += mp(s[l + j - 1]) * d[x];
                t %= mod;
                dp[i] = max(dp[i], dp[j - 1] + t);
            }
        }
        res = max(res, dp[n]);
    }
    cout << res << '\n';
}

E Serval 的俳句

记录每个字母出现的位置，考虑三段组成的字母，第一段取字母的前5个并记录最后一个字母的位置，第二段找到从记录的位置开始，取7个，再记录最后一个字母的位置，第三段同理。时间复杂度$O(26^3log|S|)$。

 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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e9 + 7, MAXN = 2e5 + 10, mod = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<vector<int>> pos(26);
    for(int i = 0; i < n; i ++) {
        pos[s[i] - 'a'].push_back(i);
    }
    for(int i = 0; i < 26; i ++) if(pos[i].size() >= 5) {
        int x1 = 4;
        for(int j = 0; j < 26; j ++) {
            int c = upper_bound(pos[j].begin(), pos[j].end(), pos[i][x1]) - pos[j].begin();
            if(pos[j].size() - c < 7) {
                continue;
            }
            int x2 = c + 6;
            for(int k = 0; k < 26; k ++) {
                int c = upper_bound(pos[k].begin(), pos[k].end(), pos[j][x2]) - pos[k].begin();
                if(pos[k].size() - c < 5) {
                    continue;
                }
                int x3 = c + 4;
                char x = 'a' + i, y = 'a' + j, z = 'a' + k;
                for(int t = 0; t < 5; t ++) {
                    cout << x;
                }
                for(int t = 0; t < 7; t ++) {
                    cout << y;
                }
                for(int t = 0; t < 5; t ++) {
                    cout << z;
                }
                cout << '\n';
                return 0;
            }

        }
    }
    cout << "none\n";
    return 0;
}

F 集合之和

这题卡了很久，以为要求使$n$最小。。。 如果是一个等差数列的话，矩阵中的任意一点的值为$O(2a_0 + (i + j)k)$，发现$n$大小的数列能够产生$2n - 1$个不同的数，故对所有的奇数都成立。若前三个数不等差，那么会产生$6$个数，后面每多一个数与前一个数等差，会多产生两个数，故对于所有大于等于$6$的偶数都有解。

 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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e9 + 7, MAXN = 2e5 + 10, mod = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    if(n % 2 == 1) {
        int x = (n + 1) / 2;
        cout << x << '\n';
        for(int i = 1; i <= x; i ++) {
            cout << i << ' ';
        }
        cout << '\n';
    } else {
        if(n >= 6) {
            int x = n / 2;
            cout << x << '\n';
            for(int i = 1, j = 1; j <= x; i ++, j ++) {
                if(i == 2) {
                    i ++;
                }
                cout << i << ' ';
            }
        } else {
            cout << "-1\n";
        }
    }
}

G Mocha 上大班啦

诈骗题。&运算只会使$0$减少，不会增加，那么对全部数进行&运算就是求每一位都为$1$的个数。

 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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e9 + 7, MAXN = 2e5 + 10, mod = 998244353;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n, vector<int> (m));
    for(int i = 0; i < n; i ++) {
        string s;
        cin >> s;
        for(int j = 0; j < m; j ++) {
            v[i][j] = s[j] - '0';
        }
    }
    struct OP {
        int i, j, l, r, p;
    };
    int q;
    cin >> q;
    vector<OP> op(q);
    for(auto &[i, j, l, r, p] : op) {
        cin >> i >> j >> l >> r >> p;
    }
    int res = 0;
    for(int i = 0; i < m; i ++) {
        int c = 1;
        for(int j = 0; j < n; j ++) {
            c &= v[j][i];
        }
        res += c;
    }
    cout << res << '\n';
}

H 旋转水管

dfs模拟，分类讨论即可, 根据当前位置的水管形状以及上一位置水管的方向来判断下一位置的方向, 时间复杂度$O(m)$。

 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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e9 + 7, MAXN = 1e5 + 10, mod = 998244353;
int m, s, t;
char G[2][MAXN];
bool vis[3][MAXN];
/*
0 向下
1 向上
2 向左
3 向右
*/
bool res = 0;
void dfs(int x, int y, int type) {
    if(vis[x][y]) {
        return;
    }
    if(x < 0 || x >= 2 || y < 0 || y >= m) {
        if(x == 2 && y == t) {
            res = 1;
        }
        return;
    }
    vis[x][y] = 1;
    if(type == 1) {
        if(G[x][y] == 'I') {
            dfs(x + 1, y, type);
        } else {
            if(y >= 1)
                dfs(x, y - 1, 2);
            dfs(x, y + 1, 3);
        }
    } else if(type == 2) {
        if(G[x][y] == 'I') {
            if(y >= 1)
                dfs(x, y - 1, type);
        } else {
            if(x >= 1)
                dfs(x - 1, y, 0);
            dfs(x + 1, y, 1);
        }
    } else if(type == 3) {
        if(G[x][y] == 'I') {
            dfs(x, y + 1, type);
        } else {
            if(x >= 1)
                dfs(x - 1, y, 0);
            dfs(x + 1, y, 1);
        }
    } else {
        if(G[x][y] == 'I') {
            if(x >= 1)
                dfs(x - 1, y, type);
        } else {
            if(y >= 1)
                dfs(x, y - 1, 2);
            dfs(x, y + 1, 3);
        }
    }
    vis[x][y] = 0;
}
void solve() {
    cin >> m >> s >> t;
    s --, t --;
    for(int i = 0; i < 2; i ++) {
        for(int j = 0; j < m; j ++) {
            cin >> G[i][j];
        }
    }
    res = 0;
    dfs(0, s, 1);
    if(res) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _ = 1;
    cin >> _;
    while(_ --) {
        solve();
    }
    return 0;
}

I Oshwiciqwq 的电梯

大模拟，由于数据范围非常的小，可以确定每一秒的状态。

代码写得又臭又长，好在写了注释，应该可以看懂。

  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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e9 + 7, MAXN = 2e5 + 10, mod = 998244353;
PII t[3][10][10];   // 0  X, 1  Y ,2  Z; first 位置， second 编号
int v[510];         // 0 未上电梯，1在x电梯上，2在y电梯上，3在z电梯上
struct P {
    int tim;        // 出现时间
    int x, y, z;    // 当前位置
    int tx, ty, tz; // 目标位置
} p[60]; 
int n, m, h, q, k;
void work() {
    for(int i = 1; i <= m; i ++) {
        for(int j = 1; j <= h; j ++) {
            if(t[0][i][j].first > 0) {
                t[0][i][j].first %= n;
                t[0][i][j].first ++;
            }
        }
    }
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= h; j ++) {
            if(t[1][i][j].first >= 0) {
                t[1][i][j].first %= m;
                t[1][i][j].first ++;
            }
        }
    }
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            if(t[2][i][j].first >= 0) {
                t[2][i][j].first %= h;
                t[2][i][j].first ++;
            }
        }
    }
}
struct RES {
    int tt;
    int p;
    int io;
    int xl;
    int x, y, z;
    const bool operator < (const RES& a) const {
        if(tt != a.tt) return tt < a.tt;
        if(xl != a.xl) return xl < a.xl;
        if(io != a.io) return io < a.io;
        if(p != a.p) return p < a.p;
    }
};
vector<RES> res;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> h >> k;
    for(int i = 0; i < k; i ++) {
        int type, ex, ey, ez;
        cin >> type >> ex >> ey >> ez;
        if(type == 0) {
            t[type][ey][ez].first = ex;
            t[type][ey][ez].second = i;
        } else if(type == 1) {
            t[type][ex][ez].first = ey;
            t[type][ex][ez].second = i;
        } else {
            t[type][ex][ey].first = ez;
            t[type][ex][ey].second = i;
        }
    }
    cin >> q;
    for(int i = 0; i < q; i ++) {
        auto &[tim, x, y, z, tx, ty, tz] = p[i];
        cin >> tim >> x >> y >> z >> tx >> ty >> tz;
    }
    int tt = 0; // 当前时间戳
    bool ok = 0;
    do {
        ok = 0;
        for(int i = 0; i < q; i ++) {
            if(p[i].tim <= tt) {
                // 未进电梯
                if(v[i] == 0) {
                    if(p[i].x != p[i].tx) {
                        ok = 1;
                        if(t[0][p[i].y][p[i].z].first == p[i].x) {
                            res.push_back({tt, i + 1, 1 , t[0][p[i].y][p[i].z].second + 1, p[i].x, p[i].y, p[i].z});
                            v[i] = 1;
                            p[i].x %= n;
                            p[i].x ++;
                        }
                    } else if(p[i].y != p[i].ty) {
                        ok = 1;
                        if(t[1][p[i].x][p[i].z].first == p[i].y) {
                            res.push_back({tt, i + 1, 1 , t[1][p[i].x][p[i].z].second + 1, p[i].x, p[i].y, p[i].z});
                            v[i] = 2;
                            p[i].y %= m;
                            p[i].y ++;
                        }
                    } else if(p[i].z != p[i].tz) {
                        ok = 1;
                        if(t[2][p[i].x][p[i].y].first == p[i].z) {
                            res.push_back({tt, i + 1, 1 , t[2][p[i].x][p[i].y].second + 1, p[i].x, p[i].y, p[i].z});
                            v[i] = 3;
                            p[i].z %= h;
                            p[i].z ++;
                        }
                    }
                } else if(v[i] == 1) {
                    ok = 1;
                    if(p[i].x == p[i].tx) {
                        res.push_back({tt, i + 1, 0, t[0][p[i].y][p[i].z].second + 1, p[i].x, p[i].y, p[i].z});
                        v[i] = 0;
                    } else {
                        p[i].x %= n;
                        p[i].x ++;
                    }
                } else if(v[i] == 2) {
                    ok = 1;
                    if(p[i].y == p[i].ty) {
                        res.push_back({tt, i + 1, 0, t[1][p[i].x][p[i].z].second + 1, p[i].x, p[i].y, p[i].z});
                        v[i] = 0;
                    } else {
                        p[i].y %= m;
                        p[i].y ++;
                    }
                } else if(v[i] == 3) {
                    ok = 1;
                    if(p[i].z == p[i].tz) {
                        res.push_back({tt, i + 1, 0, t[2][p[i].x][p[i].y].second + 1, p[i].x, p[i].y, p[i].z});
                        v[i] = 0;
                    } else {
                        p[i].z %= h;
                        p[i].z ++;
                    }
                }
            } else {
                ok = 1;
            }
        }
        work();
        tt ++;
    } while (ok);
    sort(res.begin(), res.end());
    for(auto i : res) {
        // [time] Person person_id IN / OUT Elevator elevator_id at (x, y, z);
        if(i.io == 1) {
            cout << "[" << i.tt << "s] Person " << i.p << " IN Elevator " << i.xl << " at (" << i.x << ", " << i.y << ", " << i.z << ")\n";
        } else {
            cout << "[" << i.tt << "s] Person " << i.p << " OUT Elevator " << i.xl << " at (" << i.x << ", " << i.y << ", " << i.z << ")\n";

        }
    }
}