Theme NexT works best with JavaScript enabled

2019 牛客暑期多校训练营第四场题解

本文包括 2019 牛客暑期多校训练营第四场的题面与题解。

A - meeting

题目描述

A new city has just been built. There’re $ n $ interesting places numbered by positive numbers from $ 1 $ to $ n $ .

In order to save resources, only exactly $ n-1 $ roads are built to connect these $ n $ interesting places. Each road connects two places and it takes 1 second to travel between the endpoints of any road.

There is one person in each of the places numbered $ x_1,x_2 \ldots x_k $ and they’ve decided to meet at one place to have a meal. They wonder what’s the minimal time needed for them to meet in such a place. (The time required is the maximum time for each person to get to that place.)

输入描述

First line two positive integers $ n,k $ - the number of places and persons.

For each the following $ n-1 $ lines, there’re two integers $ a,b $ that stand for a road connecting place $ a $ and $ b $ . It’s guaranteed that these roads connected al $ n $ places.

On the following line there’re $ k $ different positive integers $ x_1,x_2 \ldots x_k $ separated by spaces. These are the numbers of places the persons are at.

输出描述

A non-negative integer - the minimal time for persons to meet together.

示例1

输入

1
2
3
4
5
4 2
1 2
3 1
3 4
2 4

输出

1
2

说明

They can meet at place $ 1 $ or $ 3 $ .

备注

$ 1 \leq n \leq 105 $

题解

题意

给定一棵树,树上的 $ k $ 个点为特殊点,要求你找到一个点,使得所有的特殊点到达该点的最远距离尽可能小。

解法

树形DP,计算出每一个点到最远特殊点的距离。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define N 100001
#define M 200001
int hd[N], nx[M], e[M];
int f[N], sum[N], s1[N], s2[N], s3[N];
bool v[N];
void dfs1(int x) {
int max1 = 0, max2 = 0;
for (int i = hd[x]; i; i = nx[i])
if (f[x] != e[i]) {
f[e[i]] = x;
dfs1(e[i]);
if (s1[e[i]])
if (s1[e[i]] + 1 >= max1)
max2 = max1, max1 = s1[e[i]] + 1;
else if (s1[e[i]] + 1 > max2)
max2 = s1[e[i]] + 1;
}
s1[x] = max1, s3[x] = max2;
if (v[x]) s1[x] = max(s1[x], 1);
}
void dfs2(int x) {
for (int i = hd[x]; i; i = nx[i])
if (f[x] != e[i]) {
s2[e[i]] = max(s2[x], s1[e[i]] + 1 == s1[x] ? s3[x] : s1[x]) + 1;
dfs2(e[i]);
}
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1, Num = 0, x, y; i < n; i++) {
scanf("%d%d", &x, &y);
nx[++Num] = hd[x], hd[x] = Num, e[Num] = y;
nx[++Num] = hd[y], hd[y] = Num, e[Num] = x;
}
for (int i = 1, x; i <= k; i++) {
scanf("%d", &x);
v[x] = true;
}
dfs1(1);
dfs2(1);
int ans = -1;
for (int i = 1; i <= n; i++) {
int x = max(s1[i], max(s2[i], s3[i])) - 1;
if (ans == -1 || ans > x) ans = x;
}
printf("%d\n", ans);
return 0;
}

B - xor

题目描述

Your are given $ n $ sets.Every set contains some integers.

We say a set can express an integer, only when there exists a subset of the set such that the bitwise-xor of the elements in the subset is equal to that integer.

Now you need to answer $ m $ queries. Each query will give you three integers $ l,r,x $ and you should answer if for every $ i \in [l,r] $ ,the $ i $ -th set can express $ x $ .

输入描述

The first line contains two integers $ n,m $ .

For each of the following $ n $ lines, the first integer $ sz $ stands for the size of this set and the following $ sz $ integers stand for the elements in this set. The sets are described from number $ 1 $ to $ n $ .

For each of the following $ m $ lines, there’re three integers $ l,r,x $ that means a query.

输出描述

For each query, output a line.

