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

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

A - String

题目描述

A string is perfect if it has the smallest lexicographical ordering among its cyclic rotations.

For example: 0101 is perfect as it is the smallest string among (0101, 1010, 0101, 1010).

Given a 01 string, you need to split it into the least parts and all parts are perfect.

输入描述

The first line of the input gives the number of test cases, $ T\ (T \leq 300) $ . $ T $ test cases follow.

For each test case, the only line contains one non-empty 01 string. The length of string is not exceed $ 200 $ .

输出描述

For each test case, output one string separated by a space.

示例1

输入

1
2
3
4
5
4
0
0001
0010
111011110

输出

1
2
3
4
0
0001
001 0
111 01111 0

题解

题意

定义完美串为循环移位字典序最小的字符串,如0110不是完美串,因为它可以循环移位得到0011 .

给一个仅由01构成的字符串,要把该字符串切分成最少的份数,使得每一个字符串都是完美串。

解法

$ n $ 不超过 $ 200 $ ,暴力做即可。

代码

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;
bool check(string s) {
int n = s.size();
for (int i = 1; i < n; i++)
for (int j = 0; j < n; j++)
if (s[j] < s[(i + j) % n])
break;
else if (s[j] > s[(i + j) % n])
return false;
return true;
}
int main() {
int T;
cin >> T;
while (T--) {
string a;
cin >> a;
int len = a.size();
for (int i = 0; i < len;)
for (int j = len - i; j > 0; j--)
if (check(a.substr(i, j))) {
cout << a.substr(i, j);
i += j;
if (i < len) cout << ' ';
break;
}
cout << endl;
}
return 0;
}

B - Irreducible Polynomial

题目描述

In mathematics, a polynomial is an expression consisting of variables (also called indeterminate) and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponents of variables. For example, $ x^2 + 4x + 7 $ .

A polynomial is said to be irreducible if it cannot be factored into two or more non-trivial polynomials with real coefficients.

For example, $ x^2+1 $ is irreducible, but $ x^2-2x+1 $ is not (since $ x^2-2x+1=(x-1)(x-1) $ .

Given a polynomial of degree $ n $ with integer coefficients: $ a_nx^n+a_{n-1}x^{n-1}+…+a_1x+a_0 $ , you need to check whether it is irreducible or not.

输入描述

The first line of the input gives the number of test cases, $ T\ (T \leq 100) $ . $ T $ test cases follow.

For each test case, the first line contains one integers $ n (0 \leq n \leq 20) $ . Next line contains $ n + 1 $ integer numbers $ a_n, a_{n-1}, …, a_1, a_0 $

  • $ -10^9 \leq a_i \leq 10^9 $
  • $ a_n \ne 0 $

输出描述

For each test case, output Yes if it is irreducible, otherwise No.

示例1

输入

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

输出

1
2
No
Yes

题解

题意

给定一个 $ n $ 次 $ n+1 $ 项式 $ (A_nX^n+A_{n-1}X^{n-1} \dots A_1X+A_0) $ 的全部系数 $ A $ 。

询问这个多项式是否为不可约多项式。

解法

首先有结论: $ n>3 $ 时,该式必然为可约多项式。

然后对于 $ n<3 $ 的情况特判即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main() {
int T, n, a, b, c;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
if (n == 2) {
scanf("%d%d%d", &a, &b, &c);
int d = b * b - 4 * a * c;
printf("%s\n", d < 0 ? "Yes" : "No");
} else {
for (int i = 0; i <= n; ++i) scanf("%d", &a);
printf("%s\n", n < 2 ? "Yes" : "No");
}
}
return 0;
}

C - Governing sand

题目描述

The Wow village is often hit by wind and sand,the sandstorm seriously hindered the economic development of the Wow village.

There is a forest in front of the Wowo village, this forest can prevent the invasion of wind and sand. But there is a rule that the number of tallest trees in the forest should be more than half of all trees, so that it can prevent the invasion of wind and sand. Cutting down a tree need to cost a certain amount of money. Different kinds of trees cost different amounts of money. Wow village is also poor.

There are n kinds of trees. The number of i-th kind of trees is $ P_i $ , the height of i-th kind of trees is $ H_i $ , the cost of cutting down one i-th kind of trees is $ C_i $ .

(Note: “cutting down a tree” means removing the tree from the forest, you can not cut the tree into another height.)

