C. The Story of Emperor Bie
找 max，输出所有 max 位置。
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 2e5 + 7, mod = 1e9 + 7;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
int mx = -1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, a[i]);
}
for (int i = 1; i <= n; i++) {
if (a[i] == mx) cout << i << " ";
}
cout << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
K. LR String
队长思路：
t开头是L：s最左侧的L
t开头是R：s第一个必须是R
t结尾是L：s最后一个必须是L
t结尾是R：s最右侧的R
然后去掉开头结尾又是一个子问题
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
|
#include <bits/stdc++.h>
using namespace std;
#define rep(x,l,r) for(ll x=l;x<=r;++x)
#define per(x,r,l) for(ll x=r;x>=l;--x)
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
// #define max(x,y) ((x)<(y)?(y):(x))
// #define min(x,y) ((x)>(y)?(y):(x))
typedef long long ll;
typedef double db;
typedef __int128 i128;
const ll N=1e6+7,M=1e6+7,mod=998244353;
const ll inf=1e18;
const db eps=1e-8,pi=acos(-1.0);
int nx[N][2];
void solve()
{
string s,t;
cin>>s;
int q,n=s.length();
cin>>q;
nx[n][0]=nx[n][1]=-1;
per(i,n-1,0) {
nx[i][0]=nx[i+1][0];
nx[i][1]=nx[i+1][1];
if(s[i]=='L') nx[i][0]=i;
else nx[i][1]=i;
}
while(q--) {
cin>>t;
if((t[0]=='R'&&s[0]!='R')||(t.back()=='L'&&s.back()!='L')) {
printf("NO\n");
continue;
}
int now=0,ans=1;
for(auto x:t) {
if(x=='L') now=nx[now][0];
else now=nx[now][1];
if(now==-1) {
ans=0;
break;
}
++now;
}
if(ans) printf("YES\n");
else printf("NO\n");
}
}
signed main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);
int T=1;
cin>>T;
while(T--) {
solve();
}
return 0;
}
|
开牢了
L. Flipping Paths
首先容易想到枚举最终状态颜色，分别考虑。
接着考虑如何进行操作:
每一行都先移动到最右侧不为目标色的地方，这样之后不会再移动到他。
然后往下重复操作，最后一行一定移动到 m，最多有 400 次操作即可。
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;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n, m;
cin >> n >> m;
vector<string> g(n + 1);
for (int i = 1; i <= n; i++) {
cin >> g[i];
g[i] = " " + g[i];
}
auto check = [&](char T) {
vector<vector<int>> tmp(n + 1, vector<int>(m + 1, 0));
vector<string> ans;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
tmp[i][j] = (g[i][j] != T);
}
}
while (ans.size() <= 400) {
bool ok = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (tmp[i][j]) {
ok = 0;
break;
}
}
}
if (ok) break;
string way = "";
int y = 1;
for (int i = 1; i <= n; i++) {
int lst = -1;
for (int j = m; j > 0; j--) {
if (tmp[i][j]) {
lst = j;
break;
}
}
if (i == n) lst = m;
while (y < lst) {
tmp[i][y] ^= 1;
way.push_back('R');
y++;
}
tmp[i][y] ^= 1;
if (i != n) {
way.push_back('D');
}
}
ans.push_back(way);
}
if (ans.size() <= 400) {
cout << "YES\n";
cout << ans.size() << endl;
for (auto &s : ans) {
cout << s << endl;
}
return 1;
}
return 0;
};
bool ok = check('B');
if (!ok) {
ok = check('W');
}
if (!ok) {
cout << "NO\n";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
H. Mah-jong
首先注意到 a 数组范围极小，仅 8 种，易想到状压。
同时，观察题目中的两种组合，Peng 不会对其他造成影响，那么 Chow 是关键。
每种 Chow 最多出现 2 次，一共有 6 种 Chow。一共有 $3^6$ 种可能。
先将 729 种状态需要的每种数字的数量统计出来。
接着从左往右遍历数组，记录当前位置 i 之前每种数出现的次数，同时判断每种状态能否在当前位置满足。
找到满足当前状态的最左侧，储存 8 种数剩余的个数状压。
接着再来一遍计数即可
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
vector<int> pw3(9, 1);
vector<array<int, 8>> chows;
void init() {
for (int i = 1; i < 9; i++) pw3[i] = pw3[i - 1] * 3;
auto dfs = [&](auto self, int p, array<int, 8> &cur) {
if (p == 6) {
chows.push_back(cur);
return;
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cur[p + j] += i;
}
self(self, p + 1, cur);
for (int j = 0; j < 3; j++) {
cur[p + j] -= i;
}
}
};
array<int, 8> cur{};
dfs(dfs, 0, cur);
}
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), mdy[n + 1], bkt(pw3[8], 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i]--;
}
auto find = [&](const array<int, 8> &s) {
int mask = 0;
for (int i = 0; i < 8; i++) {
mask += s[i] % 3 * pw3[i];
}
return mask;
};
array<int, 8> pre{};
vector<int> num[8];
for (int i = 1; i <= n; i++) {
pre[a[i]]++;
num[a[i]].push_back(i);
for (auto cur : chows) {
bool flag = 1;
for (int j = 0; j < 8; j++) {
if (pre[j] < cur[j]) {
flag = 0;
break;
}
}
if (!flag) continue;
int pos = i;
for (int j = 0; j < 8; j++) {
if (cur[j]) {
pos = min(pos, num[j][(int)num[j].size() - cur[j]]);
}
}
int mask = 0;
for (int j = 0; j < 8; j++) {
mask += (pre[j] % 3 - cur[j] % 3 + 3) % 3 * pw3[j];
}
mdy[pos - 1].push_back(mask);
}
}
for (int i = 0; i < 8; i++) pre[i] = 0;
int mask = find(pre);
bkt[mask]++;
ll ans = 0;
for (int i = 1; i <= n; i++) {
for (auto mask : mdy[i - 1]) {
ans += bkt[mask];
}
pre[a[i]]++;
int mask = find(pre);
bkt[mask]++;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init();
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
G. Yelkrab
易想到 Trie 树来解决。
某个队伍的 LCP 就是所有人都走到 Trie 树中的某个节点。
那么我们将所有队伍都扔到 Trie 树中，对于其中某个节点，我们只关心有多少个 Piggy 能到达这个点，记为 cnt 个。
按照每队 j 个人拆分，当前节点能分成 $\left\lfloor \frac{cnt}{j} \right\rfloor$ 个队伍，其贡献其实也就是 $\left\lfloor \frac{cnt}{j} \right\rfloor$
我们将所有的点 $\left\lfloor \frac{cnt}{j} \right\rfloor$ 加起来，就是 $f_{i, j}$
当新串插入，某点 cnt 增加后，哪些点会产生变化？
向下取整，假设当前值变为 t，有变化的只会是 t 的因子，因为刚好整除使得贡献加一。
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 5e5 + 7, mod = 1e9 + 7;
struct Node {
vector<int> nxt;
int cnt;
Node() : nxt(26, 0), cnt(0) {}
};
vector<int> divs[N];
void init() {
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j += i) {
divs[j].push_back(i);
}
}
}
void solve() {
int n;
cin >> n;
vector<Node> tr(1);
vector<ll> f(n + 1, 0), ans;
ll res = 0;
string s;
auto insert = [&](const string &s) {
int p = 0;
for (char c : s) {
int u = c - 'a';
if (!tr[p].nxt[u]) {
tr[p].nxt[u] = tr.size();
tr.emplace_back();
}
p = tr[p].nxt[u];
int tmp = ++tr[p].cnt;
for (int d : divs[tmp]) {
res ^= f[d] * d;
f[d]++;
res ^= f[d] * d;
}
}
ans.push_back(res);
};
for (int i = 1; i <= n; i++) {
cin >> s;
insert(s);
}
for (auto x : ans) cout << x << " ";
cout << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init();
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|