If for every $ i \in [l,r] $ ,the $ i $ -th set can express $ x $ , you need to print “YES”, and “NO” otherwise.

示例1

输入

1
2
3
4
5
1 3
2 1 2
1 1 0
1 1 3
1 1 4

输出

1
2
3
YES
YES
NO

备注

$ 1 \le n,m \le 50000 $ , $ 1 \le sz \le 32 $ , $ 1 \le l \le r \le n $ ,the every integer in input $ )\in [0,2^{32}) $ 。

题解

题意

给定 $ n $ 个集合以及 $ m $ 个询问,每次询问给定三个数 $ l $ , $ r $ 和 $ v $ ,询问任意的 $ i \in [l,r] $ 的集合,能否找出子集异或为 $ v $ 。

解法

线段树维护任意区间线性基交集。

代码

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
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 50010
#define INF 0x3f3f3f3f
#define mod 1000000007
struct LBasis {
ll d[33];
int tot;
void init() {
memset(d, 0, sizeof(d));
tot = 0;
}
bool insert(ll x) {
for (int i = 32; i >= 0; i--) {
if (x & (1LL << i)) {
if (d[i])
x ^= d[i];
else {
d[i] = x;
return true;
}
}
}
return false;
}

bool checkin(ll x) {
for (int i = 32; i >= 0; i--) {
if (x & (1LL << i)) {
if (d[i])
x ^= d[i];
else
return false;
}
}
return true;
}
};
LBasis intersection(const LBasis &a, const LBasis &b) {
LBasis ans, c = b, d = b;
ans.init();
for (int i = 0; i <= 32; i++) {
ll x = a.d[i];
if (!x) continue;
int j = i;
ll T = 0;
for (; j >= 0; --j) {
if ((x >> j) & 1)
if (c.d[j]) {
x ^= c.d[j];
T ^= d.d[j];
} else
break;
}
if (!x)
ans.d[i] = T;
else {
c.d[j] = x;
d.d[j] = T;
}
}
return ans;
}
LBasis node[N << 2];
void pushup(int rt) {
node[rt] = intersection(node[rt << 1], node[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
if (l == r) {
int sz;
scanf("%d", &sz);
node[rt].init();
while (sz--) {
ll x;
scanf("%lld", &x);
node[rt].insert(x);
}
return;
}
int m = (l + r) >> 1;
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
pushup(rt);
}
bool query(int L, int R, int l, int r, ll v, int rt) {
if (L <= l && R >= r) {
return node[rt].checkin(v);
}
int m = (l + r) >> 1;
bool ok = true;
if (L <= m) ok = ok && query(L, R, l, m, v, rt << 1);
if (R > m) ok = ok && query(L, R, m + 1, r, v, rt << 1 | 1);
return ok;
}
int main() {
int n, m, l, r;
ll x;
scanf("%d%d", &n, &m);
build(1, n, 1);
while (m--) {
scanf("%d%d%lld", &l, &r, &x);
printf("%s\n", query(l, r, 1, n, x, 1) ? "YES" : "NO");
}
return 0;
}

C - sequence

题目描述

Your are given two sequences $ a_{1 \dots n} $ and $ b_{1 \dots n} $ .You need to answer $ \displaystyle \max_{1 \le l \le r \le n} \{min(a_{l \dots r}) \times sum(b_{l \dots r})\} $ 。
Where $ min(a) $ means the minimal value of every element of sequence $ a $ , $ sum(a) $ means the sum of every element of sequence $ a $ .

输入描述

The first line contains an integer $ n $ .

The second line contains $ n $ integers meaning $ a_{1 \dots n} $ .

The third line contains n integers meaning $ b_{1 \dots n} $ .

输出描述

An integer meaning the answer.

示例1

输入

1
2
3
3
1 -1 1
1 2 3

输出

1
3

备注

For all test datas, $ 1 \leq n \leq 3 \times 10^6,-10^6 \leq a_i,b_i \leq 10^6 $ .

题解

题意

给定两个序列 $ a $ 和 $ b $ ,要求找到一个区间 $ [l,r] $ ,使得 $ a $ 序列在该区间中的最小值乘 $ b $ 序列在该区间的区间和的积尽可能大。

解法

枚举 $ a $ 序列中的每个值为最小值时的最大乘积,用线段树维护 $ b $ 序列前缀和以实现查询最大区间和的效果。

代码

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
#include <algorithm>
#include <iostream>
#define ll long long
using namespace std;
#define N 3000010
#define INF 0x3f3f3f3f3f3f3f3f
int n, m, l, r;
int a[N];
int L[N], R[N];
int b[N];
ll sum[N], tree_max[(N << 2) + 10];
ll tree_min[(N << 2) + 10];
void push_up(int index) {
tree_max[index] = max(tree_max[index << 1], tree_max[(index << 1) | 1]);
tree_min[index] = min(tree_min[index << 1], tree_min[(index << 1) | 1]);
}
void build(int left, int right, int index) {
if (left == right) {
tree_max[index] = sum[left];
tree_min[index] = sum[left];
return;
}
int mid = left + ((right - left) >> 1);
build(left, mid, index << 1);
build(mid + 1, right, (index << 1) | 1);
push_up(index);
}
ll query_max(int dis, int left, int right, int ql, int qr) {
ll res = -INF;
if (ql <= left && right <= qr) return tree_max[dis];
int mid = left + ((right - left) >> 1);
if (ql <= mid) res = max(res, query_max(dis << 1, left, mid, ql, qr));
if (qr > mid)
res = max(res, query_max((dis << 1) | 1, mid + 1, right, ql, qr));
return res;
}
ll query_min(int dis, int left, int right, int ql, int qr) {
ll res = INF;
if (ql <= left && right <= qr) return tree_min[dis];
int mid = left + ((right - left) >> 1);
if (ql <= mid) res = min(res, query_min(dis << 1, left, mid, ql, qr));
if (qr > mid)
res = min(res, query_min((dis << 1) | 1, mid + 1, right, ql, qr));
return res;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sum[1] = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &b[i]);
sum[i + 1] = sum[i] + b[i];
}
L[1] = 1;
R[n] = n;
for (int i = 2; i <= n; i++) {
L[i] = i;
while (a[L[i] - 1] >= a[i]) {
if (L[i] == 1) break;
L[i] = L[L[i] - 1];
}
}
for (int i = n - 1; i >= 1; i--) {
R[i] = i;
while (a[R[i] + 1] >= a[i]) {
if (R[i] == n) break;
R[i] = R[R[i] + 1];
}
}
build(1, n + 1, 1);
ll ans = -INF;
for (int i = 1; i <= n; i++) {
if (a[i] == 0)
ans = max(ans, 0LL);
else if (a[i] > 0)
ans = max(ans, a[i] * (query_max(1, 1, n + 1, i + 1, R[i] + 1) -
query_min(1, 1, n + 1, L[i], i)));
else if (a[i] < 0)
ans = max(ans, a[i] * (query_min(1, 1, n + 1, i + 1, R[i] + 1) -
query_max(1, 1, n + 1, L[i], i)));
}
printf("%lld\n", ans);
return 0;
}