输入描述

The problem is multiple inputs (no more than 30 groups).

For each test case.

The first line contines one positive integers $ n (1 \leq n \leq 10^5) $ ,the kinds of trees.

Then followed $ n $ lines with each line three integers $ H_i (1 \leq H_i \leq 10^9) $ -the height of each tree, $ C_i (1 \leq C_i \leq 200) $ -the cost of cutting down each tree, and $ P_i(1 \leq P_i\leq 10^9) $ -the number of the tree.

输出描述

For each test case, you should output the minimum cost.

示例1

输入

1
2
3
4
5
6
2
5 1 1
1 10 1
2
5 1 2
3 2 3

输出

1
2
1
2

题解

题意

给定 $ n $ 种树的高度、移除的花费和数量,求最小花费使得剩下树中最高的树的数量占一半以上。

解法

枚举最大高度,每次将高度值大于该树的树全砍掉,通过预处理把时间复杂度降到 $ \mathcal{O}(n) $ 。如果数量还是太多那么选择花费最小的树删掉,注意到 $ c<=200 $ ,那么可以保存每种花费的树的个数,二分找出最小花费。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x7fffffffffffffff
#define N 100010
#define M 201
struct faner {
int h, c, p;
ll s, sp;
} a[N];
bool cmp(faner a, faner b) { return a.h == b.h ? a.c < b.c : a.h < b.h; }
int lowbit(int x) { return x & (-x); }
struct {
ll c[M];
ll Query(int m) {
ll sum = 0;
for (int i = m; i > 0; i -= lowbit(i)) sum += c[i];
return sum;
}
void Add(int m, ll x) {
for (int i = m; i < M; i += lowbit(i)) c[i] += x;
}
void Clear() { memset(c, 0, sizeof(c)); }
} Bit1, Bit2;
int main() {
int n;
while (~scanf("%d", &n)) {
Bit1.Clear();
Bit2.Clear();
for (int i = 1; i <= n; i++) scanf("%d%d%d", &a[i].h, &a[i].c, &a[i].p);
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++) {
a[i].s = a[i - 1].s + (ll)a[i].c * (ll)a[i].p;
a[i].sp = a[i].p + (a[i - 1].h == a[i].h ? a[i - 1].sp : 0);
}
ll num = 0, bef = 1, ans = INF;
for (int i = 1; i <= n; i++) {
if (num >= a[i].sp) {
int l = 0, r = 200, sign = 0;
while (l < r) {
int mid = (l + r) >> 1;
if (Bit1.Query(mid) >= num - (a[i].sp - 1))
r = mid, sign = r;
else
l = mid + 1, sign = l;
}
ll sum =
Bit2.Query(sign - 1) +
(ll)sign * (num - (a[i].sp - 1) - Bit1.Query(sign - 1)) +
a[n].s - a[i].s;
ans = min(ans, sum);
} else
ans = min(ans, a[n].s - a[i].s);
if (a[i + 1].h != a[i].h) {
for (int j = bef; j <= i; j++) {
Bit1.Add(a[j].c, (ll)a[j].p);
Bit2.Add(a[j].c, (ll)a[j].p * (ll)a[j].c);
num += (ll)a[j].p;
}
bef = i + 1;
}
}
printf("%lld\n", ans);
}
return 0;
}

D - Number

题目描述

I have a very simple problem for you. Given a positive integeter $ n (1 \leq n \leq 1000000) $ and a prime number $ p(2 \leq p \leq 1000000) $ , your job is to output a positive number which is divisible by $ P $ and has exactly $ n $ digits. Please output T_T if you can not find such number.

输入描述

The first line of the input file contains two integers $ n (1 \leq n \leq 1000000) $ and $ p (2 \leq p \leq 1000000) $ . $ p $ is a prime number.

输出描述

Output one number (without leading zeros) or T_T

示例1

输入

1
2 5

输出

1
10

示例2

输入

1
1 11

输出

1
T_T

示例3

输入

1
5 2

输出

1
10000

题解

题意

给定 $ n $ ,找到一个 $ n $ 位数的素数 $ p $ 的倍数,如果没有,则输出T_T

解法

如果 $ p $ 的位数超过所要求的位数,那么显然答案不存在

