Codeforces Round 985 div1+2 个人题解(A~E)

Dashboard - Refact.ai Match 1 (Codeforces Round 985) - Codeforces

火车头

#include <bits/stdc++.h>using namespace std;#define ft first
#define sd second#define yes cout << "yes\n"
#define no cout << "no\n"#define Yes cout << "Yes\n"
#define No cout << "No\n"#define YES cout << "YES\n"
#define NO cout << "NO\n"#define pb push_back
#define eb emplace_back#define all(x) x.begin(), x.end()
#define all1(x) x.begin() + 1, x.end()
#define unq_all(x) x.erase(unique(all(x)), x.end())
#define unq_all1(x) x.erase(unique(all1(x)), x.end())
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fLL#define RED cout << "\033[91m"     // 红色
#define GREEN cout << "\033[92m"   // 绿色
#define YELLOW cout << "\033[93m"  // 蓝色
#define BLUE cout << "\033[94m"    // 品红
#define MAGENTA cout << "\033[95m" // 青色
#define CYAN cout << "\033[96m"    // 青色
#define RESET cout << "\033[0m"    // 重置typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// typedef __int128_t i128;typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<string, ll> psl;typedef tuple<int, int, int> ti3;
typedef tuple<ll, ll, ll> tl3;
typedef tuple<ld, ld, ld> tld3;typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vl> vvl;// std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());template <typename T>
inline T read()
{T x = 0;int y = 1;char ch = getchar();while (ch > '9' || ch < '0'){if (ch == '-')y = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar();}return x * y;
}template <typename T>
inline void write(T x)
{if (x < 0){putchar('-');x = -x;}if (x >= 10){write(x / 10);}putchar(x % 10 + '0');
}/*#####################################BEGIN#####################################*/
void solve()
{
}int main()
{ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);// freopen("test.in", "r", stdin);// freopen("test.out", "w", stdout);int _ = 1;std::cin >> _;while (_--){solve();}return 0;
}/*######################################END######################################*/
// 链接：

A. Set

8
3 9 2
4 9 1
7 9 2
2 10 2
154 220 2
147 294 2
998 24435 3
1 1000000000 2

2
6
0
4
0
1
7148
500000000

解题思路

对于一个数$n$，我们能构造出的最大的有 $k$ 个 $x$ 的倍数的$x$为$\lfloor \frac{n}{k}\rfloor$。因此，答案为$\max (0,\lfloor \frac{r}{k}\rfloor -l+1)$

实现代码

void solve()
{ll l, r, k;cin >> l >> r >> k;cout << max(0ll, r / k - l + 1) << "\n";
}

B. Replacement

6
2
11
0
2
01
1
4
1101
001
6
111110
10000
6
010010
11010
8
10010010
0010010

NO
YES
YES
NO
YES
NO

解题思路

注意到我们每次是选择一个$01$或者$10$来进行替换，使其留下$1$或者$0$，因此，每个替换都等价于删除另一种数字，例如替换为$1$等价于删除一个$0$，所以，我们可以维护$0$和$1$的数量，如果在最后一次删除前$0$和$1$的数量归零则游戏输了。

实现代码

void solve()
{int n;string s, r;cin >> n >> s >> r;int cnt0 = 0;int cnt1 = 0;for (auto c : s){if (c == '1')cnt1++;elsecnt0++;}if (cnt0 == 0 || cnt1 == 0){NO;return;}for (int i = 0; i < n - 1; i++){if (r[i] == '1')cnt0--;elsecnt1--;if (i == n - 2)continue;if (cnt0 == 0 || cnt1 == 0){NO;return;}}YES;
}

C. New Rating

5
6
1 2 3 4 5 6
7
1 2 1 1 1 3 4
1
1
9
9 9 8 2 4 4 3 5 3
10
1 2 3 4 1 3 2 1 1 10

5
4
0
4
5

解题思路

