B
题目大意：给定一个正整数 $n$。若满足以下条件，非负整数对 $a,b$ 被称为“美丽对”： - $a + b = n$。- 数字 $a$ 是回文数。需要找到一个“美丽对”，或者报告不存在。
数据范围：$1 \le t \le 10^4$，$1 \leq n \leq 10^{18}$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
ll tem = n % 12;
vl tem2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 22, 11};
if (n < tem2[tem]) {
cout << -1 << endl;
return;
}
cout << tem2[tem] << ' ' << n - tem2[tem] << endl;
return;
}
|
C
题目大意：这是该问题的简单版本。不同版本之间的区别在于本版本中 $n$ 和测试用例数量的约束更小。只有在你解决所有版本的本题后才能进行 hack。有 $n$ 个无限高的连通容器，按环形排列。每个容器底面积为 $1\,\mathrm{cm}^2$，并且第 $i$ 个容器与第 $(i \bmod n) + 1$ 个容器之间，在高度为 $h_i$ $\mathrm{cm}$ 处有一个体积可忽略不计的连通管。对于每个容器 $i$，请找出在第 $i$ 个容器保持为空的前提下，能放入这些容器中的水的最大总体积（单位为 $\mathrm{cm}^3$）。形式化地，给定数组 $h_1, h_2, \ldots, h_n$。
数据范围：$1 \le t \le 1000$，$3 \le n \le 3000$，$1 \le h_i \le 10^9$，$\sum n \le 3000$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl res(n);
rep(i, 0, n - 1) {
vl tem;
rep(j, i, i + n - 1) tem.push_back(a[j % n]);
vl pre(n);
pre[0] = tem[0];
rep(j, 1, n - 1) pre[j] = max(pre[j - 1], tem[j]);
vl suf(n);
suf[n - 1] = tem[n - 1];
frep(j, n - 2, 0) suf[j] = max(suf[j + 1], tem[j]);
ll ans = 0;
rep(j, 1, n - 1) { ans += min(pre[j - 1], suf[j]); }
res[i] = ans;
}
rep(i, 0, n - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
D
题目大意：给定整数 $k$，存在一个长度为 $2^k+1$ 的二进制数序列，其中首尾已知、其余位置未知。接下来分 $k$ 轮填充：每轮在相邻已知下标之间取中点，并把该中点的值赋为两端点的异或。所有赋值同时进行，需要根据这一规则处理序列相关问题。
数据范围：$1 \le t \le 10^4,\quad 1 \le n \le 10^5,\quad 1 \le k \le 30$，$\sum n \le 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| using i128 = __int128_t;
void solve() {
ll n, k;
cin >> n >> k;
string s, t;
cin >> s >> t;
string tem;
rep(i, 0, n - 1) tem.push_back('0');
auto calc = [&](string s, string t) -> ll {
ll ans = 0;
rep(i, 0, n - 1) { ans += (s[i] != t[i]); }
return ans;
};
ll tems = calc(s, tem);
ll temt = calc(t, tem);
ll temm = calc(s, t);
if (k % 2 == 1)
cout << ((1LL << k) + 1) / 3 * (tems * (n - tems) + temt * (n - temt) + temm * (n - temm)) << endl;
else
cout << ((1LL << k) + 2) / 3 * (tems * (n - tems) + temt * (n - temt)) + ((1LL << k) - 1) / 3 * temm * (n - temm) << endl;
return;
}
|
E
题目大意：Vlad 想出了一个长度为 $n$ 的排列 $p$。之后，对每个 $i \in [1,n]$，他统计满足下述条件的区间 $(l,r)$ 的数量： $1 \le l \le r \le n$，且子数组 $p_l,p_{l+1},\dots,p_r$ 的最小值恰好等于 $p_i$，并把这个数量记作 $a_i$。现在他把数组 $a_1,a_2,\dots,a_n$ 交给 Misha，让他还原排列 $p$。但 Misha 很快发现，不一定能唯一还原出排列 $p$。于是他打算算出所有合法排列 $p$ 的数量，结果对 $10^9+7$ 取模。需要帮他完成计算。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 5 \times 10^5$，$1 \le a_i \le 10^{12}$，$\sum n \le 5 \times 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
54
55
56
57
58
59
| using i128 = __int128_t;
constexpr int MOD = 1e9 + 7;
constexpr int MX = 5e5 + 1;
ll F[MX]; // 预处理阶乘
ll INV_F[MX]; // 预处理逆元
ll mul(ll x, ll y) { return x * y % MOD; }
ll qpow(ll x, int n) {
ll res = 1;
for (; n; n >>= 1) {
if (n % 2) res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
auto init = [] {
F[0] = 1;
for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD; // 预处理阶乘
INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
for (int i = MX - 1; i; i--) {
INV_F[i - 1] = INV_F[i] * i % MOD;
} // 预处理逆元
return 0;
}();
// 计算C(n,m),即从n个数中取m个数
ll comb(int n, int m) { return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD; }
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
bool flag = true;
auto dfs = [&](this auto&& dfs, ll l, ll r) -> ll {
if (l > r) return 1;
if (!flag) return 0;
int idx = -1;
ll tem = 1;
rep(i, 0, (r - l) / 2) {
if (1LL * (i + 1) * (r - l + 1 - i) == a[l + i]) {
idx = l + i;
break;
}
if (1LL * (i + 1) * (r - l + 1 - i) == a[r - i]) {
idx = r - i;
break;
}
}
if (idx == -1) {
flag = false;
return 0;
}
tem = mul(tem, comb(r - l, idx - l));
tem = mul(tem, dfs(l, idx - 1));
tem = mul(tem, dfs(idx + 1, r));
return tem;
};
ll ans = dfs(0, n - 1);
cout << ans << endl;
return;
}
|
F
题目大意：本题为困难版本，两个版本的区别在于本版本对 $n$ 和测试用例数量的限制更高。只有完成本题所有版本才能提交 hack。有 $n$ 个无限高的连通容器围成一个圆环。每个容器底面积为 $1\ \text{cm}^2$，第 $i$ 个容器与第 $(i \bmod n) + 1$ 个容器之间存在一条体积可忽略的连通通道，通道高度为 $h_i$ 厘米。对于每个容器 $i$，求出在第 $i$ 个容器保持为空的条件下，所有容器中能装入的最大总水量（单位 $\text{cm}^3$）。
数据范围：$1 \le t \le 10^4$，$3 \le n \le 2 \cdot 10^5$，$1 \le h_i \le 10^9$，$\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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ll idx = -1;
ll maxx = *max_element(all(a));
rep(i, 0, n - 1) {
if (a[i] == maxx) {
idx = i;
break;
}
}
vl tem;
rep(i, idx + 1, idx + n - 1) tem.push_back(a[i % n]);
int m = sz(tem);
vector<int> r(m, m);
vector<int> l(m, -1);
stack<int> s;
for (int i = m - 1; i >= 0; i--) {
while (!s.empty() && tem[s.top()] <= tem[i]) s.pop();
if (!s.empty()) r[i] = s.top();
s.push(i);
} // 求右边第一个小于的下标
while (!s.empty()) s.pop();
for (int i = 0; i <= m - 1; i++) {
while (!s.empty() && tem[s.top()] <= tem[i]) s.pop();
if (!s.empty()) l[i] = s.top();
s.push(i);
} // 求左边第一个小于的下标
vl res(n);
vl tem2(n);
vl tem3(n);
rep(i, 0, m - 1) { tem2[i] = (l[i] == -1 ? tem[i] * (i + 1) : tem2[l[i]] + tem[i] * (i - l[i])); }
frep(i, m - 1, 0) { tem3[i] = (r[i] == m ? tem[i] * (m - i) : tem3[r[i]] + tem[i] * (r[i] - i)); }
rep(i, 0, n - 1) {
if (i > 0) res[(i + idx + 1) % n] += tem2[i - 1];
if (i < n - 1) res[(i + idx + 1) % n] += tem3[i];
}
rep(i, 0, n - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
G
题目大意：有一条由 $n+1$ 个格子组成的带，编号从 $1$ 到 $n+1$。一开始，第 $1$ 个格子上有一个权值为 $1$ 的棋子，第 $1 \sim n$ 个格子上分别写有数 $a_1, a_2, \ldots, a_n$。有两名玩家进行游戏，每次轮到玩家操作时，按以下顺序进行： 1. 设当前棋子在第 $i$ 个格子。2. 玩家可以将棋子的权值增加任意整数，范围是 $0$ 到 $a_i$ 之间（包含 $0$ 和 $a_i$）。3. 然后，玩家可以将棋子向前移动任意正整数步，但不能超过当前棋子的权值，且移动后不能超出这条带的末端。使棋子恰好落在第 $n+1$ 个格子的那一步的玩家获胜。两人都采取最优策略时，谁能获胜？
数据范围：$1 \le t \le 10^4$，$1 \le n \le 10^5$，$0 \le a_i \le 10^9$，$\sum n \le 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
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
set<array<ll, 3>> s;
vvl tem(n + 2);
set<ll> win;
rep(i, 0, n + 1) win.insert(i);
rep(i, 0, n) s.insert({1, i, i + 1});
rep(i, 1, n) {
if (n - i - 1 >= 0) tem[n - i - 1].push_back(i);
}
frep(i, n - 1, 0) {
for (auto& p : tem[i]) {
win.erase(p);
auto x = win.upper_bound(p);
auto xx = x;
xx--;
s.erase({p - *xx, *xx, p});
s.erase({*x - p, p, *x});
s.insert({*x - *xx, *xx, *x});
}
while (!s.empty() && (*prev(s.end()))[0] >= a[i] + 2) {
auto [len, l, r] = *prev(s.end());
rep(j, l + 1, r - a[i] - 1) {
if (i == 0 && j == 1) {
cout << 2 << endl;
return;
}
s.erase({r - j + 1, j - 1, r});
s.insert({1, j - 1, j});
s.insert({r - j, j, r});
win.insert(j);
if (i - j - 1 >= 0) tem[i - j - 1].push_back(j);
}
}
}
cout << 1 << endl;
return;
}
|
