D
题目大意：你面前有两个鼓：一个左鼓和一个右鼓。敲击左鼓可以记录为 “L”，敲击右鼓可以记录为 “R”。这个世界的奇怪力量变幻莫测：有时一次敲击会发出一声响，有时会发出两声响。因此，敲击左鼓可能会发出 “L” 或 “LL”，敲击右鼓可能会发出 “R” 或 “RR”。敲击的序列记录在字符串 $p$ 中，而实际听到的声音记录在字符串 $s$ 中。给定 $p$ 和 $s$，判断字符串 $s$ 是否可能是由 $p$ 的敲击产生的结果。
数据范围：$1 \leq t \leq 10^4$，$1 \le |p| \le 2 \cdot 10^5$，$1 \le |p| \le |s| \le 2 \cdot 10^5$，$\sum |s| \le 2 \cdot 10^5$。
思路：
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
| void solve() {
string s;
cin >> s;
int n = sz(s);
string t;
cin >> t;
int m = sz(t);
vi cnt;
vi cnt2;
int tem = 0;
rep(i, 0, n - 1) {
if (i > 0 && s[i] != s[i - 1]) {
cnt.push_back(tem);
tem = 1;
} else
tem++;
}
if (tem) {
cnt.push_back(tem);
tem = 0;
}
rep(i, 0, m - 1) {
if (i > 0 && t[i] != t[i - 1]) {
cnt2.push_back(tem);
tem = 1;
} else
tem++;
}
if (tem) {
cnt2.push_back(tem);
tem = 0;
}
if (sz(cnt) != sz(cnt2)) {
cout << "NO" << endl;
return;
}
int ans = 0;
int st = 0, st2 = 0;
rep(i, 0, sz(cnt) - 1) {
if (s[st] != t[st2]) {
cout << "NO" << endl;
return;
}
int x = cnt[i], y = cnt2[i];
if (y > 2 * x || y < x) {
cout << "NO" << endl;
return;
}
st += x, st2 += y;
}
cout << "YES" << endl;
return;
}
|
E
题目大意：Boneca Ambalabu 给你一个包含 $n$ 个整数的序列 $a_1,a_2,\ldots,a_n$。在所有 $1 \leq k \leq n$ 中，输出 $(a_k \oplus a_1) + (a_k \oplus a_2) + \ldots + (a_k \oplus a_n)$ 的最大值。
数据范围：$1 \leq t \leq 10^4$，$1 \leq n \leq 2 \cdot 10^5$，$0 \leq a_i < 2^{30}$，$\sum n \le 2 \cdot 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl cnt(32);
rep(i, 0, n - 1) {
frep(j, 31, 0) { cnt[j] += ((a[i] >> j) & 1); }
}
ll ans = 0;
rep(i, 0, n - 1) {
ll tem = 0;
rep(j, 0, 31) {
if (a[i] >> j & 1)
tem += (1LL << j) * (n - cnt[j]);
else
tem += (1LL << j) * (cnt[j]);
}
ans = max(ans, tem);
}
cout << ans << endl;
return;
}
|
F
题目大意：Trulicina 给你三个整数 $n$、$m$ 和 $k$。题目保证 $k \geq 2$ 且 $n \cdot m \equiv 0 \pmod{k}$。请输出一个 $n \times m$ 的整数网格，满足以下所有条件： - 网格中的每个整数都在 $1$ 到 $k$ 之间（包含 $1$ 和 $k$）。
数据范围：$1 \leq t \leq 10^4$，$2 \leq n \cdot m \leq 2 \cdot 10^5$，$2 \leq k \leq n \cdot m$，$\sum n \cdot m \le 2 \cdot 10^5$。
思路：
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
| constexpr int MX = 2e5 + 5;
vector<int> divisors[MX];
auto init = [] {
for (int i = 1; i < MX; i++) {
for (int j = i; j < MX; j += i) {
divisors[j].push_back(i);
}
}
return 0;
}();
void solve() {
ll n, m, k;
cin >> n >> m >> k;
vvi ma(n, vi(m));
if (m % k == 0) {
rep(i, 0, n - 1) { rep(j, 0, m - 1) ma[i][j] = (j % k + i) % k + 1; }
} else if (n % k == 0) {
rep(i, 0, m - 1) {
rep(j, 0, n - 1) { ma[j][i] = (j % k + i) % k + 1; }
}
} else {
int idx = -1, idx2 = -1;
for (int& p : divisors[k]) {
if (n % p == 0 && m % (k / p) == 0) {
idx = p, idx2 = k / p;
}
}
rep(i, 0, n - 1) {
rep(j, 0, m - 1) { ma[i][j] = (i % idx) * idx2 + (j % idx2) + 1; }
}
}
rep(i, 0, n - 1) {
rep(j, 0, m - 1) cout << ma[i][j] << ' ';
cout << endl;
}
return;
}
|
G
题目大意：Chimpanzini Bananini 正站在一场重大战斗的边缘——这场战斗注定会带来终结。对于任意长度为 $m$ 的数组 $b$，我们定义该数组的"炫酷值"为 $\sum_{i=1}^m b_i \cdot i = b_1 \cdot 1 + b_2 \cdot 2 + b_3 \cdot 3 + \ldots + b_m \cdot m$。Chimpanzini Bananini 给你一个空数组。你可以对它进行三种类型的操作： 1. 对数组进行循环移位。即数组 $[a_1, a_2, \ldots, a_n]$ 变为 $[a_n, a_1, a_2, \ldots, a_{n-1}]$。2. 反转整个数组。
数据范围：$1 \leq t \leq 10^4$，$1 \leq q \leq 2 \cdot 10^5$，$1 \leq s \leq 3$，$1 \leq k \leq 10^6$，$\sum q \le 2 \cdot 10^5$。
思路：
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
| void solve() {
ll q, op, x;
cin >> q;
ll tot = 0;
ll len = 0;
ll res = 0;
deque<ll> d;
bool flag = false;
rep(i, 0, q - 1) {
cin >> op;
if (op == 1) {
ll tem;
if (!flag) {
tem = d.back();
d.pop_back();
d.push_front(tem);
} else {
tem = d.front();
d.pop_front();
d.push_back(tem);
}
res = res + tot - len * tem;
cout << res << endl;
} else if (op == 2) {
res = tot * (len + 1) - res;
flag = (flag ? false : true);
cout << res << endl;
} else {
cin >> x;
len++;
tot += x;
res += x * len;
if (!flag)
d.push_back(x);
else
d.push_front(x);
cout << res << endl;
}
}
return;
}
|
H
题目大意：Saturnita 的情绪取决于一个长度为 $n$ 的数组 $a$（只有他知道其含义）以及一个函数 $f(k, a, l, r)$（只有他知道如何计算）。以下是该函数的伪代码实现： function f(k, a, l, r): ans := 0 for i from l to r (inclusive): while k is divisible by a[i]: k := k/a[i] ans := ans + k return ans 给定 $q$ 个查询，每个查询包含整数 $k$、$l$ 和 $r$。对于每个查询，请输出 $f(k,a,l,r)$ 的值。
数据范围：$1 \leq t \leq 10^4$，$1 \leq n \leq 10^5$，$1 \leq q \leq 5 \cdot 10^4$，$2 \leq a_i \leq 10^5$，$1 \leq k \leq 10^5$，$1 \leq l \leq r \leq n$，$\sum n \le 10^5$，$\sum q \le 5 \cdot 10^4$。
思路：
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
| constexpr int MX = 1e5 + 5;
vector<int> divisors[MX];
auto init = [] {
for (int i = 1; i < MX; i++) {
for (int j = i; j < MX; j += i) {
divisors[j].push_back(i);
}
}
return 0;
}();
void solve() {
ll n, q, l, r, k;
cin >> n >> q;
vl a(n);
rep(i, 0, n - 1) { cin >> a[i]; }
ll maxx = *max_element(all(a));
map<ll, vl> tem;
rep(i, 0, n - 1) tem[a[i]].push_back(i);
rep(i, 0, q - 1) {
cin >> k >> l >> r;
l--, r--;
int tem2 = l;
ll ans = 0;
vector<pll> tem4;
for (auto& p : divisors[k]) {
if (p > maxx) break;
if (tem[p].empty()) continue;
int tem3 = ranges::lower_bound(tem[p], tem2) - tem[p].begin();
if (tem3 == sz(tem[p])) continue;
if (tem[p][tem3] > r) continue;
tem4.emplace_back(tem[p][tem3], p);
}
ranges::sort(tem4);
for (auto& [x, y] : tem4) {
if (x < tem2) continue;
if (k % y != 0) continue;
ans += k * (x - tem2);
while (k % y == 0) k /= y;
ans += k;
tem2 = x + 1;
if (k == 1) break;
}
if (tem2 <= r) ans += k * (r - tem2 + 1);
cout << ans << endl;
}
return;
}
|