若是存在,我们只需要在 $ p $ 后面补 $ 0 $ 即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int n;
char p[8];
int main() {
scanf("%d%s", &n, p);
int x = strlen(p);
if (n < x)
printf("T_T\n");
else {
for (int i = 0; i < x; i++) putchar(p[i]);
while (n-- > x) putchar('0');
putchar('\n');
}
return 0;
}

E - Find the median

题目描述

Let median of some array be the number which would stand in the middle of this array if it was sorted beforehand. If the array has even length let median be smallest of of two middle elements. For example, median of the array $ [10,3,2,3,2] $ is $ 3 (i.e. [2,2,\underline{3},3,10]) $ . Median of the array $ [1,5,8,1] $ is $ 1 (i.e.[1,\underline{1},5,8]) $ .

At first, you’re given an empty sequence. There are $ N $ operations. The i-th operation contains two integers $ L_i $ and $ R_i $ . This means that adding $ R_i-L_i+1 $ integers $ L_i, L_i+1, … , R_i $ into the sequence. After each operation, you need to find the median of the sequence.

输入描述

The first line of the input contains an integer N (1≤N≤400000)N\ (1 \leq N \leq 400000)N (1≤N≤400000) as described above.

The next two lines each contains six integers in the following format, respectively:

$ - $ $ X_1\ X_2\ A_1\ B_1\ C_1\ M_1 $
$ - $ $ Y_1\ Y_2\ A_2\ B_2\ C_2\ M_2 $

These values are used to generate $ L_i, R_i $ as follows:

We define:
$ - $ $ X_i = (A_1 \times X_{i-1} + B_1 \times X_{i-2} + C_1)\ module\ M_1 $ , for $ i = 3\ to\ N $
$ - $ $ Y_i = (A_2 \times Y_{i-1} + B_2 \times Y_{i-2} + C_2)\ module\ M_2 $ , for $ i = 3\ to\ N $

We also define:
$ - $ $ L_i = min(X_i, Y_i) + 1 $ , for $ i = 1\ to\ N $ .
$ - $ $ R_i = max(X_i, Y_i) + 1 $ , for $ i = 1\ to\ N $ .

Limits:
$ 1 \leq N \leq 400000 $

$ 0 \leq A_1 < M_1 $

$ 0 \leq A_2 < M_2 $

$ 0 \leq B_1 < M_1 $

$ 0 \leq B_2 < M_2 $

$ 0 \leq C_1 < M_1 $

$ 0 \leq C_2 < M_2 $

$ 0 \leq X_1 < M_1 $

$ 0 \leq X_2 < M_1 $

$ 0 \leq Y_1 < M_2 $

$ 0 \leq Y_2 < M_2 $

$ 1 \leq M_1 \leq 10^9 $

$ 1 \leq M_2 \leq 10^9 $

输出描述

You should output $ n $ lines. Each line contains an integer means the median.

示例1

输入

1
2
3
5
3 1 4 1 5 9
2 7 1 8 2 9

输出

1
2
3
4
5
3
4
5
4
5

说明

$ L = [3, 2 ,4, 1, 7] $

$ R = [4, 8, 8, 3, 9] $

题解

题意

每次给数组插入区间 $ [L_i,R_i] $ 内的所有数,每操作一次查询中位数。

解法

首先考虑暴力做法,查询数组中位数需要知道当前数组的大小 $ sum $ ,那么中位数的位置就是 $ (sum−1)/2 $ 。

对于多次插入,多次查询的问题,需要数据结构维护答案。