D - triples I

题目描述

Doctor Elephant is testing his new program: output the bitwise or of the numbers inputed.

He has decided to input several multiples of $ 3 $ and the output of the program should be his favorite umber $ a $ .

Because he is lazy, he decided to input as few numbers as possible. He wants you to construct such an input for every $ a $ he chose.

It’s guaranteed that for every aaa in the input there is such a solution. If there’re multiple solutions you can output any.

输入描述

There’re multiple test cases in a test file.

The first line contains a positive integer $ T $ - the number of test cases.

In each of the following $ T $ lines there is one positive integer $ a $ .

输出描述

For each test case output a line. First you need to output the number of numbers in your input, and then you need to output these numbers, separating by spaces.

示例1

输入

1
2
3
2
3
7

输出

1
2
1 3
2 3 6

说明

$ 3=3, (3|6)=7 $

备注

$ 1 \le T \le 10^5, 1 \leq a \leq 10^18 $ .

E - triples II

题目描述

Doctor Elephant is testing his new program: output the bitwise or of the numbers inputed.

He has decided to input nnn multiples of $ 3 $ and the output of the program should be his favorite number $ a $ .

He wants to know how many possible sequences are there. Because the answer can be large, you only need to output the answer modulo $ 998244353 $ .

输入描述

There’re multiple test cases in a test file.