我们可以设计三个$dp$值$f,g,h$，$f[i]$代表第$i$次比赛不进行任何跳过的评分，$g[i]$代表第$i$次比赛正在进行跳过的最大评分，$h[i]$代表第$i$次比赛已经进行跳过后的最大平方，我们令$calc(a[i])$代表评级的更新规则，则可以得到以下状态转移方程：$f[i]=f[i-1]+clac(a[i]),g[i]=\max (g[i-1],f[i]),h[i]=\max (h[i-1]+calc(a[i]),g[i-1])$

实现代码

void solve()
{int n;cin >> n;vi a(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];}vi f(n + 1, -inf);vi g(n + 1, -inf);vi h(n + 1, -inf);f[0] = g[0] = h[0] = f[1] = h[1] = 0;for (int i = 1; i <= n; i++){int v = a[i];if (f[i - 1] < v)f[i] = f[i - 1] + 1;else if (f[i - 1] == v)f[i] = f[i - 1];elsef[i] = f[i - 1] - 1;g[i] = max(f[i], g[i - 1]);if (i == 1)continue;if (h[i - 1] < v)h[i] = h[i - 1] + 1;else if (h[i - 1] == v)h[i] = h[i - 1];elseh[i] = h[i - 1] - 1;h[i] = max(h[i], g[i - 1]);}cout << h[n] << endl;
}

D. Cool Graph

5
3 0
3 1
1 2
3 2
1 2
2 3
3 3
1 2
2 3
3 1
6 6
1 2
1 6
4 5
3 4
4 6
3 6

0
1
1 2 3
0
1
1 2 3
3
1 3 6
2 4 5
3 4 6

解题思路

看到限制条件为最多可以进行 $2\cdot \max (n,m)$ 次操作，结合树的边数为 $n-1$ ，因此我们可以考虑先将图删掉尽可能能多的边，然后再重新构建出一棵树，刚好可以接近用完操作。

顺着这个思路往下想，对于一个度数大于等于 $2$ 的点 $x$ ，我们可以选择对 $x$ 和它的两个邻接点 $y$ 和 $z$ 进行操作，如果 $y$ 和 $z$ 存在一条边，则一次性删除了三条边，否则，我们删除了两条边并构建了一条边 $(y,z)$ ，至少删除了一条边。因此，我们最多不会超过 $m$ 次，就可以将 这个图删的只剩下孤点和孤边。如果没有孤边，说明所有边已被删除，直接满足要求。

考虑对一堆孤点和孤边进行操作来构建一棵树。

我们可以选取一个孤边作为树的基础。

如果遇见孤点，则对树的两个端点 $x$ 和 $y$ 以及孤点 $z$ 进行操作，这样我们相当于在 $x$ 和 $y$ 之间插入了一个点 $z$ 使得边 $x\to y$ 变成 $x\to z\to y$ ，然后我们把 $z$ 赋值给 $y$ 即可。

如果遇见孤边，则对孤边的两个端点 $u$ 和 $v$ 和树的端点 $x$ 进行操作，这样我们相当于将 $u$ 和 $v$ 与端点 $x$ 建边，使得边 $u\to v,x$ 变成 $u\to x\leftarrow v$ 。

实现代码

void solve()
{int n, m;cin >> n >> m;vector<set<int>> adj(n + 1);for (int i = 0; i < m; i++){int u, v;cin >> u >> v;adj[u].insert(v);adj[v].insert(u);}if (m == 0){cout << "0\n";return;}vector<array<int, 3>> ans;auto del = [&](int a, int b, int c){adj[a].erase(b);adj[b].erase(a);adj[a].erase(c);adj[c].erase(a);if (adj[b].find(c) != adj[b].end()){adj[b].erase(c);adj[c].erase(b);}else{adj[b].insert(c);adj[c].insert(b);}};for (int i = 1; i <= n; i++){while (adj[i].size() >= 2){int a = i;int b = *adj[i].begin();int c = *next(adj[i].begin());ans.pb({a, b, c});del(a, b, c);}}int u = 0, v = 0;for (int i = 1; i <= n; i++){if (adj[i].size() == 1){u = i;v = *adj[i].begin();break;}}if (u){vb vis(n + 1);vis[u] = vis[v] = 1;for (int i = 1; i <= n; i++){if (vis[i])continue;if (adj[i].size() == 1){ans.pb({u, i, *adj[i].begin()});vis[i] = 1;vis[*adj[i].begin()] = 1;}else{ans.pb({u, v, i});vis[i] = 1;v = i;}}}cout << ans.size() << "\n";for (auto [a, b, c] : ans){cout << a << " " << b << " " << c << "\n";}
}