考虑用线段树维护。线段树维护对于区间 $ [l,r] $ 内包含的数的个数,同时需要 $ tag $ 标记当前区间更新次数。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 400010
struct node {
int l, r;
ll num;
int tag;
} tree[maxn << 3];
int bb[maxn * 2], X[maxn], Y[maxn], L[maxn], R[maxn];
void build(int root, int l, int r) {
tree[root].l = l;
tree[root].r = r;
tree[root].num = 0;
tree[root].tag = 0;
if (l + 1 == r) return;
int mid = (l + r) >> 1;
build(root << 1, l, mid);
build(root << 1 | 1, mid, r);
}
void pushdown(int root) {
if (tree[root].tag == 0) return;
if (tree[root].l + 1 == tree[root].r) return;
tree[root << 1].tag += tree[root].tag;
tree[root << 1].num +=
1ll * tree[root].tag * (bb[tree[root << 1].r] - bb[tree[root << 1].l]);
tree[root << 1 | 1].tag += tree[root].tag;
tree[root << 1 | 1].num +=
1ll * tree[root].tag *
(bb[tree[root << 1 | 1].r] - bb[tree[root << 1 | 1].l]);
tree[root].tag = 0;
}
void pushup(int root) {
if (tree[root].l + 1 == tree[root].r) return;
tree[root].num = tree[root << 1].num + tree[root << 1 | 1].num;
}
void update(int root, int xx, int yy) {
if (xx == tree[root].l && tree[root].r == yy) {
tree[root].num += bb[yy] - bb[xx];
tree[root].tag++;
return;
}
pushdown(root);
int mid = (tree[root].l + tree[root].r) >> 1;
if (yy <= mid)
update(root << 1, xx, yy);
else if (xx >= mid)
update(root << 1 | 1, xx, yy);
else {
update(root << 1, xx, mid);
update(root << 1 | 1, mid, yy);
}
pushup(root);
}
ll query(int root, ll res) {
if (tree[root].l + 1 == tree[root].r) {
ll tmp = tree[root].num / (bb[tree[root].r] - bb[tree[root].l]);
return bb[tree[root].l] + (res - 1) / tmp;
}
pushdown(root);
if (res <= tree[root << 1].num)
return query(root << 1, res);
else
return query(root << 1 | 1, res - tree[root << 1].num);
}
int main() {
int n;
scanf("%d", &n);
int A1, A2, B1, B2, C1, C2, M1, M2;
scanf("%d%d%d%d%d%d", &X[1], &X[2], &A1, &B1, &C1, &M1);
scanf("%d%d%d%d%d%d", &Y[1], &Y[2], &A2, &B2, &C2, &M2);
for (int i = 3; i <= n; i++)
X[i] = (1ll * A1 * X[i - 1] + 1ll * B1 * X[i - 2] + C1) % M1;
for (int i = 3; i <= n; i++)
Y[i] = (1ll * A2 * Y[i - 1] + 1ll * B2 * Y[i - 2] + C2) % M2;
int tot = 0;
for (int i = 1; i <= n; i++) {
L[i] = min(X[i], Y[i]) + 1, R[i] = max(X[i], Y[i]) + 1;
R[i]++;
bb[++tot] = L[i];
bb[++tot] = R[i];
}
sort(bb + 1, bb + 1 + tot);
int totn = unique(bb + 1, bb + 1 + tot) - (bb + 1);
for (int i = 1; i <= n; i++) {
L[i] = lower_bound(bb + 1, bb + 1 + totn, L[i]) - bb;
R[i] = lower_bound(bb + 1, bb + 1 + totn, R[i]) - bb;
}
build(1, 1, totn);
ll sum = 0;
for (int i = 1; i <= n; i++) {
update(1, L[i], R[i]);
sum += (bb[R[i]] - bb[L[i]]);
ll res = (sum + 1) / 2;
ll ans = query(1, res);
printf("%lld\n", ans);
}
return 0;
}

F - Energy stones

题目描述

CNZ lives in the forest, and he has $ N $ energy stones, numbered from $ 1 $ to $ N $ .

CNZ need to eat energy generated by energy stones.

The $ i $ -th energy stone initially contains $ E_i $ units of energy and will increase $ L_i $ units of energy each second.

The maximum energy of $ i $ -th energy stone is $ C_i $ , the stone’s energy stops increasing once it reach $ C_i $ .

Each time he absorbs the energy of a continuous interval of stone. For example, if CNZ absorbs the energy of $ [S, T] $ stones, all energy stones numbered from $ S $ to $ T $ will become zero units of energy. CNZ can get the sum of energy in this range.

CNZ will eat $ M $ times. The i-th eating happens after $ t_i $ seconds, and eat interval is $ [S_i, T_i]. $

What’s the total amount of energy CNZ has eaten after $ M $ eating.

输入描述

The first line of the input gives the number of test cases, $ T (T \leq 20) $ . $ T $ test cases follow.

Each test case starts with a line containing the integer $ N\ (1 \leq N \leq 10^5) $ , the number of energy stones .

Then, there are $ N $ more lines, the i-th of which contains the three integers $ E_i $ , $ L_i $ and $ C_i $ as described above.

The next line contains one integer $ M $ .

Then, there are $ M $ more lines, the $ i $ -th of which contains the three integers $ t_i $ , $ S_i $ and $ T_i $ as described above.