The first line contains a positive integer $ T $ - the number of test cases.

In each of the following $ T $ lines there’re two non-negative integers $ n $ and $ a $ .

输出描述

For each test case output a line - the number of such sequences modulo $ 998244353 $ .

示例1

输入

1
2
3
4
3
3 3
2 7
233 333

输出

1
2
3
7
2
650745136

备注

$ 1 \le T \le 500 $ , $ 1 \leq n \leq 10^{18} $ , $ 0 \leq a \leq 10^{18} $ .

题解

题意

给定 $ n $ 和 $ a $ ,询问你用 $ n $ 个 $ 3 $ 的整倍数(包括 $ 0 $ )按位或运算得到数字 $ a $ 的方案数有多少种。

解法

将这 $ n $ 个数和 $ a $ 二进制拆分,对于 $ a $ 的每一位,这 $ n $ 个数对应位置上至少有一个 $ 1 $ 即可。

那么考虑 $ a $ 的二进制位的每一个 $ 1 $ ,分为几个集合。使得这些数都为 $ 3 $ 的倍数,考虑方案数,用容斥原理去重。

$ S_{i,j} $ 表示分的集合包含 $ i $ 个模 $ 3 $ 为 $ 1 $ , $ j $ 个模 $ 3 $ 为 $ 2 $ 的分法数量。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 64
#define mod 998244353
ll C[N][N], S[N][N];
ll Qpow(ll a, ll b, ll c) {
a = a % c;
ll res = 1;
while (b) {
if (b & 1) res = res * a % c;
b >>= 1;
a = a * a % c;
}
return res % c;
}
void Prepare() {
for (int i = 0; i < N; i++) C[i][0] = C[i][i] = 1;
for (int i = 1; i < N; i++)
for (int j = 1; j <= i; j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int p = 0; p <= i; p++)
for (int q = 0; q <= j; q++)
if ((p + 2 * q) % 3 == 0)
S[i][j] = (S[i][j] + C[i][p] * C[j][q] % mod) % mod;
S[0][0] = 1;
}
int main() {
Prepare();
int T;
scanf("%d", &T);
while (T--) {
ll n, a, x = 0, y = 0;
scanf("%lld%lld", &n, &a);
for (int i = 0; i < N; i++)
if (a & (1ll << i)) (i & 1 ? x : y)++;
ll ans = 0;
for (int i = 0; i <= x; i++)
for (int j = 0; j <= y; j++) {
ll tmp = C[x][i] * C[y][j] % mod * Qpow(S[i][j], n, mod) % mod;
if ((x + y - i - j) & 1) tmp = -tmp;
ans = (ans + tmp + mod) % mod;
}
printf("%lld\n", ans);
}
return 0;
}

F - merge

题目描述

a is a permutation of $ 1 \dots N $ , the original values are given.

There are $ M $ operations, each of them is of one of two types:

1 l m r, means replacing $ a_{l \dots r} $ with $ merge(a_{l \dots m},a_{m+1 \dots r}) $ .

2 i, means that you need to answer the value $ a_i $ .

Where $ merge(a,b) $ means the following code:

1
2
3
4
5
6
7
8
9
10
def merge(a, b):
c = []
while a.size() and b.size():
if a[0] < b[0]:
c.append(a[0])
a.pop_front()
else:
c.append(b[0])
b.pop_front()
return c+a+b

输入描述

The first line contains two integer $ N,M $ .

The second line contains $ N $ integers $ a_{1 \dots N} $ .

For the following $ M $ lines, each line is of format 1 l m r or 2 i .

输出描述

For each operation of the second type, output a line containing the answer.

示例1

输入

1
2
3
4
5
5 3
2 3 1 4 5
2 3
1 1 3 5
2 3

输出

1
2
1
1

题解

题意

