ABC459 D
出处：ABC459 D
题目大意：给你一个字符串 $S$，问是否有办法重排 $S$ 使得 $S$ 的所有相邻两个字符均不同。如果有，请输出一种方案。如果有多种方案，你可以随便输出一组。$T$ 组数据。
数据范围：$1 \le T \le 300000$。
思路：
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
| void solve() {
string s;
cin >> s;
int n = sz(s);
vi cnt(26);
rep(i, 0, n - 1) cnt[s[i] - 'a']++;
int tem = *max_element(all(cnt));
if (tem > (n + 1) / 2) {
cout << "No" << endl;
return;
}
priority_queue<pii, vector<pii>, less<>> q;
rep(i, 0, 25) {
if (cnt[i]) q.emplace(cnt[i], i);
}
cout << "Yes" << endl;
string res = "";
while (sz(q) >= 2) {
auto [x1, y1] = q.top();
q.pop();
auto [x2, y2] = q.top();
q.pop();
res.push_back((char)('a' + y1));
res.push_back((char)('a' + y2));
if (x1 > 1) q.emplace(x1 - 1, y1);
if (x2 > 1) q.emplace(x2 - 1, y2);
}
if (!q.empty()) res.push_back((char)(q.top().second + 'a'));
cout << res << endl;
return;
}
|
ABC459 E
出处：ABC459 E
题目大意：有一个 $N$ 个结点的有根树，节点编号为 $1 \sim N$，$1$ 是根，$i$ 的父亲是 $P_i$。现在点 $i$ 上有 $C_i$ 颗糖。所有糖两两不同。现在，有 $N$ 只松鼠，第 $i$ 只松鼠必须取 $i$ 的子树中的 $D_i$ 颗糖并且吃下去。求不同的方案的总数，$\bmod \ 998244353$。如果在两个方案中，有一只松鼠吃的糖的集合不同，那么这两个方案就是不同的。如果无方案，输出 $0$。
数据范围：$1 \le N \le 2 \times 10^5$，$1 \le P_i \le N$，$1 \le C_i \le 10^9$，$\sum D_i \le 10^6$。
思路：
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
| constexpr int MOD = 998244353;
constexpr int MX = 1e6 + 1;
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(ll n, ll m) {
if (n < m) return 0;
ll res = 1;
rep(i, 0, m - 1) { res = res * ((n - i) % MOD) % MOD; }
res = res * INV_F[m] % MOD;
return res;
}
void solve() {
int n;
cin >> n;
vi pa(n);
vvi ma(n);
rep(i, 1, n - 1) {
cin >> pa[i];
pa[i]--;
ma[pa[i]].push_back(i);
ma[i].push_back(pa[i]);
}
vl c(n);
rep(i, 0, n - 1) cin >> c[i];
vl d(n);
rep(i, 0, n - 1) cin >> d[i];
ll ans = 1;
auto dfs = [&](this auto&& dfs, int x, int pa) -> ll {
ll tem = c[x];
for (int& p : ma[x]) {
if (p == pa) continue;
tem += dfs(p, x);
}
ans = ans * comb(tem, d[x]) % MOD;
return tem - d[x];
};
dfs(0, -1);
cout << ans << endl;
return;
}
|
ABC459 F
出处：ABC459 F
题目大意：给定一个长度为 $N$ 的非负整数序列 $A = (A_1, A_2, \ldots, A_N)$。你可以对 $A$ 执行以下操作零次或多次： - 选择一个满足 $1 \le i \le N-1$ 的整数 $i$，将 $A_i$ 减少 $1$，同时将 $A_{i+1}$ 增加 $1$。需要求出，至少需要多少次操作，才能使 $A$ 变成严格递增的序列。
数据范围：$1 \le T \le 3 \times 10^5$，$1 \le N \le 2 \times 10^5$，$0 \le A_i \le 10^9$，$\sum N \le 6 \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
| void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
stack<pll> s;
rep(i, 0, n - 1) {
s.emplace(1, a[i] - i + n);
while (sz(s) >= 2) {
auto [x1, y1] = s.top();
s.pop();
auto [x2, y2] = s.top();
s.pop();
ll tem = (y2 + x2 - 1) / x2;
ll tem2 = y1 / x1;
if (tem > tem2) {
s.emplace(x1 + x2, y1 + y2);
} else {
s.emplace(x2, y2);
s.emplace(x1, y1);
break;
}
}
}
ll ans = 0;
vector<pll> tem;
while (!s.empty()) {
tem.push_back(s.top());
s.pop();
}
ranges::reverse(tem);
ll pre1 = 0;
ll pre2 = 0;
int idx = 0;
for (auto& [x, y] : tem) {
ll tem2 = y / x;
ll re = y % x;
rep(i, 0, x - 1) {
ll tem3 = tem2 + (i >= x - re);
pre1 += a[idx];
pre2 += tem3 - n + idx;
if (idx != n - 1) ans += pre1 - pre2;
idx++;
}
}
cout << ans << endl;
return;
}
|