Limits:

  • $ 1 \leq N \leq 10^5 $
  • $ 0 \leq E_i \leq C_i \leq 10^6 $
  • $ 0 \leq L_i \leq 10^6 $
  • $ 0 < M \leq 10^5 $
  • $ 0 < t_i \leq 2 \times 10^5 $
  • $ t_{i-1} < t_i $
  • $ 1 \leq S_i \leq T_i \leq N $

输出描述

For each test case, output one line containing Case #x: y, where $ x $ is the test case number (starting from $ 1 $ ) and $ y $ is the result.

示例1

输入

1
2
3
4
5
6
7
8
9
1
4
2 1 4
2 2 5
2 1 10
2 3 2
2
1 1 4
4 2 3

输出

1
Case #1: 20

说明

题解

题意

有 $ n $ 块石头,每块有初始能量 $ E_i $ ,每秒石头会增长能量 $ L_i $ ,石头的能量上限是 $ C_i $ 。

有 $ m $ 次时刻,每次会把 $ [s_i,t_i] $ 的石头的能量吸干,询问最后得到了多少能量。

解法

考虑每个石头对答案的贡献,使用权值树状数组和set维护。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100005
int E[N], L[N], C[N], d[N], mx;
vector<int> st[N], en[N];
set<int> se;
void init(int n) {
se.clear();
for (int i = 0; i <= n; i++) st[i].clear(), en[i].clear();
}
struct {
ll limit, b[200005];
void init(int mx) {
limit = mx + 1;
for (int i = 0; i <= limit; i++) b[i] = 0;
}
int lowbit(int x) { return x & -x; }
void add(int x, ll v) {
while (x <= limit) {
b[x] += v;
x += lowbit(x);
}
}
ll ask(ll x) {
ll res = 0;
if (x > limit) x = limit;
while (x) {
res += b[x];
x -= lowbit(x);
}
return res;
}
ll query(int l, int r) {
if (l > r) return 0;
return ask(r) - ask(l - 1);
}
} g1, g2;
ll ans = 0;
void solve(int x) {
if (se.size()) {
auto p = se.begin();
if (L[x] && *p >= (C[x] - E[x] + L[x] - 1) / L[x])
ans += C[x];
else
ans += E[x] + L[x] * *p;
ans += g2.ask(d[x] - 1) * L[x];
ans += g1.query(d[x], g1.limit) * C[x];
}
}
int main() {
int n, T, l, r;
scanf("%d", &T);
for (int tt = 1; tt <= T; tt++) {
printf("Case #%d: ", tt);
ans = mx = 0;
scanf("%d", &n);
init(n);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &E[i], &L[i], &C[i]);
d[i] = L[i] ? (C[i] + L[i] - 1) / L[i] : 1e6 + 1;
}
int m, t;
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &t, &l, &r);
st[l].push_back(t);
en[r + 1].push_back(t);
mx = max(mx, t);
}
g1.init(mx);
g2.init(mx);
for (int i = 1; i <= n; i++) {
for (auto x : st[i]) {
se.insert(x);
auto p = se.find(x);
auto pre = p, suf = p;
if (p != se.begin()) --pre;
if (p != se.end()) ++suf;
if (p != se.begin()) {
int dt = *p - *pre;
g1.add(dt, 1);
g2.add(dt, dt);
}
if (suf != se.end()) {
int dt = *suf - *p;
g1.add(dt, 1);
g2.add(dt, dt);
if (p != se.begin()) {
int dt = *suf - *pre;
g1.add(dt, -1);
g2.add(dt, -dt);
}
}
}
for (auto x : en[i]) {
auto p = se.find(x);
auto suf = p, pre = p;
if (p != se.begin()) --pre;
if (p != se.end()) ++suf;
if (p != se.begin()) {
int dt = *p - *pre;
g1.add(dt, -1);
g2.add(dt, -dt);
}
if (suf != se.end()) {
int dt = *suf - *p;
g1.add(dt, -1);
g2.add(dt, -dt);
if (p != se.begin()) {
dt = *suf - *pre;
g1.add(dt, 1);
g2.add(dt, dt);
}
}
se.erase(p);
}
solve(i);
}
printf("%lld\n", ans);
}
return 0;
}

G - Make Shan Happy

题目描述

Shan is a kind of fish and looks very beautiful in dress.