给定一个字符串,求该串的不重复的回文子串的数量。

解法

先利用后缀数组求出s#rev(s)的不相等子串个数,再扣掉包含字符#的子串个数,包含#’的子串个数为 $ (len(s)+1)^2 $ 。具体取法为以#及左边任意字符为起点,以#及右边字符为终点构成的串,显然这样能取出所有包含#的子串,且这些子串都不相等。
所以求出来结果是:

这样求出来的结果是包含a = rev(b)的,比如s = abac,求出来的结果是a,b,c,ab,ba,ac,ca,cab,aba,bac,abac,cabaa,b,c,ab,ba,ac,ca,cab,aba,bac,abac,caba,可以看出除了a,b,c,abaa,b,c,aba这几个回文串,剩余的串都是成对的,那么我们用回文树求出s本质不同的回文串个数加上之前的 $ ans $ 再除以 $ 2 $ 就是答案了。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 400010
template <typename _tp>
inline _tp read(_tp& x) {
char ch = getchar(), sgn = 0;
x = 0;
while (ch ^ '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') ch = getchar(), sgn = 1;
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
if (sgn) x = -x;
}
char str[N];
int s[N];
ll ans;
struct SAM {
int l[N << 1], fa[N << 1], nxt[N << 1][30];
int last, cnt;

void Init() {
ans = 0;
last = cnt = 1;
l[cnt] = fa[cnt] = 0;
memset(nxt[cnt], 0, sizeof(nxt[cnt]));
}

int NewNode() {
++cnt;
memset(nxt[cnt], 0, sizeof(nxt[cnt]));
l[cnt] = fa[cnt] = 0;
return cnt;
}

void Insert(int ch) {
int np = NewNode(), p = last;
last = np;
l[np] = l[p] + 1;
while (p && !nxt[p][ch]) nxt[p][ch] = np, p = fa[p];
if (!p)
fa[np] = 1;
else {
int q = nxt[p][ch];
if (l[p] + 1 == l[q])
fa[np] = q;
else {
int nq = NewNode();
memcpy(nxt[nq], nxt[q], sizeof(nxt[q]));
fa[nq] = fa[q];
l[nq] = l[p] + 1;
fa[np] = fa[q] = nq;
while (nxt[p][ch] == q) nxt[p][ch] = nq, p = fa[p];
}
}
ans += 1ll * (l[last] - l[fa[last]]);
}

} SAM;

struct Palindromic_Tree {
int next[N][26], fail[N], cnt[N], num[N], len[N], S[N];
int last, n, p;
int newnode(int l) {
for (int i = 0; i < 26; i++) next[p][i] = 0;
cnt[p] = 0;
num[p] = 0;
len[p] = l;
return p++;
}
void Init() {
p = 0;
newnode(0);
newnode(-1);
last = 0, n = 0, S[n] = -1, fail[0] = 1;
}

int get_fail(int x) {
while (S[n - len[x] - 1] != S[n]) x = fail[x];
return x;
}

void add(int c) {
S[++n] = c;
int cur = get_fail(last);
if (!next[cur][c]) {
int now = newnode(len[cur] + 2);
fail[now] = next[get_fail(fail[cur])][c];
next[cur][c] = now;
num[now] = num[fail[now]] + 1;
}
last = next[cur][c];
cnt[last]++;
}
ll count() {
ll res = p * 1ll;
for (int i = p - 1; i >= 0; --i) cnt[fail[i]] += cnt[i];
return (res - 2);
}
} PAM;
int main() {
scanf("%s", str + 1);
int len = strlen(str + 1);
SAM.Init();
for (int i = 1; i <= len; i++) SAM.Insert(str[i] - 'a');
SAM.Insert(28);
for (int i = len; i > 0; --i) SAM.Insert(str[i] - 'a');
ans -= (ll)(len + 1) * (len + 1);
PAM.Init();
for (int i = 1; i <= len; i++) PAM.add(str[i] - 'a');
ans += PAM.count();
printf("%lld\n", (ans / 2ll));
return 0;
}

G - tree

题目描述

