这场是不是有点太简单~依旧上大分。
C
题目大意：Alice,Bob和Carol到泉水边取水。Alice每隔 $a$ 天去一次，Bob每隔 $b$ 天去一次，Carol每隔 $c$ 天去一次。
每天，去的人会平分 $6$ 升水，问他们在 $m$ 天内各收集了多少水？
数据范围： $1 \leq a,b,c \leq 10^6, 1 \leq m \leq 10^{17}$
思路：非常典的容斥。
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
|
void solve() {
ll a, b, c;
ll m;
cin >> a >> b >> c >> m;
auto check = [&](ll x, ll y) {
ll g = __gcd(x, y);
if (x / g > (m + 1) / y) return m + 1;
return (x / g) * y;
};
ll tem = check(a, b);
ll tot = check(tem, c);
ll re = m / tot;
ll tem2 = check(a, c);
ll tem3 = check(b, c);
ll re1 = m / tem - re;
ll re2 = m / tem2 - re;
ll re3 = m / tem3 - re;
ll res1 = m / a - (re1 + re2) - re;
ll res2 = m / b - (re1 + re3) - re;
ll res3 = m / c - (re2 + re3) - re;
ll resa = 1LL * 6 * res1 + 1LL * 3 * (re1 + re2) + 1LL * 2 * re;
ll resb = 1LL * 6 * res2 + 1LL * 3 * (re1 + re3) + 1LL * 2 * re;
ll resc = 1LL * 6 * res3 + 1LL * 3 * (re2 + re3) + 1LL * 2 * re;
cout << resa << ' ' << resb << ' ' << resc << endl;
return;
}
|
D
题目大意：给定一个 $n$ 个点和 $m$ 条边的无向图，顶点的编号为 $1$ 到 $n$ ，这张图没有自环和重边。
现在需要为每条边选择一个方向，确定边的方向后，我们称一条形如 $v_1 \rightarrow v_2 \leftarrow v_3 \rightarrow v_4 \ldots$ 的路径为交替路径。
如果原始图中以顶点 $v$ 为起点的所有路径（不一定是简单路径）在生成的有向图中都是交替出现的，那么称顶点 $v$ 为美丽顶点，现在请求出美丽顶点的最大数目。
数据范围： $1 \leq n \leq 2 \cdot 10^5, 0 \leq m \leq 2 \cdot 10^5$
思路：首先非常显然地，看到类似交替路径的字眼，就会想到二分图，然后由于这里可以不是简单路径，因此不难验证这边不存在奇环，也确实是二分图。
然后考虑染色（毕竟这个分段能出的只有染色），对于每个联通分量，首先染色判断它是不是二分图，如果是，则贡献为两种染色数量的最大值，如果不是则贡献为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
|
void solve() {
int n, m, x, y;
cin >> n >> m;
vvi ma(n);
rep(i, 0, m - 1) {
cin >> x >> y;
ma[x - 1].push_back(y - 1);
ma[y - 1].push_back(x - 1);
}
vector<int> vis(n);
int ans = 0, ans2 = 0;
bool flag = true;
auto dfs = [&](this auto&& dfs, int x, int c) -> void {
vis[x] = c;
if (c == 1)
ans++;
else
ans2++;
for (int& p : ma[x]) {
if (!vis[p])
dfs(p, 3 - c);
else if (vis[p] == c) {
flag = false;
}
}
return;
};
int res = 0;
rep(i, 0, n - 1) {
if (vis[i]) continue;
ans = 0, ans2 = 0;
flag = true;
dfs(i, 1);
if (flag) res += max(ans, ans2);
}
cout << res << endl;
return;
}
|
E
题目大意：对于正整数 $x$ ，字符串 $S(x)$ 是这么形成的：
首先把当前 $x$ 连接到字符串末尾。
随后，如果 $x \leq 9$ ，则退出，否则 $x=digit(x)$ ，这里 $digit(x)$ 是 $x$ 在十进制下数位和。
给定一个由数字组成的字符串 $S$ ，请重新排列该字符串中的字符，使其组成某个数字 $x$ 的 $S(x)$ ，题目保证有解。
数据范围： $1 \leq |S| \leq 10^5,1 \leq sum(|S|) \leq 10^5$
思路：一看下去其实有点无从下手的题，其实大多数时候都是在找性质。
首先观察到， $x_1+x_2+\ldots +x_k+x_k=digit(S)$ ，其中每个 $x_i$ 是第 $i$ 个数的数位和。
那么，这里可以考虑到 $digit(S) \leq 9 \cdot 10^5$ ，因此可以暴力枚举 $x_1$ ，有了 $x_1$ 之后，其实就得到了第二个数，然后就可以算出后面所有的数了，只需考虑所有的和是否等于 $digit(S)$ ，以及给出的所有数字是否刚好用完即可。
不过有点史，还是需要好好写一下。
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
|
void solve() {
string s;
cin >> s;
if (sz(s) == 1) {
cout << s << endl;
return;
}
vi cnt(10);
rep(i, 0, sz(s) - 1) { cnt[s[i] - '0']++; }
int ans = 0;
rep(i, 0, 9) ans += cnt[i] * i;
int maxx = 0;
rep(i, 1, ans) {
int sum = i;
int tem = i;
vi temp;
temp.push_back(i);
while (tem > 0) {
if (0 <= tem && tem <= 9) {
sum += tem;
temp.push_back(i);
break;
}
int tem2 = 0;
int tem3 = tem;
while (tem3 > 0) {
tem2 += tem3 % 10;
tem3 /= 10;
}
sum += tem2;
temp.push_back(tem2);
tem = tem2;
}
if (1 <= i && i <= 9) {
if (sum != ans || !cnt[i]) continue;
} else {
if (sum != ans) continue;
}
int sum2 = i;
vi cnt2(10);
while (sum2 >= 10) {
int tem2 = sum2;
int tem3 = 0;
while (tem2 > 0) {
tem3 += tem2 % 10;
cnt2[tem2 % 10]++;
tem2 /= 10;
}
sum2 = tem3;
}
cnt2[sum2]++;
int sum3 = 0;
bool flag = true;
frep(i, 9, 0) {
if (cnt2[i] > cnt[i]) {
flag = false;
break;
}
sum3 += i * (cnt[i] - cnt2[i]);
}
if (sum3 != i || !flag) continue;
maxx = i;
break;
}
string res = "";
int maxx2 = maxx;
vi cnt2(10);
while (maxx2 >= 10) {
int tem2 = maxx2;
int tem3 = 0;
while (tem2 > 0) {
tem3 += tem2 % 10;
cnt2[tem2 % 10]++;
tem2 /= 10;
}
maxx2 = tem3;
}
cnt2[maxx2]++;
frep(i, 9, 0) { rep(j, 0, cnt[i] - cnt2[i] - 1) res.push_back('0' + i); }
vector<string> tem2;
tem2.push_back(res);
while (maxx >= 10) {
tem2.push_back(to_string(maxx));
int tem = 0;
while (maxx > 0) {
tem += maxx % 10;
maxx /= 10;
}
maxx = tem;
}
tem2.push_back(to_string(maxx));
int tot = 0;
for (auto& p : tem2) {
rep(i, 0, sz(p) - 1) { tot += (p[i] == '0'); }
}
rep(i, 0, cnt[0] - tot - 1) res.push_back('0');
rep(i, 1, sz(tem2) - 1) res += tem2[i];
cout << res << endl;
return;
}
|
F
题目大意： 我们称分数 $\frac{x}{y}$ 的一次增长为以下两种情况之一：
要么把分子 $x$ 加一，要么当分母 $y > 1$ 时，将其减一。
定义 $MSF(b,k)$ 为给定一个整数数组 $b_1,b_2,\ldots,b_m$ 和一个整数 $k$ 时，构造数组 $\frac{1}{b_1},\ldots,\frac{1}{b_m}$ ，一共执行 $k$ 次增长操作（每次增长的对象可以不同）后，得到的分数和的最大值。
现在给定两个整数数组 $a_1,\ldots,a_n$ 和 $k_1,\ldots,k_m$ ，请对每个 $k_i$ 计算 $\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}MSF(a[l \ldots r],k_i) \pmod{998244353}$ 。
数据范围： $1 \leq n,m \leq 5 \cdot 10^5,1 \leq a_i \leq 10^8,0 \leq k_1 \leq k_2 \leq k_m \leq 10^8$ 。
思路：非常迷的是这些 $k_i$ 为啥要排好序，明明可以用在线的说，神秘出题人。
首先，看到这种双求和，在我的分段第一反应一定是单调栈贡献法，此题在Round 1082的d2C2亦有记载。
总的原始和的求法就不讲了，你都做到这里了，没必要吧。
好的，现在我们来看一下，怎么来考虑贡献。
首先，对于 $\frac{a}{b},b > 1$ 时，单次加分子的贡献为 $\frac{1}{b}$ ，减分母的贡献为 $\frac{a}{b(b-1)}$ ，因此当单次加分子的贡献大于等于单次减分母的贡献时，有 $\frac{1}{b} \leq \frac{a}{b(b-1)}$ ，也就是 $b-1 \leq a$ ，而 $b=1$ 时最优策略也是加分子，因此单步的最大贡献必然是加分子。
考虑整个区间，由于显然无论加分子还是减分母，都在分母最小的元素上做文章是最优的，因此这里单调栈的轮廓就浮现出来了，考虑当前元素作为最小的范围。
随后，当 $k$ 很大的时候，又出现了一种策略，那就是首先把 $a_i$ 减到 $1$ ，然后再每次加分子，而当 $k$ 很小的时候直接加分子就可以。
不过，为什么没有别的策略？例如给分子加一些，分母减一些，这个用数学可以证明，此处不提了。
接着，考虑它们之间的分界点，一直加分子的贡献是 $\frac{k}{b}$ ，而先减到 $1$ 再加分子的贡献为 $k-(b-1)+1-\frac{1}{b}=k-b+2-\frac{1}{b}$ ，计算可以得出，一直加分子在 $k \geq b-1$ 的时候是最优的，也就是 $k > b$ 。
于是，由于这里具有单调性，完全可以对 $a$ 进行排序，然后每次查找对应的位置，再做一下前缀和跟后缀和，这里前缀和需要做的是 $\sum\limits_{j=1}^{i} c_j$ 跟 $\sum\limits_{j=1}^{i} -b+2-\frac{1}{b}$ ，后缀和需要做的是 $\sum\limits_{i=1}^{j}\frac{c_i}{b}$ ，这里的 $c_i$ 指的都是当前元素作为最小值的范围。
最后，注意一下C++需要按步取模，第一次交忘了一个取模就wa19了，有点难受，不过这题作为edu的F，最多就是个d2D的水平，不知道出题人在干什么。
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
|
constexpr int MOD = 998244353;
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;
}
void solve() {
ll n, m, k;
cin >> n >> m;
vector<pii> a(n);
rep(i, 0, n - 1) {
cin >> a[i].second;
a[i].first = 1;
}
vector<pll> b(n);
ll tot = 0;
vi r(n, n);
vi l(n, -1);
stack<int> s;
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && a[s.top()].second > a[i].second) s.pop();
if (!s.empty()) r[i] = s.top();
s.push(i);
} // 求右边第一个小于的下标
while (!s.empty()) s.pop();
for (int i = 0; i <= n - 1; i++) {
while (!s.empty() && a[s.top()].second >= a[i].second) s.pop();
if (!s.empty()) l[i] = s.top();
s.push(i);
} // 求左边第一个小于的下标
rep(i, 0, n - 1) {
b[i].first = a[i].second;
b[i].second = 1LL * (r[i] - i) * (i - l[i]);
}
rep(i, 0, n - 1) {
tot += 1LL * (i + 1) * (n - i) % MOD * qpow(a[i].second, MOD - 2) % MOD;
tot %= MOD;
}
ranges::sort(b);
vl pre1(n);
vl suf1(n);
vl pre2(n);
pre1[0] = b[0].second % MOD;
rep(i, 1, n - 1) { pre1[i] = (pre1[i - 1] + b[i].second % MOD) % MOD; }
pre2[0] = b[0].second % MOD * (((2 - b[0].first % MOD - qpow(b[0].first, MOD - 2)) % MOD + MOD) % MOD) % MOD;
rep(i, 1, n - 1) {
ll tem = b[i].second % MOD * (((2 - b[i].first % MOD - qpow(b[i].first, MOD - 2)) % MOD + MOD) % MOD) % MOD;
pre2[i] = (pre2[i - 1] + tem) % MOD;
}
suf1[n - 1] = b[n - 1].second % MOD * qpow(b[n - 1].first, MOD - 2) % MOD;
frep(i, n - 2, 0) {
ll tem = b[i].second % MOD * qpow(b[i].first, MOD - 2) % MOD;
suf1[i] = (suf1[i + 1] + tem) % MOD;
}
rep(i, 0, m - 1) {
cin >> k;
auto x = ranges::upper_bound(b, make_pair(k, LLONG_MAX));
int tem = x - b.begin();
ll tem2, tem3;
if (tem == 0)
tem2 = 0;
else
tem2 = (k * pre1[tem - 1] % MOD + pre2[tem - 1]) % MOD;
if (tem == n)
tem3 = 0;
else
tem3 = k * suf1[tem] % MOD;
cout << (tot + tem2 + tem3) % MOD << endl;
}
return;
}
|