There is a tree whose root is 1. Every node i in this tree owns a weight $ W_i $ , satisfying that if $ x $ is an ancestor of $ y $ then $ W[x] \le W[y] $ .

Shan have several questions, each question can be represented as a pair(x,k), Shan wants to find the biggest node y such that $ y - k \le W[lca(x,y)] $ .

Shan is not happy today, can you help her to answer these questions?

输入描述

First line two integers: $ n(\le 10^5) $ and $ m(\le 10^5) $

Second line $ n $ integers, the $ i_{th} $ integer represents $ Wi $

Next $ n-1 $ lines, two integers each line u and v meaning that there an edge between $ u $ and $ v $ .

Next $ m $ lines, two integers each line $ x (1 \le x \le n) $ and $ k( -10^6 \le k \le 10^6) $ representing a question.

输出描述

$ m $ lines. One integer each line, $ i_{th} $ integer represents the answer to $ i_{th} $ question, and output $ 0 $ if there is no such node.

示例1

输入

1
2
3
4
5
6
7
8
9
10
11
5 5
1 3 4 3 5
1 2
2 3
2 4
1 5
1 1
2 3
3 -3
4 1
5 2

输出

1
2
3
4
5
2
4
0
4
5

H - Pair

题目描述

Given three integers $ A $ , $ B $ , $ C $ .Count the number of pairs < $ x\ , y $ > (with $ 1 \leq x \leq A $ and $ 1 \leq y \leq B $ )

such that at least one of the following is true:

  • ( $ x\ and\ y $ ) > $ C $
  • ( $ x\ xor\ y $ ) < $ C $

(“and”, “xor” are bit operators)

输入描述

The first line of the input gives the number of test cases, $ T\ (T \leq 100) $ . $ T $ test cases follow.

For each test case, the only line contains three integers $ A $ , $ B $ and $ C $ . $ 1 \leq A,B,C \leq 10^9 $

输出描述

For each test case, the only line contains an integer that is the number of pairs satisfying the condition given in the problem statement.

示例1

输入

1
2
3
4
3
3 4 2
4 5 2
7 8 5

输出

1
2
3
5
7
31

题解

题意

给定 $ A,B,C $ 问在 $ [1,A] $ 和 $ [1,B] $ 中有多少对 $ x,y $ 满足 $ x\ and \ y>C $ 或 $ x \ xor \ y < C $ .

解法

问题可以转化为求有多少对 $ (x,y) $ 满足$ x\ and \ y \leq C $ 并且 $ x \ xor \ y \geq C $ 。

用 $ dp[pos][la][lb][land][lxor] $ 表示到第 $ pos $ 位的个数, $ la $ 位表示是否是 $ A $ 的上限, $ lb $ 表示是否是 $ B $ 的上限, $ land $ 表示的上限是否是 $ C $ , $ lxor $ 表示异或的下限是否是 $ C $ ,因为该 $ dp $ 表示的值与输入的 $ A,B,C $ 有关,所以每次都要 $ memset $ 置-1。因为 $ dfs $ 存在 $ x $ 或 $ y $ 为 $ 0 $ 的情况,而 $ x,y $ 最小是 $ 1 $ ,所以要减掉 $ x $ 或 $ y $ 为 $ 0 $ 的情况。 $ x $ 为 $ 0 $ 的个数有 $ max(0,B-C+0) $ ,即 $ y>=C $ ;同理, $ y $ 为 $ 0 $ 有 $ max(0,A-C+0) $ 种。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[35][2][2][2][2], A, B, C, ans;
int T, a[35], b[35], c[35];
void init() {
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
ll aa = A, bb = B, cc = C;
int pos = 0;
while (aa) {
a[pos++] = aa % 2;
aa /= 2;
}
pos = 0;
while (bb) {
b[pos++] = bb % 2;
bb /= 2;
}
pos = 0;
while (cc) {
c[pos++] = cc % 2;
cc /= 2;
}
}
ll dfs(int pos, int la, int lb, int land, int lxor) {
if (pos < 0) return 1;
if (dp[pos][la][lb][land][lxor] != -1) return dp[pos][la][lb][land][lxor];
ll res = 0;
int up1 = 1, up2 = 1, up3 = 1, up4 = 0;
if (la) up1 = a[pos];
if (lb) up2 = b[pos];
if (land) up3 = c[pos];
if (lxor) up4 = c[pos];
for (int i = 0; i <= up1; ++i)
for (int j = 0; j <= up2; ++j) {
if ((i & j) > up3) continue;
if ((i ^ j) < up4) continue;
res +=
dfs(pos - 1, la && (i == a[pos]), lb && (j == b[pos]),
land && ((i & j) == c[pos]), lxor && ((i ^ j) == c[pos]));
}
return dp[pos][la][lb][land][lxor] = res;
}
int main() {
scanf("%d", &T);
while (T--) {
memset(dp, -1, sizeof(dp));
scanf("%lld%lld%lld", &A, &B, &C);
init();
ans = dfs(30, 1, 1, 1, 1);
ans = ans - max(A - C + 1, 0ll) - max(B - C + 1, 0ll);
printf("%lld\n", A * B - ans);
}
return 0;
}