You are given a tree $ A $ of $ n $ nodes.

There are $ m $ queries.

In each query, you are given a tree $ B $ of $ m $ nodes and you have to answer how many connected subgraphs of $ A $ is isomorphic to $ B $ .

Because the answer may be too large, you only need to output it modulo $ 10^9+7 $ .

输入描述

The first line contains an integer $ n $ .

The next $ n-1 $ lines,each line contains two integers - the endpoints of an edge of $ A $ .

The next line, an integer $ t $ - the number of queries.

For each query:

The first line contains an integer $ m $ .

For each of the next $ m-1 $ lines, each line contains two integer - the endpoints of an edge of $ B $ .

输出描述

For each query, output a line containing one integer that stands for the answer.

示例1

输入

1
2
3
4
5
6
7
4
1 2
1 3
1 4
1
2
1 2

输出

1
3

备注

For all test datas, $ n \leq 2000 $ , $ t \leq 10000 $ , $ m \leq 12 $ .

H - RNGs

题目描述

The relationship between Byteland and Bitland is on thin ice and a war is certained to start. The message of your agent shows that the communication in Bitland is encrypted. They’ve chosen three different RNGs (Random Number Generators) that can produce a sequence of 0s and 1s.

At the start of every day, they’ll randomly pick one RNG, pick one random seed and use that RNG to generate a binary sequence of length 2000. This sequence will act as an encryption key.

As an officer of Byteland, rather than decrypt the datas, you’ve decided to solve an easier problem first: for an encyption key generated, figure out which RNG is used to generate it.

The following is a sample code of these three RNGs written in the out-dated language, C++ (it’s recommend to copy-paste the following code to your favorite editor):

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
typedef unsigned int u32;
typedef unsigned long long u64;
struct RNG {
virtual void srand(u32 seed) = 0;
virtual bool gen() = 0;
};
struct RNG0 : RNG {
u32 x;
void srand(u32 seed) { x = seed; }
bool gen() {
x = x * 214013u + 2531011u;
return (x >> 28) & 1;
}
};
struct RNG1 : RNG {
int index;
u32 mt[624];
void srand(u32 seed) {
mt[0] = seed;
index = 624;
for (int i = 1; i < 624; ++i)
mt[i] = 1812433253u * (mt[i - 1] ^ (mt[i - 1] >> 30)) + i;
}
void twist() {
for (int i = 0; i < 624; ++i) {
u32 y = (mt[i] & 0x80000000u) + (mt[(i + 1) % 624] & 0x7fffffffu);
mt[i] = mt[(i + 397) % 624] ^ (y >> 1);
if (y & 1) mt[i] ^= 0x9908b0df;
}
index = 0;
}
bool gen() {
if (index >= 624) twist();
u32 y = mt[index];
y ^= y >> 11;
y ^= (y << 7) & 2636928640u;
y ^= (y << 15) & 4022730752u;
y ^= y >> 18;
++index;
return (y >> 16) & 1;
}
};
struct RNG2 : RNG {
u64 x;
void srand(u32 seed) { x = seed; }
bool gen() {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return (x >> 16) & 1;
}
};
RNG *rng[3] = {new RNG0(), new RNG1(), new RNG2()};

输入描述

The first line contains the number of test cases $ T $ . In real data, $ T=1000 $ .

Each of the following $ T $ lines contain a binary string of length $ 2000 $ - an encryption key.

输出描述

Output $ T $ lines, for the $ i $ -th encryption key in the input, output $ 0 $ if its generated using RNG0, $ 1 $ if generated using RNG1 and $ 2 $ if generated using RNG2.

示例1

输入