E. Common Generator

4
3
8 9 10
4
2 3 4 5
2
147 154
5
3 6 8 25 100000

2
-1
7
3

解题思路

由于一个数 $x$ 可以增加它的因数 $d$ ，我们很容易就可以想到，要构造一个数 $a_i$ ，我们只要要构造出它的因数的倍数 $kd$ 并使得 $kd\le a_i$，我们就可以很轻松的构造出 $a_i$ 。由于每次操作都是对当前值进行加法，因此我们因数 $d$ 选的越小，我们的操作空间越大，所以为了构造出 $a_i$ ,我们一定是选择它的最小质因数 $p$ 来进行构造。

1. 考虑 $a_i$ 为偶数，我们只要选择 $x=2$，就一定可以构造出 $a_i$ 。
2. 考虑 $a_i$ 为非质数的奇数，我们也只要选择 $x=2$，就一定可以构造出 $a_i$ 。对于$a_i$，我们只需要将 $x$ 加上 $p-1$ 次 $2$ 就可以获得因数最小包含 $a_i$ 最小质数因子 $p$ 的数 $2\times p$ 。由于$a_i$ 为非质数的奇数，其最小质因子最小为 $3$ ，因此 $a_i \gt 2\times p $，我们只要对 $2\times p$ 不断加上 $p$ 就可以得到 $a_i$ 。
3. 考虑 $a_i$ 为质数，我们只能选择它自己来获得它。

综上

1. 如果 $a$ 中质数数量大于 $1$ ，则不存在符合要求的整数。

2. 如果 $a$ 中质数数量等于 $0$ ，则选择 $x=2$ 一定可以构造出所有 $a_i$ 。

3. 如果 $a$ 中质数数量等于 $1$ ，则我们只能选择选择 $x=\text{pri}$ ，$\text{pri}$ 为唯一的质数。

   考虑检查$x=\text{pri}$ 是否可以生成所有 $a_i$

   • 对于 $a_i$ 为偶数，只要 $a_i\le 2\times \text{pri}$ ，我们就可以使得选择器包含因数 $2$ 从而构造出所有偶数。
   • 对于 $a_i$ 为奇数，只要$a_i-p\le 2\times \text{pri}$ ，我们就可以使得选择器包含因数 $2$ 从而构造出 $2\times p$ 进而构造出 $a_i$ 。

实现代码

const int N = 4e5;vector<int> minp;   // 存储每个数的最小质因子
vector<int> primes; // 存储找到的所有质数// 欧拉筛函数
void sieve(int n)
{minp.assign(n + 1, 0); // 初始化最小质因子数组primes.clear();        // 清空质数数组for (int i = 2; i <= n; i++){if (minp[i] == 0){                        // 如果 minp[i] 仍为 0，说明 i 是质数minp[i] = i;         // 记录 i 的最小质因子为自身primes.push_back(i); // 将 i 添加到质数列表中}// 遍历已找到的质数for (auto p : primes){if (i * p > n){ // 如果 i * p 超过 n，停止break;}minp[i * p] = p; // 记录 i * p 的最小质因子if (p == minp[i]){ // 如果当前质数等于 i 的最小质因子，停止break;}}}
}void solve()
{int n;cin >> n;vi a(n);int cntPri = 0;int pri = 0;for (int i = 0; i < n; i++){cin >> a[i];if (minp[a[i]] == a[i]){cntPri++;pri = a[i];}}if (cntPri >= 2){cout << "-1\n";return;}if (cntPri == 0){cout << "2\n";return;}for (int i = 0; i < n; i++){if (a[i] == pri)continue;int v = a[i] & 1 ? a[i] - minp[a[i]] : a[i];if (pri * 2 > v){cout << "-1\n";return;}}cout << pri << "\n";
}

这场没打，第二天就是区赛，不敢打。

感觉这场挺简单的。