I - Chessboard

题目描述

CSL likes playing tricks very much. The unlucky TL always becomes the target of CSL’s tricks.

Today CSL came to trick TL again. He saw that TL has a very very large checkerboard and many glass balls. So he have an idea. He said to TL:

“What a big chessboard you have… How about play a game with me ? I will give you $ N $ and $ M $ ,and you can choose an arbitrarily large square area on the chessboard (assuming you choose a $ k \times k $ square area) and place a number of glass balls on each of the squares (each square should place not less than $ M $ glass balls). Your placement needs to be satisfied:

If we choose $ k $ squares of different rows and columns, then no matter how we choose, the total number of glass balls in this $ k $ squares should always be the same, and should not greater then $ N $ .

You just need to tell me how many ways you have to satisfy this. If you can’t tell me, the chessboard and glass balls will all belong to me !

TL doesn’t want to give the chessboard and glass ball to CSL, but he knows that the clever CSL has already worked out the answer in his mind. Can you help him solve this problem?

输入描述

The first line of the input is a single integer $ T (T \leq 5) $ indicating the number of test cases.

Each of the following $ T $ lines contains $ 2 $ integers $ N $ and $ M $ (meaning as description)

$ T \leq 5 $ , $ 1 \leq n,m \leq 2000 $

输出描述

For each test case, output the answer in a single line. because the answer may be very big, so just print the result after mod $ 998244353 $

示例1

输入

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

输出

1
2
3
4
5
1
3
9
26
73

备注

题解

题意

给定 $ n,m $ 。求 $ k \times k $ 的矩阵, $ 1 \leq k \leq n $ ,矩阵内的每个元素都不小于 $ m $ ,且矩阵内不同行不同列的元素相加都为一个定值 $ T $ ,且 $ T<=n $ 。询问这样的矩阵有多少种。

解法

  • 设 $ Ai $ 为第 $ i $ 行全为 $ 1 $ ,其它位置全为 $ 0 $ 的方阵。
  • 设 $ Bj $ 为第 $ j $ 列全为 $ 1 $ ,其它位置全为 $ 0 $ 的方阵。
  • 一个 $ k $ 行 $ k $ 列,任取 $ k $ 个元素,每个元素不同行不同列的方阵,一定可以由 $ \{A1,A2,….,B1,B2…..\} $ 的生成的线性空间中。也就是 $ \sum_{i=1}^ka_iA_i+\sum_{j=1}^kb_jB_k $
  • 于是有 $ \sum_{i=1}^ka_i+\sum_{j=1}^kb_j \geq n $
  • 但很可惜,如上线性空间的基中只有 $ 2k−1 $ 个向量,因此表出方式不唯一。
  • 对于不同的表出方式,令 $ d=\min_{i=1}^ka_i $ 做变换 $ ai:=ai−d $ , $ bi:=bi+d $ ,于是我们识破了本质相同的矩阵的不同表出方式。
  • 对于一个确定的 $ k $ ,答案为 $ \sum_{i=1}^ka_i+\sum_{j=1}^kb_j \leq n $ (存在 $ a_i=0 $ )
  • 枚举 $ k $ ,用 $ \sum_{i=1}^ka_i+\sum_{j=1}^kb_j≤n $ ,( $ a_i,b_j \geq 0 $ ) 的解数,减去 $ \sum_{i=1}^ka_i+\sum_{j=1}^kb_j \leq n $ ,( $ b_j \geq 0,ai \geq 1 $ ) 的解数即可,复杂度 $ \mathcal{O}(n) $

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100010
#define mod 998244353
ll p[N], q[N];
ll powermod(ll a, ll b, ll c) {
ll ans = 1;
a = a % c;
while (b) {
if (b & 1) ans = ans * a % c;
b >>= 1;
a = a * a % c;
}
return ans % c;
}
void init() {
p[0] = q[0] = 1;
for (int i = 1; i < N; ++i) p[i] = (p[i - 1] * i) % mod;
q[N - 1] = powermod(p[N - 1], mod - 2, mod);
for (int i = N - 1; i > 0; --i) q[i - 1] = q[i] * i % mod;
}
ll C(ll n, ll m) {
if (n < m) return 0;
return p[n] * q[m] % mod * q[n - m] % mod;
}

