Absolute Beauty
出处：CF1898D
题目大意：给定 $a_1,\ldots,a_n$ 和 $b_1,\ldots,b_n$ ，定义美丽值为 $\sum\limits_{i=1}^{n}|a_i-b_i|$ ，现在可以交换任意 $b_i,b_j$ 至多一次，问能达到的最大美丽值是多少？
数据范围： $2 \leq n \leq 2 \cdot 10^5,1 \leq a_i,b_i \leq 10^9$ 。
思路：其实是个不难的题目，首先求出原来的美丽值，考虑每次变化对原来的贡献。
通过画图表示交换的两对分别为大于和小于的所有情况，可以将每对数表示为一条线段，观察得出这两条线段交换的贡献就是中间的空白区域长度乘2，于是贪心即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
void solve() {
int n;
cin >> n;
vl a(n);
vl b(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) cin >> b[i];
ll tot = 0;
ll maxx = 0;
rep(i, 0, n - 1) { tot += 1LL * abs(a[i] - b[i]); }
maxx = max(maxx, tot);
vector<pll> ma;
rep(i, 0, n - 1) ma.emplace_back(min(a[i], b[i]), max(a[i], b[i]));
ll mixx2 = ma[0].second;
ll maxx2 = ma[0].first;
rep(i, 1, n - 1) {
if (maxx2 >= ma[i].second) maxx = max(maxx, tot + 2 * (maxx2 - ma[i].second));
if (mixx2 <= ma[i].first) maxx = max(maxx, tot + 2 * (ma[i].first - mixx2));
maxx2 = max(maxx2, ma[i].first);
mixx2 = min(mixx2, ma[i].second);
}
cout << maxx << endl;
return;
}
|
出处：CF1413C
题目大意：给定 $a_1,a_2,\ldots,a_6$ ，现在给定 $b_1,b_2,\ldots,b_n$ ，要求每个 $b_j$ 变为 $b_j-a_i$ ，从而使最大值和最小值之差最小，请求出这个最小差值。
数据范围： $1 \leq n \leq 10^5, 1 \leq b_i \leq 10^9, b_i \geq a_j$
思路：这道题跟LC3854
相似，只需要求出所有可能值，排序后做不定长滑窗，保证当前滑窗内有原来全部元素即可。
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
|
void solve() {
vi a(6);
rep(i, 0, 5) cin >> a[i];
int n;
cin >> n;
vi b(n);
rep(i, 0, n - 1) cin >> b[i];
vector<pii> tem;
rep(i, 0, 5) {
rep(j, 0, n - 1) { tem.emplace_back(b[j] - a[i], j); }
}
ranges::sort(tem);
int l = 0;
map<int, int> ma;
int ans = INT_MAX;
rep(r, 0, sz(tem) - 1) {
ma[tem[r].second]++;
if (sz(ma) == n) {
while (true) {
if (ma[tem[l].second] == 1) break;
ma[tem[l].second]--;
l++;
}
}
if (sz(ma) == n) ans = min(ans, tem[r].first - tem[l].first);
}
cout << ans << endl;
return;
}
|
Split Plus K
出处：CF1909D
题目大意：有 $n$ 个数 $a_1,\ldots,a_n$ ，现在要进行下列操作任意次数：找一个 $x$ ，将其替换为 $y+z=x+k$ ，问最后是否能使剩下的所有数相等？如果可以，最小操作数量是多少？
数据范围： $1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^{12},1 \leq a_i \leq 10^{12}$
思路：首先，分裂可以看成合并，那么考虑最后有 $t$ 个 $b$ ，得到 $t_i \cdot b=(t_i-1) \cdot k+a_i$ ，也就是 $t_i(b-k)=a_i-k$ ，那么此时需要让 $\sum\limits_{i=1}^{n}t_i$ 最小，也就是 $b-k$ 需要是所有 $a_i-k$ 的最大公因数（注意如果出现异号的 $a_i-k$ 就不行了），然后计数即可。
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
|
void solve() {
ll n, k;
cin >> n >> k;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
bool pd = true;
rep(i, 1, n - 1) {
if (a[i] != a[0]) {
pd = false;
break;
}
}
if (pd) {
cout << 0 << endl;
return;
}
rep(i, 0, n - 1) a[i] -= k;
rep(i, 0, n - 1) {
if (a[i] == 0) {
cout << -1 << endl;
return;
}
}
ll mixx = *min_element(all(a));
ll maxx = *max_element(all(a));
if (mixx < 0 && maxx > 0) {
cout << -1 << endl;
return;
}
ll ans = __gcd(abs(a[0]), abs(a[1]));
rep(i, 0, n - 1) { ans = __gcd(ans, abs(a[i])); }
ll res = 0;
rep(i, 0, n - 1) { res += abs(a[i]) / ans; }
cout << res - n << endl;
return;
}
|
Pashmak and Graph
出处：CF459E
题目大意：给定一个 $n$ 个点 $m$ 条边的加权无向图，需要找到一条边数尽可能多的路径（可以不是简单路径），使得路径上每一条边的权值都严格大于前一条边的权值。
数据范围： $2 \leq n \leq 3 \cdot 10^5, 1 \leq m \leq \min(n \cdot (n-1),3 \cdot 10^5)$
思路：就是在图上求LIS，注意由于是LIS因此必然不可能形成自环，此处可以将边按照权值排序，然后做DP，注意这里由于多条边的权值可能相等，因此不能分次序更新，应该同时转移后再重新合并。
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
|
void solve() {
int n, m, x, y, z;
cin >> n >> m;
vector<tri> ma;
rep(i, 0, m - 1) {
cin >> x >> y >> z;
ma.emplace_back(x - 1, y - 1, z);
}
int l = 0;
vi dp(n);
int ans = 0;
map<int, vector<pii>> ma2;
for (auto& [x, y, z] : ma) {
ma2[z].emplace_back(x, y);
}
for (auto& [a, b] : ma2) {
vector<pii> tem;
for (auto& [x, y] : b) {
tem.emplace_back(y, dp[x] + 1);
}
for (auto& p : tem) {
dp[p.first] = max(dp[p.first], p.second);
ans = max(ans, dp[p.first]);
}
}
cout << ans << endl;
return;
}
|
Fafa and Ancient Alphabet
出处：CF935D
题目大意：给定一个字符集，其中字符为 $1 \sim m$ ，给定两个字符串 $S_1$ 和 $S_2$ ，它们中部分已经缺失，用 $0$ 表示，每个 $0$ 位置等概率填上字符集中的数字，问字典序上 $S_1$ 大于 $S_2$ 的概率，请用模 $10^9+7$ 的逆元表示。
数据范围： $1 \leq n,m \leq 10^5$
思路：考虑从前往后遍历，考虑以下四种情况：
- 若 $a_i \not ={0} \wedge b_i=0$ ，那么大于的概率为 $\frac{a_i-1}{m}$ ，等于的概率为 $\frac{1}{m}$ 。
- 若 $a_i=0 \wedge b_i \not ={0}$ ，那么大于的概率为 $\frac{m-b_i}{m}$ ，等于的概率为 $\frac{1}{m}$ 。
- 若 $a_i=0 \wedge b_i=0$ ，那么大于的概率为 $\frac{m-1}{2m}$ ，等于的概率为 $\frac{1}{m}$ 。
- 若 $a_i \not ={0} \wedge b_i \not ={0}$ ，那么分以下三种情况：
- $a_i>b_i$ ，那么答案加上之前相等的概率，并输出
- $a_i<b_i$ ，直接输出答案
- $a_i=b_i$ ，无变化，继续遍历
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
|
void solve() {
int n, m;
cin >> n >> m;
vi a(n);
vi b(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) cin >> b[i];
vector<pii> ma(n);
ll tem = 1;
ll ans = 0;
rep(i, 0, n - 1) {
if (a[i] != 0 && b[i] != 0) {
if (a[i] < b[i]) {
cout << ans << endl;
return;
} else if (a[i] == b[i]) {
continue;
} else {
ans += tem;
ans %= MOD;
cout << ans << endl;
return;
}
} else if (a[i] != 0 && b[i] == 0) {
ans += mul(tem, mul(a[i] - 1, qpow(m, MOD - 2)));
ans %= MOD;
tem = mul(tem, qpow(m, MOD - 2));
} else if (a[i] == 0 && b[i] != 0) {
ans += mul(tem, mul(m - b[i], qpow(m, MOD - 2)));
ans %= MOD;
tem = mul(tem, qpow(m, MOD - 2));
} else {
ans += mul(tem, mul(m - 1, qpow(2 * m, MOD - 2)));
ans %= MOD;
tem = mul(tem, qpow(m, MOD - 2));
}
}
cout << ans << endl;
return;
}
|
