这场也没打，感觉D偏难了，其他的题都比较trivial~
C
题目大意：给定一个只包含小写英文字母的字符串，现在可以选择一对整数 $1 \leq i < j \leq n$ ，它们相等且都不是*，且它们之间的字符都是*，然后把它们都变为*。
如果无法变了，游戏结束，此时如果每个字符都是*，则输出YES,否则输出NO。
数据范围： $1 \leq n \leq 5000,1 \leq sum(n) \leq 5000$ 。
思路：看到这种类似邻项消除的题目，肯定要想着用栈做，然后最后只需要检查栈是否为空即可，不过这种题目容易忘记。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lii = lambda: list(mii())
def solve():
n = ii()
s = input()
st = []
for i in range(n):
st.append(s[i])
if len(st) >= 2 and st[-1] == st[-2]:
st.pop()
st.pop()
print("NO" if st else "YES")
return
for _ in range(ii()):
solve()
|
D
题目大意：给定 $n$ 的排列，现在数组中间有两个传送门，可以把左边传送门左边的数传到右边传送门的右边，或者把左边传送门右边的数传到右边传送门的左边，问最终能得到的最小字典序序列是什么。
数据范围： $1 \leq n \leq 2 \cdot 10^5, 0 \leq x < y \leq 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
|
void solve() {
int n, x, y;
cin >> n >> x >> y;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
int mixx = INT_MAX;
rep(i, x, y - 1) mixx = min(mixx, a[i]);
int tem = 0;
rep(i, x, y - 1) {
if (a[i] == mixx) tem = i - x;
}
auto tem2 = a;
int l = y - x;
rep(i, x, y - 1) { a[x + (i - x - tem + l) % l] = tem2[i]; }
bool flag = false;
rep(i, 0, x - 1) {
if (a[i] > a[x] && flag == false) {
flag = true;
rep(j, x, y - 1) cout << a[j] << ' ';
}
cout << a[i] << ' ';
}
rep(i, y, n - 1) {
if (a[i] > a[x] && flag == false) {
flag = true;
rep(j, x, y - 1) cout << a[j] << ' ';
}
cout << a[i] << ' ';
}
if (!flag) {
rep(i, x, y - 1) cout << a[i] << ' ';
}
cout << endl;
return;
}
|
E
题目大意：给定一个 $n$ 个元素的数组 $a$ ，Alice和Bob在上面博弈。
Alice先开始，轮到每个玩家的时候，如果 $a$ 是非递减的，那么游戏结束，否则可以将某个 $x$ 拆成 $y,z,yz=x$ ，同时 $y$ 和 $z$ 需要位于 $x$ 的原来位置，但顺序可以自由分配，如果无法拆则游戏结束。
游戏结束的时候，如果 $a$ 是非递减的，那么Bob获胜，反之Alice获胜，现在需要你给出双方都以最优最优策略进行游戏的结果。
数据范围： $1 \leq n \leq 10^5,1 \leq a_i \leq 10^6$ 。
思路：首先考虑 Alice 只需要每次将一个数的最小素因子丢在后面，那么她就赢了。
因此，只需要计算一个数是否只是某个素因子的幂次，然后后续再比较即可。
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
|
constexpr int MX = 1e6 + 1;
int lpf[MX]; // 存储每个数的最小素因子，复杂度O(NloglogN)
auto init = [] {
for (int i = 2; i < MX; i++) {
if (lpf[i] == 0) {
for (int j = i; j < MX; j += i) {
if (lpf[j] == 0) lpf[j] = i;
}
}
}
return 0;
}();
// 质因数分解，返回值为pair<素因子，素因子次幂>，复杂度O(logN)
vector<pair<int, int>> cnt(int x) {
vector<pair<int, int>> res;
while (x > 1) {
int p = lpf[x];
int e = 1;
for (x /= p; x % p == 0; x /= p) {
e++;
}
res.emplace_back(p, e);
}
return res;
}
void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
bool flag = true;
rep(i, 1, n - 1) {
if (a[i] < a[i - 1]) {
flag = false;
break;
}
}
if (flag) {
cout << "Bob" << endl;
return;
}
rep(i, 0, n - 1) {
if (a[i] == 1) continue;
auto tem = cnt(a[i]);
if (sz(tem) >= 2) {
cout << "Alice" << endl;
return;
}
a[i] = tem[0].first;
}
flag = true;
rep(i, 1, n - 1) {
if (a[i] < a[i - 1]) {
flag = false;
break;
}
}
if (flag)
cout << "Bob" << endl;
else
cout << "Alice" << endl;
return;
}
|
F
题目大意：现在有 $n$ 个粒子，每个粒子的能量为 $x$ ，压力为 $y$ ，这表示它最多与 $y$ 个粒子一起共存。
现在有一个商店，这个商店出售 $m$ 个粒子，每个粒子的能量和压力都给出，现在要求出对于每个商店的粒子，将它加入原来粒子群后，取出某些粒子（买来的粒子不一定要取出）所能获得的最大能量值。
数据范围： $1 \leq n,m \leq 2 \cdot 10^5, 1 \leq x \leq 10^9, 0 \leq y \leq n, 1 \leq sum(n+m) \leq 2 \cdot 10^5$ 。
思路：对于这种题有个套路，就是要先计算出总体的粒子的最大数，然后再考虑选入这个粒子后的最大数。
首先，很容易想到枚举集合中最小压力数，因此考虑倒序遍历。
然后，考虑选入当前商店粒子，设它的压力值为 $y$ ，则需要求出压力值大于等于 $y$ ，且集合数小于等于 $y$ 的合法集合最大值。
随后，只需要使用堆倒序遍历确定集合大小，并取前缀最大值使得可以进行 $O(1)$ 查询。
比较trivial，但是ds对我来说比较难想，就卡了一下后面取看题解了。
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
|
void solve() {
int n, m;
cin >> n >> m;
vector<pii> ma(n);
vector<pii> ma2(m);
rep(i, 0, n - 1) cin >> ma[i].first >> ma[i].second;
rep(i, 0, m - 1) cin >> ma2[i].first >> ma2[i].second;
vl suf(n + 2);
priority_queue<ll, vector<ll>, greater<>> q;
map<int, vector<int>> ma3;
rep(i, 0, n - 1) ma3[ma[i].second].push_back(ma[i].first);
ll tem = 0;
ll ans = 0;
frep(i, n, 0) {
if (ma3.count(i)) {
for (auto& p : ma3[i]) {
q.push(p);
tem += 1LL * p;
}
}
while (sz(q) > i + 1) {
auto node = q.top();
q.pop();
tem -= node;
}
suf[i + 1] = tem;
if (sz(q) == i + 1) suf[i + 1] -= q.top();
ans = max(ans, tem);
}
rep(i, 1, n + 1) suf[i] = max(suf[i - 1], suf[i]);
rep(i, 0, m - 1) { cout << max(ans, 1LL * ma2[i].first + suf[ma2[i].second + 1]) << ' '; }
cout << endl;
return;
}
|
G
题目大意：现在给定一个 $x$ 和 $n$ 个计算操作，计算操作分为加减乘除四种，问按照任意次序执行这些操作后，得到的数的期望是多少，并模 $10^9+7$ 。
数据范围： $1 \leq n \leq 3000, 1 \leq x \leq 10^9, 1 \leq sum(n^2) \leq 3000^2$ 。
思路：首先考虑把减法和除法分别变成加法和乘逆元，这是显然的。
随后，注意到一个加法的贡献只跟后面它乘的数有关系，考虑现在 $m$ 个乘数的排列，加法的数就是插空法。
现在，考虑插入一个加数，它的背后有 $x$ 个乘数的概率，计算方案数显然是 $\frac{x!(m-x)!}{(m+1)!}$ 。
由于对每个加数，它们的位置都可以互换，因此只需要把加数的总和丢进去。
接着，还需要计算在 $m$ 个乘数中取 $x$ 个乘数乘起来的期望，这个可以用子序列DP做出来。
最后，不要忘了 $x$ 也是有贡献的。
其实很trivial，感觉比D简单多了~
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
|
constexpr int MOD = 1e9 + 7;
constexpr int MX = 3001;
ll F[MX]; // 预处理阶乘
ll INV_F[MX]; // 预处理逆元
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() {
int n;
ll x;
cin >> n >> x;
map<char, vl> ma;
string s;
ll tot = 0;
rep(i, 0, n - 1) {
cin >> s;
if (s[0] == '/') {
s[0] = 'x';
ma[s[0]].push_back(qpow(stoll(s.substr(1)), MOD - 2));
} else if (s[0] == '-') {
s[0] = '+';
ma[s[0]].push_back(-stoll(s.substr(1)));
} else
ma[s[0]].push_back(stoll(s.substr(1)));
}
ll ans = 0;
int m = sz(ma['x']);
vvl dp(m + 1, vl(m + 1));
dp[0][0] = 1;
rep(i, 1, m) {
dp[i] = dp[i - 1];
rep(j, 1, m) {
dp[i][j] += dp[i - 1][j - 1] * ma['x'][i - 1] % MOD;
dp[i][j] %= MOD;
}
}
rep(i, 0, sz(ma['+']) - 1) { tot = (tot + ma['+'][i] + MOD) % MOD; }
vl pre(m + 1);
pre[0] = 1;
rep(i, 1, m) { pre[i] = (pre[i - 1] + dp[m][i]) % MOD; }
ll tem = x * dp[m][m] % MOD;
rep(i, 0, m) {
ans += tot * F[m - i] % MOD * F[i] % MOD * INV_F[m + 1] % MOD * dp[m][i] % MOD;
ans %= MOD;
}
ans = (ans + tem) % MOD;
cout << ans << endl;
return;
}
|