int main() {
init();
int t;
scanf("%d", &t);
while (t--) {
int n, m;
scanf("%d%d", &n, &m);
ll ans = 0;
for (int i = 1; i <= n; ++i) {
int T = n - m * i;
if (T < 0) break;
for (int j = 0; j <= T; ++j) {
ans = (ans + C(j + 2 * i - 1, 2 * i - 1) + mod) % mod;
ans = (ans - C(j + i - 1, 2 * i - 1) + mod) % mod;
}
}
printf("%lld\n", ans);
}
return 0;
}

J - A+B problem

题目描述

Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. And all the leading zeros are omitted.

For example: the reversed number of $ 1234 $ is $ 4321 $ . The reversed number of $ 1000 $ is $ 1 $ .

We define reversed number of $ x $ as $ f(x) $ . Given you two positive integers $ A $ and $ B $ , you need to calculate the reversed sum: $ f(f(A)+f(B)) $ .

输入描述

The first line of the input gives the number of test cases, $ T\ (T \leq 300) $ . $ T $ test cases follow.

For each test case, the only line contains two positive integers: $ A $ and $ B $ . ( $ 1 \leq A, B \leq 2^{31}-1 $ )

输出描述

For each test case, output a single line indicates the reversed sum.

示例1

输入

1
2
3
4
3
12 1
101 9
991 1

输出

1
2
3
22
11
2

题解

题意

$ f(x) $ 被定义为反转数字 $ x $ ,并去除前导零之后的数,输入两个数 $ x,y $ ,询问 $ f(f(A)+f(B)) $ 。

解法

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll f(ll a) {
ll t = 0;
while (a) t = t * 10 + a % 10, a /= 10;
return t;
}
ll a, b;
int main() {
int t;
for (scanf("%d", &t); t--;) {
scanf("%lld%lld", &a, &b);
printf("%lld\n", f(f(a) + f(b)));
}
return 0;
}

K - Function

题目描述

CSL likes to study various functions. Recently, he became fascinated with a new function. He named it $ CSL $ function. Its expression is as follows:

Where p is a prime number. But CSL doesn’t like floating point numbers and even numbers, nevertheless, he likes square numbers very much, so he decided to add some restrictions to his $ CSL $ functions:

  1. if $ CSL(p,x) $ is not integer,then let $ CSL(p,x)=0 $
  2. if $ CSL(p,x) $ is integer,but $ p $ is $ 2 $ or $ p $ can’t be expressed as the sum of two squares(which means: $ \nexists a,b \in N^+,s.t. \ a^2+b^2=p $ ),then let $ CSL(p,x)=1 $

TL saw the function of $ CSL $ . He thought it was not interesting enough, so he also defined a $ tl $ function:

Where p is a prime number too. $ TL $ asked $ CSL $ proudly: I will give you an $ x $ , Could you calculate $ \sum_{d|x}\prod_{p}tl(p,d) $ (in which $ p $ passing through all the prime numbers)?

$ CSL $ thought about it and told $ TL $ the answer quickly. and he asked $ TL $ :so if I give you a $ n $ , Could you calculate $ \sum_{d=1}^{n}\prod_{p}tl(p,d) $ ?

$ TL $ can’t do this, so he turned up to you for help.

输入描述

The first line of the input is a single integer $ T (T \leq 5) $ indicating the number of test cases.

Each of the following $ T $ lines contains one integer $ n $ (meaning as description)

$ T \leq 5 $

$ n \leq 10^{9} $

输出描述

示例1

输入

1
2
3
4
5
4
1
2
3
5

输出

1
2
3
4
1
2
3
8