忘了把账号密码记下来了,所以就记一下思路,只有几道补题的代码。

A. Who is better?

 

斐波那契博弈+扩展中国剩余定理

扩展中国剩余定理已经收入模板

 

B. so easy

 

用线段树大小不够。

这里提供标程的解法
q的值比较小,所以解题应该从q入手
用并查集模拟实现一个链表
用map模拟并查集,初始时每个点的父亲指向后面第一个可用的点。 当删除一个点i时,令x的父亲等于x+1的父亲 查询时直接输出 x 的父亲.

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
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 100;
unordered_map<int, int> fa;

int findfa(int x) {
if (!fa.count(x)) return x;
return fa[x] = findfa(fa[x]);
}


int main() {
int n, q;
scanf("%d %d", &n, &q);
int op, x;
while (q--) {
scanf("%d %d", &op, &x);
if (op == 1) {
fa[x] = findfa(x + 1);
} else {
int ans = findfa(x);
if (ans > n) ans = -1;
printf("%d\n", ans);
}
}
return 0;
}

 

C. Buy Watermelon

 

签到题,分是否为2的倍数讨论。

 

D. Carneginon

 

直接每次都kmp比较,时间是够的。

 

E. XKC’s basketball team

 

这题就可以用权值线段树了,记每个数的下标,找到符合条件,且下标最大的点,优先右子树查找。

 

G. Colorful String

 

回文自动机裸题,但因为当时不会只好赛后补了。

就是要求每个回文串中不同字符的个数以及该串出现次数。

出现次数,回文自动机已经求好了,接下来求回文串中不同字符的个数。

在树上沿着next或者叫child指针dfs,设置一个vis[26],记录每种字母是否出现对当前节点,若出边有节点,则进入,若该出边字母vis=0,则进入的节点val值+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
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6 + 10;
typedef pair<int, int> pii;
ll ans;
char s[maxn];
struct tree {
int fail[maxn], len[maxn], ch[maxn][26], cnt[maxn];
int last = 0, tot = 0, n = 0;
int newnode(int x) {
len[tot] = x;
return tot++;
}
int get_fail(char* s, int x, int n) {
while (s[n - len[x] - 1] != s[n])x = fail[x];
return x;
}
int work(char s[]) {
s[0] = -1;
newnode(0); newnode(-1);
fail[0] = 1;
for (n = 1; s[n]; ++n) {
s[n] -= 'a';
int cur = get_fail(s, last, n);
if (!ch[cur][s[n]]) {
int t = newnode(len[cur] + 2);
fail[t] = ch[get_fail(s, fail[cur], n)][s[n]];
ch[cur][s[n]] = t;
}
cnt[last = ch[cur][s[n]]]++;
}
for (int i = tot - 1; i >= 0; i--) {
cnt[fail[i]] += cnt[i];
}
return tot;
}
}T;
bool vis[26];
int val[maxn];
void cal(int p) {
bool flg = 0;
for (int i = 0; i < 26; i++) {
if (T.ch[p][i]) {
flg = 1;
if (vis[i]) {
int to = T.ch[p][i];
val[to] = val[p];
cal(to);
}
else {
int to = T.ch[p][i];
vis[i] = 1;
val[to] = val[p] + 1;
cal(to);
vis[i] = 0;
}
}
}
if (!flg)return;
}
int main() {
cin.sync_with_stdio(false);
cin >> s + 1;
int tot = T.work(s);
cal(0);
cal(1);
for (int i = 2; i < tot; i++) {
ans += T.cnt[i] * val[i];
}
cout << ans << endl;
return 0;
}

 

I. query

 

用筛法nlogn地处理出满足条件的数对,接下来就是二维偏序问题。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
typedef pair<int, int> pii;
int n, m;
int pos[maxn];
ll sum[maxn];
struct X
{
int l, r;
int ask;
};
bool cmp(X a, X b) {
return a.l != b.l ? a.l > b.l:a.ask < b.ask;
}
vector<X>vc;
ll ans[maxn];
int lowbit(int x) {
return x & -x;
}
void add(int x) {
for (int i = x; i <= n; i += lowbit(i)) {
sum[i]++;
}
}
ll query(int r) {
ll res = 0;
for (int i = r; i > 0; i -= lowbit(i)) {
res += sum[i];
}
return res;
}
int main() {
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int u;
cin >> u;
pos[u] = i;
}
for (int i = 1; i <= n; i++) {
int tmp = 2 * i;
while (tmp <= n) {
vc.push_back(X{ min(pos[i],pos[tmp]),max(pos[i],pos[tmp]),0 });
tmp += i;
}
}
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
vc.push_back(X{ l,r,i });
}
sort(vc.begin(), vc.end(), cmp);
for (int i = 0; i < vc.size(); i++) {
X p = vc[i];
if (p.ask == 0) {
add(p.r);
}
else {
ans[p.ask] = query(p.r);
}
}
for (int i = 1; i <= m; i++) {
cout << ans[i] << endl;
}
return 0;
}

 

M. Longest subsequence

 

要求字典序大于给定字符串t的s的子序列个数。

预处理出s串中每个位置i后面字符c最近出现的位置。

初始时两个指针分别指向s,t最左端。

遍历字符串s,在每个位置都找它后面最仅大于t中对应位置字符的位置,该位置后所有字符都可以加入序列。

位置更新,t指针右移,s指针找到当前位置后最近的t指针指向的字符在s中的位置

若s指针找不到下一个位置,则跳出遍历。

若t指针指到了t串末尾,说明t是s的子序列,则若s指针后还有字符,则把这些字符都加上,组成的序列字典序也大于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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, int> pii;
const int maxn = 1e6 + 5;
char s[maxn], t[maxn];
int n, m, ans;
int a[maxn][26];
int main() {
cin.sync_with_stdio(false);
cout.tie(0);
cin >> n >> m;
cin >> (s + 1) >> (t + 1);
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < 26; j++) {
if (s[i + 1] == 'a' + j)
a[i][j] = i + 1;
else a[i][j] = a[i + 1][j];
}
}
int pos = 0;
bool flg = 0;
for (int i = 1; i <= m; i++) {
int c = t[i] - 'a';
for (int j = c + 1; j < 26; j++) {
if (a[pos][j] == 0)continue;
ans = max(ans, i + n - a[pos][j]);
}
pos = a[pos][c];
if (pos == 0) {
flg = 1;
break;
}
}
if (!flg&&pos!=n)ans = max(ans, m + n - pos);
if (ans == 0)cout << -1 << endl;
else cout << ans << endl;
return 0;
}