1
2
1
00111011000010101110100010010000000111010010100001101111001110001100100110100000011100110010010010101100011001110000010000010100001101000001011100111100001010011110101110000101011000010100110111100100111101011001011000110001100111111000111101010000010100001010011101001011110101101110001100011010110101010110011101011001101010001010011100100101101111111000000011010111000000111010101101110001001001000100001101111011100010010000101010101000111010000001101101010101101101011011001101011011001101111111011101001100101011101000110001100111100001010010001101101010000101001010000101010010010110111001111110101101110000011000011111011101011001110100110101011110101110001110110110001001111001000010001100001000110100101100100101100000011111110010000110111111100001001100011010111010001100101100110110110101110111110101101001100011001010100000110001111110111001110010000111111010010110011010111001011011100000100010100010110011000011110100001100111110110011100101101110011010010011101100100101010101111110000000011111101011110101001001111001100101110111101000110110010110111010111110111011010011101110100111100011010010111101100010101111100001010000100100010011111110001000011001101101110110010011010010000100111001110101001111100110011101010100001001100000100111110001101010101010000110111001100000001100110000001010000101111001010110001110000100100101011110001010000110010100010101001100101111110111001101110000101101001100011111100110001000111100100011101011010011111101001100110010110111001101000101001111011000110001000000101011100110111011111010011010011100011000010100011111001110111000011100101100010110011010001001001000001011110101110001011001001001100011010001011000001011000111101010010001001010100101010101110010101001111110001001110110010101011100001001010010100101000101111111101110001011101101110011111101100001001100101101100011101010010110101000001001100100101110111101100000000110001110100101011110010001010011011110111111001100110000101011111100011001111111100001110000001100100001000010

输出

1
0

说明

The sample is generated using RNG0 with $ s=123 $ . Please note that this test case is only a sample and won’t be included in the testing.

备注

Your program will be tested on one test data containing $ 1000 $ test cases. Each test case is generated randomly: first randomly pick between (*rng[0],*rng[1],*rng[2]) , and randomly pick an integer s between $ [0,109] $ , do srand(s), then call gen() $ 2000 $ times and take the outputed sequence.

You must answer correctly for at least $ 990 $ test cases. It’s worth noting that even if you’re unsure of the number of some certain test case, you still need to output $ 0,1 \ or\ 2 $ , or you may get Wrong Answer verdict.

I - string

题目描述

We call $ a,b $ non-equivalent if and only if $ a \neq b $ and $ a \neq rev(b), $ where $ rev(s) $ refers to the string obtained by reversing characters of $ s $ , for example $ rev(abca)=acba $ .

There is a string $ s $ consisted of lower-case letters. You need to find some substrings of $ s $ so that any two of them are non-equivalent. Find out what’s the largest number of substrings you can choose.

输入描述

A line containing a string $ s $ of lower-case letters.

输出描述

A positive integer - the largest possible number of substrings of $ s $ that are non-equivalent.

示例1

输入

1
abac

输出

1
8

说明

The set of following substrings is such a choice: $ abac,b,a,ab,aba,bac,ac,c $ .

备注

$ 1≤∣s∣≤2×105 $ , $ s $ is consisted of lower-case letters.

J - free

题目描述

Your are given an undirect connected graph.Every edge has a cost to pass.You should choose a path from $ S $ to $ T $ and you need to pay for all the edges in your path. However, you can choose at most $ k $ edges in the graph and change their costs to zero in the beginning. Please answer the minimal total cost you need to pay.

输入描述

The first line contains five integers $ n,m,S,T,K $ .

For each of the following $ m $ lines, there are three integers $ a,b,l $ , meaning there is an edge that costs $ l $ between $ a $ and $ b $ .

$ n $ is the number of nodes and $ m $ is the number of edges.

输出描述

An integer meaning the minimal total cost.

示例1

输入

1
2
3
3 2 1 3 1
1 2 1
2 3 2

输出

1
1

备注

$ 1 \le n,m \le 10^3,1 \le S,T,a,b \le n,0\le k\le m,1\le l\le10^6 $ .
Multiple edges and self loops are allowed.

题解

题意

给定一张无向图,允许重边与自环。再给定起点 $ s $ ,终点 $ t $ 和一个整数 $ k $ ,表示你可以将图中的 $ k $ 条边的权值变为 $ 0 $ 。现在询问你从 $ s $ 到 $ t $ 的最短路径长度。

解法

