Weakened Common Divisor
出处：CF1025B
题目大意：我们定义弱公约数，给出几对数 $(a_1,b_1),\ldots,(a_n,b_n)$ ，它们的弱公约数满足大于1，且能整除每个数对中至少一个数，给你几对数，求它们的弱公约数。
数据范围： $1 \leq n \leq 150000,2 \leq a_i,b_i \leq 2 \cdot 10^9$
思路：注意到只需要求出第一对数的所有因数并验证即可。
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;
cin >> n;
vector<pii> ma(n);
rep(i, 0, n - 1) cin >> ma[i].first >> ma[i].second;
set<int> s;
bool flag = false;
for (int i = 2; i * i <= ma[0].first; i++) {
if (ma[0].first % i == 0) {
if (check(i)) s.insert(i);
if (check(ma[0].first / i)) s.insert(ma[0].first / i);
flag = true;
}
}
if (!flag) s.insert(ma[0].first);
flag = false;
for (int i = 2; i * i <= ma[0].second; i++) {
if (ma[0].second % i == 0) {
if (check(i)) s.insert(i);
if (check(ma[0].second / i)) s.insert(ma[0].second / i);
flag = true;
}
}
if (!flag) s.insert(ma[0].second);
rep(i, 1, n - 1) {
for (auto it = s.begin(); it != s.end();) {
int p = *it;
if (ma[i].first % p != 0 && ma[i].second % p != 0) {
it = s.erase(it);
} else
it++;
}
if (s.empty()) break;
}
if (s.empty())
cout << -1 << endl;
else
cout << *s.begin() << endl;
return;
}
|
Row GCD
出处：CF1458A
题目大意：给定 $a_1,\ldots,a_n$ 和 $b_1,\ldots,b_m$ ，对于 $j \in [1,m]$ ，请求出 $gcd(a_1+b_j,\ldots,a_n+b_j)$
数据范围： $1 \leq n,m \leq 2 \cdot 10^5,1 \leq a_i \leq 10^{18},1 \leq b_j \leq 10^{18}$
思路：注意有 $gcd(a_1+b_j,\ldots,a_n+b_j)=gcd(a_1+b_j,a_2-a_1,\ldots,a_n-a_{n-1})$ ，于是只需要预处理后面的最大公因数即可。
1
2
3
4
5
6
7
8
9
10
11
12
|
void solve() {
int n, m;
cin >> n >> m;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl b(m);
rep(i, 0, m - 1) cin >> b[i];
ll tem = 0;
frep(i, n - 1, 1) { tem = __gcd(tem, abs(a[i] - a[i - 1])); }
rep(i, 0, m - 1) { cout << __gcd(tem, a[0] + b[i]) << ' '; }
return;
}
|
Insert a Progression
出处：CF1671D
题目大意：给定 $a_1,\ldots,a_n$ ，同时给 $x$ 个正整数 $1,2,\ldots,x$ ，需要将这 $x$ 个数插入到序列首位，末位以及任意两个元素之间。
现在需要使 $\sum\limits_{i=1}^{n+x-1}|a_i-a_{i+1}|$ 最小，请求出这个最小值。
数据范围： $1 \leq n,x \leq 2 \cdot 10^5,1 \leq a_i \leq 2 \cdot 10^5$
思路：注意到如果 $[a_i,a_{i+1}]$ 之间的元素插进去完全没影响，可以考虑区间合并，不过更简单的办法是求出最大值和最小值，然后插（可以想想为什么）。
然后，对于剩下的元素，分为比最小值小的，和最大值大的，考虑插在首尾哪里，或者插在最大值/最小值旁边即可。
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
|
void solve() {
int n, x;
cin >> n >> x;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
if (n == 1) {
cout << ((a[0] >= 1 && a[0] <= x) ? x - 1 : a[0] - 1) << endl;
return;
}
ll ans = 0;
rep(i, 0, n - 2) ans += 1LL * abs(a[i + 1] - a[i]);
vector<pll> res;
vector<pll> ma;
rep(i, 0, n - 2) ma.emplace_back(min(a[i], a[i + 1]), max(a[i], a[i + 1]));
ranges::sort(ma);
rep(i, 0, n - 2) {
if (!res.empty() && ma[i].first <= res.back().second) {
res.back().second = max(res.back().second, ma[i].second);
} else
res.emplace_back(ma[i]);
}
ll tem = 0;
ll tem2 = *min_element(all(a));
ll tem3 = *max_element(all(a));
tem = min({a[0] - 1, a[n - 1] - 1, 2 * (tem2 - 1)});
ll tem4 = 0;
tem4 = min({max(0LL, x - a[n - 1]), max(0LL, x - a[0]), 2 * max(0LL, x - tem3)});
cout << ans + tem + tem4 << endl;
return;
}
|
Least Prefix Sum
出处：CF1779C
题目大意：给定一个数组 $a_1,\ldots,a_n$ ，现在可以进行若干次以下操作：即选择某个下标 $i$ ，将 $a_i$ 变为它的相反数，最后要使 $pre_m$ 变为其非严格最小的前缀和，问操作次数最少是多少？
数据范围： $1 \leq m \leq 2 \cdot 10^5, -10^9 \leq a_i \leq 10^9$
思路：首先很容易考虑到前后的贪心策略，但是这里讲的是，每次应该取当前绝对值最大的操作，而不是对当前元素进行操作，从而尽量较少操作次数，这样操作需要用到堆。
这道题没做出来，要多想。
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, m;
cin >> n >> m;
m--;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
ll tem = 0;
int ans = 0;
priority_queue<ll, vector<ll>, greater<>> q;
rep(i, m + 1, n - 1) {
tem += 1LL * a[i];
if (a[i] < 0) q.push(a[i]);
while (tem < 0 && !q.empty()) {
auto node = q.top();
q.pop();
tem -= 2 * node;
ans++;
}
}
tem = 0;
priority_queue<ll, vector<ll>, less<>> q1;
while (!q.empty()) q.pop();
frep(i, m, 1) {
tem += 1LL * a[i];
if (a[i] > 0) q1.push(a[i]);
while (tem > 0 && !q1.empty()) {
auto node = q1.top();
q1.pop();
tem -= 2 * node;
ans++;
}
}
cout << ans << endl;
return;
}
|
Round Dance
出处：CF1833E
题目大意：有 $n$ 个人来到节日现场，他们要跳圆圈舞，每个圆圈舞必须至少有两个人，现在每个人只记得自己的一个邻居，问可能的圆圈舞的最大和最小数量是多少？
数据范围： $2 \leq n \leq 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
45
46
47
48
49
|
void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) a[i]--;
vvi ma(n);
rep(i, 0, n - 1) {
ma[i].push_back(a[i]);
ma[a[i]].push_back(i);
}
int ans = 0;
int ans2 = 0;
vi vis(n);
rep(i, 0, n - 1) {
if (vis[i]) continue;
queue<int> q;
vi tem;
vis[i] = 1;
q.push(i);
while (!q.empty()) {
auto node = q.front();
q.pop();
tem.push_back(node);
for (int& p : ma[node]) {
if (!vis[p]) {
vis[p] = 1;
q.push(p);
}
}
}
bool pd = true;
for (int& p : tem) {
if (sz(ma[p]) != 2) {
pd = false;
break;
}
}
if (pd && sz(tem) >= 3)
ans++;
else
ans2++;
}
if (ans2)
cout << ans + 1 << ' ' << ans + ans2 << endl;
else
cout << ans << ' ' << ans << endl;
return;
}
|
Ordered Permulations
出处：CF2040C
题目大意：给定 $1 \sim n$ 的一个排列 $p_1,\ldots,p_n$ ，定义 $S(p)=\sum\limits_{1 \leq l \leq r \leq n}\min(p_l,\ldots,p_r)$ ，要找到使 $S(p)$ 最大的排列，并且按照字典序选取第 $k$ 个，如果这样的排列数量小于 $k$ ，就输出 $-1$ 。
数据范围：$1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^{12}$
思路：手玩发现，只需要按照顺序将当前最小值放在两侧的其中一侧，就可以使最后的结果最小（单调栈也可以这么想），于是转化为字典序问题，这就不难了。
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() {
ll n, k;
cin >> n >> k;
vi a(n);
if (n <= 62 && k > (1LL << (n - 1))) {
cout << -1 << endl;
return;
}
int l = 0, r = n - 1;
rep(i, 1, n - 1) {
int tem = n - i - 1;
ll tem2;
if (tem >= 62)
tem2 = LLONG_MAX;
else
tem2 = (1LL << tem);
if (k > tem2) {
k -= tem2;
a[r] = i;
r--;
} else {
a[l] = i;
l++;
}
}
rep(i, 0, n - 1) {
if (a[i] == 0) {
a[i] = n;
break;
}
}
rep(i, 0, n - 1) cout << a[i] << ' ';
cout << endl;
return;
}
|
Dreamoon and Sums
出处：CF476C
题目大意：给定 $a$ 和 $b$ ，定义好数为 $x \pmod{b} \not ={0}$ 且 $\frac{\frac{x}{b}}{x \pmod{b}}=k$ ，其中 $k \in [1,a]$ 且为整数，现在要求 好数的个数，并对 $10^9+7$ 取模。
数据范围： $1 \leq a,b \leq 10^7$
思路：令 $x=tb+r$ ，则有 $r \not ={0}$ 且 $t=kr$ ，得到 $x=krb+r=r(kb+1)$ ，同时有 $r \in [1,b-1],k \in [1,a]$ ，直接计数即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void solve() {
ll a, b;
cin >> a >> b;
if (b == 1) {
cout << 0 << endl;
return;
}
ll tem = b * (b - 1) / 2 % MOD * a % MOD;
ll tem2 = (a + 1) * a / 2 % MOD * (b * (b - 1) / 2 % MOD) % MOD;
ll tem3 = tem2 * b % MOD;
cout << (tem + tem3) % MOD << endl;
return;
}
|
Tell Your World
出处：CF849B
题目大意：给定 $n$ 个平面上的点，问是否能画两条平行且不重叠的线，使得集合中的每个点都在他们之中的一条线上，且每条线至少经过一个点。
数据范围： $3 \leq n \leq 1000$
思路：根据抽屉原理，前三个点至少有两个点位于同一条线上，找出这条线，遍历，再验证其他点是否在另一条线上即可。
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
|
void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
double tem1 = a[1] - a[0], tem2 = (a[2] - a[0]) / 2.0, tem3 = (a[2] - a[1]);
auto check = [&](double x) -> bool {
bool flag = false;
int idx = -1;
rep(i, 1, n - 1) {
if ((a[i] - a[0]) == x * i) continue;
if (!flag) {
idx = i;
flag = true;
} else {
if ((a[i] - a[idx]) != x * (i - idx)) {
flag = 0;
break;
}
}
}
if (!flag)
return false;
else
return true;
};
if (check(tem1) || check(tem2) || check(tem3)) {
cout << "YES" << endl;
return;
}
cout << "NO" << endl;
return;
}
|