分层图解决,在原有路径的基础上新建 $ k $ 层路径,第 $ i $ 层可以通过无代价去 $ i+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
#include <bits/stdc++.h>
using namespace std;
#define N 1010
#define M 2010
#define Pii pair<int, int>
#define MPii(x, y) make_pair(x, y)
#define Inf 0x3f3f3f3f
struct Graph {
int Head[N], Next[M], End[M], Weight[M], Dist[N][N], Num;
bool vis[N][N];
void clear(int n) {
Num = 0;
for (int i = 0; i <= n; i++) {
Head[i] = 0;
for (int j = 0; j <= n; j++) Dist[i][j] = Inf, vis[i][j] = false;
}
}
void AddEdge(int x, int y, int w) {
Next[++Num] = Head[x], Head[x] = Num, End[Num] = y, Weight[Num] = w;
}
void Dijkstra(int s, int n, int k) {
priority_queue<Pii, vector<Pii>, greater<Pii> > Que;
Que.push(MPii(0, s - 1));
Dist[s][0] = 0;
while (!Que.empty()) {
int u = Que.top().second;
Que.pop();
int c = u / n;
u = u % n + 1;
if (vis[u][c]) continue;
vis[u][c] = true;
for (int i = Head[u]; i; i = Next[i]) {
int v = End[i], w = Weight[i];
if (!vis[v][c])
if (Dist[v][c] > Dist[u][c] + w) {
Dist[v][c] = Dist[u][c] + w;
Que.push(MPii(Dist[v][c], v + c * n - 1));
}
if (c != k && !vis[v][c + 1])
if (Dist[v][c + 1] > Dist[u][c]) {
Dist[v][c + 1] = Dist[u][c];
Que.push(MPii(Dist[v][c + 1], v + (c + 1) * n - 1));
}
}
}
}
} G;
int main() {
int n, m, s, t, k;
scanf("%d%d%d%d%d", &n, &m, &s, &t, &k);
G.clear(n);
for (int i = 1, x, y, z; i <= m; i++) {
scanf("%d%d%d", &x, &y, &z);
G.AddEdge(x, y, z);
G.AddEdge(y, x, z);
}
G.Dijkstra(s, n, k);
int ans = Inf;
for (int i = 0; i <= k; i++) ans = min(ans, G.Dist[t][i]);
printf("%d\n", ans);
return 0;
}

K - number

题目描述

300iq loves numbers who are multiple of $ 300 $ .

One day he got a string consisted of numbers. He wants to know how many substrings in the string are multiples of $ 300 $ when considered as decimal integers.

Note that leading and trailing zeros are allowed (both in original string and substrings you chose) and the same substring appearing in different places can be counted multiple times.

输入描述:

A single line consisting a string consisted of characters '0' to '9'.

输出描述:

The number of substrings that are multiples of $ 300 $ when considered as decimal integers.

示例1

输入

1
600

输出

1
4

说明

'600', '0', '0', '00' are multiples of $ 300 $ . (Note that '0' are counted twice because it appeared two times)

示例2

输入

1
123000321013200987000789

输出

1
55

备注

let the string in the input be $ s $ , $ 1 \leq |s| \leq 10^5 $ .

题解

题意

给定一个仅包含数字的字符串,求其中能被 $ 300 $ 整除的子串的数量。

解法

能被 $ 300 $ 整除的数必然末尾两数均为 $ 0 $ ,那么只要第一位数不为零,且各位数之和为 $ 3 $ 的倍数即可。

那么问题转化为,给定一个序列,询问有多少子串满足各位之和为 $ 3 $ 的整倍数,且该子串后两位均为 $ 0 $ 。

同时注意到单个的 $ 0 $ 也符合条件,需要特判一下。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100010
char a[N];
int s[N];
ll ans = 0;
map<int, int> mp;
int main() {
mp[0] = 1;
scanf("%s", a + 1);
int n = strlen(a + 1), add = 0;
for (int i = 1; i <= n; i++) {
s[i] = (s[i - 1] + a[i] - '0') % 3;
if (a[i] == '0') {
ans++;
if (a[i + 1] == '0') ans += (ll)mp[s[i]];
}
mp[s[i]]++;
}
printf("%lld\n", ans);
return 0;
}