Educational Codeforces Round 180 (Rated for Div. 2)¶
created: 2025-06-25 00:58:42
25号上午考最后一门数据库，考完就可以尽情写题了，最近一个月都没咋写。
刚才大概数了一下，目前这个博客里的CF博客数量好像是24篇，有点太少阿，虽然也是有几场还没有写博客，但是也很少。
以后必须每场打完就开始写，因为很多时候也是等st，不如早点把博客写了呢...
这场打的勉强还行，排名稍微像人类一点了。E没有思路啊。明天就看看题解吧～（应该是今天）。
A¶
直接每局就行。
// Date: 2025-06-23
// Time: 22:34:41
void ChatGptDeepSeek()
{
int a, x, y;
cin >> a >> x >> y;
if(x > y) swap(x, y);
for(int b = x; b <= y; b++){
if(abs(b - x) < abs(a - x) && abs(b - y) < abs(a - y)){
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
B¶
发现最多只需要操作一次，若不为单调递增或递减，则必最多只需要操作一次。
因为这样想，假如对于 \(i\)， 有 \(a_{i - 1} < a_i, a_i > a_{i + 1}\)，所以 a_i 一定可以和 \(min(a_{i-1},a_{i+1})\) 合并变成 \(max(a_{i-1},a_{i+1})\)，小于也是同理，所以若不为有序的，则必只需要操作一次。
// Date: 2025-06-23
// Time: 22:41:58
void ChatGptDeepSeek()
{
// x,
// 1 3 4 5 6 4 3
int n;
cin >> n;
vi a(n + 1);
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i < n; i++){
if(abs(a[i] - a[i + 1]) <= 1){
cout << "0\n";
return;
}
}
for(int i = 2; i < n; i++){
if(a[i - 1] < a[i] && a[i + 1] < a[i]){
cout << "1\n";
return;
}
if(a[i - 1] > a[i] && a[i + 1] > a[i]){
cout << "1\n";
return;
}
}
// 1 4 5 1
cout << "-1\n";
}
C¶
当时想得稍微有点复杂，想得也有点慢，用了树状数组，然后我很担心会 fst，因为 1000 * \(10^5\) 的树状数组，感觉可能会 T 吧，看他们都是二分写的。不过也过了，而且时间挺快的。
就是分析限制，我们就假设选两个小的数是 \(a_l\), \(a_r\)，第三个数字假如是 \(x\)，则 \(x < a_l + a_r\) 且 \(a_l + a_r + x > a_n\)，显然符合条件的 \(x\) 在一个区间里，如果事先给 \(a\) 排好序，这里 \(a\) 的顺序不影响答案，所以肯定一开始排个序好搞点。
因为 \(n \le 5000\)， 所以双重循环枚举小的两个数字肯定没问题，再用二分来找出合法的第三个数字的区间，当然用树状数组也行，不过确实是稍微麻烦一点。
// Date: 2025-06-23
// Time: 22:49:48
constexpr int N = int(1e5);
struct Fenwick{
vector<int> b;
Fenwick (int n){
b.assign(n, 0);
}
int lowbit(int x){return (x) & (-x);}
void add(int i, int x){
while(i < b.size()){
b[i] += x;
i += lowbit(i);
}
}
int query(int i){
int res = 0;
while(i){
res += b[i];
i -= lowbit(i);
}
return res;
}
int get(int l, int r){
return query(r) - query(l - 1);
}
};
void ChatGptDeepSeek()
{
int n;
cin >> n;
vi a(n + 1);
for(int i = 1; i <= n; i++)
cin >> a[i];
// vc<vl> dp(2, vl (N + 1));
sort(ALL(a));
// vl dp(3 * a[n] + 1);
/*
拿的这三个数
它们的和要大于最大的数字
且两个小的数字的和要大于最大的那个数字
*/
// x + y > z && x + y + z > mx
// z < x + y, z > mx - x - y
// z []
Fenwick tr(a[n] + 1);
// for(int i = 1; i <= n; i++){
// tr.add(a[i], 1);
// }
ll ans = 0;
// for(int l = 1; l < n; l++){
// for(int r = l + 1; r <= n; r++){
// int R = a[l] + a[r] - 1, L = a[n] - a[l] - a[r] + 1;
// L = max(a[r], L);
// if(L > R) continue;
// int cnt =
// // cerr << format("a[l] = {}, a[r] = {}, L = {}, R = {}, cnt = {}, l = {}, r = {}\n", a[l], a[r], L, R, cnt,l , r);
// ans += cnt;
// }
// }
for(int r = n; r >= 1; r--){
for(int l = r - 1; l >= 1; l--){
int R = a[l] + a[r] - 1, L = a[n] - a[l] - a[r] + 1;
L = max(a[r], L);
R = min(R, a[n]);
if(L > R) continue;
ans += tr.get(L, R);
}
tr.add(a[r], 1);
}
cout << ans << '\n';
}
然后刚才用二分重写了一个，std::lower_bound 确实爽阿。
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++)
cin >> a[i];
sort(a.begin() + 1, a.end());
/*
a[l] + a[r] + x > a[n], x < a[l] + a[r]
x > a[n] - a[l] - a[r]
*/
long long ans = 0;
for(int l = 1; l <= n; l++){
for(int r = l + 1; r < n; r++){
auto L = upper_bound(a.begin() + r + 1, a.end(), a[n] - a[l] - a[r]) - a.begin();
auto R = lower_bound(a.begin() + r + 1, a.end(), a[l] + a[r]) - a.begin() - 1;
if(L <= R)
ans += R - L + 1;
}
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while(t--)
solve(); return 0;
}
D¶
又是一个不难的D题，稍微想下画画图就看出来啦。
首先必须存在度为2的点，否则无论如何，不可能存在合法的方案。
那么很简单了，就让其他点都恰好只有一条路径，度为2的那个点的子结点的边反一下就行。注意选取的度为2的点，不能是 dfs 选的根节点，然后就没啥要注意的了，直接写就行。
// Date: 2025-06-23
// Time: 23:34:39
void ChatGptDeepSeek()
{
int n;
cin >> n;
vc<vi> g(n + 1);
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int vertex = -1;
for(int i = 2; i <= n; i++){
if(g[i].size() == 2){
vertex = i;
break;
}
}
int root = 1;
if(vertex == -1){
if(g[1].size() == 2){
root = 2;
vertex = 1;
}else{
cout << "NO\n";
return;
}
}
cout << "YES\n";
vc<pii> ans;
auto dfs = [&](auto &&self, int u, int pre, int s) -> void{
if(u == vertex) s ^= 1;
for(auto v : g[u]){
if(v == pre) continue;
if(s) ans.push_back({u, v});
else ans.push_back({v, u});
self(self, v, u, s ^ 1);
}
};
dfs(dfs, root, 0, 1);
for(auto [u, v] : ans)
cout << u << " " << v << '\n';
}
E¶
upd: 考完了，但并没有刷题，只是把这个 E 题看了一下，直接启动的题解，因为过的人算挺少。但是这题挺有意思的，要是多想一下就好了，虽然不一定能想得出来。
如果一个节点不是绿色，那么这颗子树必然颜色全都相同，否则假如这里有其他颜色，则到根节点必须经过不同的颜色。
但如果自己想，就算想到了这个，可能也很难写。由于我是看了题解的，所以要用dp，这还真没想过要dp。
让 \(cnt_u\) 表示 \(u\) 为绿色时，以 \(u\) 为根节点的子树的染色方式，如果 \(u\) 为黄色或者蓝色，都只会有一种染色方式。所以 \(u\) 的子树的染色方式是 \(cnt_u + 2\)。
因为每个子树都可以被独立的染色，因此 $cnt_v = (cnt_{u1} + 2)(cnt_{u2} + 2) \ldots (cnt_{uk} + 2) $，其中 \({u1, u2,\ldots,uk}\) 是 \(v\) 的子节点。
然后就可以用 \(dp\) 求了： 让 \(dp_m\) 是 \(m\) 种染色方法的树的最小节点数，注意到每个节点的染色数是它的子节点的染色数的乘积，那么 \(dp_m = min(dp_m, dp_{\frac{m}{x}} + dp_{x - 2})\)，其中 \(x\) 为 \(m\) 的因子。
这里怎么理解呢？相当于是我们去找一个已经染色数为 \(\frac{m}{x}\) 的树，那么我们只要再加一个染色树为 \(x\) 的树，那么新的树的染色树就会正好是 \(m\)，因为多一个子节点，就可以乘子节点的染色数。那么为什么是 \(x-2\) 呢？因为我们的 \(dp\) 表示的是根节点为绿色的染色需要的节点数量，它作为子节点时，染色数量是要 \(+2\) 的，所以我们这里直接减。
直接枚举 \(m\) 和因子，时间复杂度是 \(O(M\sqrt{M})\),也可以 \(O(M\log{M})\)。
#include<bits/stdc++.h>
using namespace std;
constexpr int M = int(5e5);
constexpr int inf = int(1e9);
int dp[M + 1];
void solve(){
int m;
cin >> m;
cout << (dp[m] != inf ? dp[m] : -1) << '\n';
}
int main(){
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
for(int i = 1; i <= M; i++)
dp[i] = inf;
dp[1] = 1;
for(int m = 2; m <= M; m++){
for(int p = 1; p * p <= m; p++){
if(m % p) continue;
if(p > 2) dp[m] = min(dp[m], dp[m / p] + dp[p - 2]);
if(m / p > 2) dp[m] = min(dp[m], dp[p] + dp[m / p - 2]);
}
}
int t; cin >> t; while(t--)
solve(); return 0;
}
\(M\log{M}\) 的,哇这个枚举因子很快啊。
#include<bits/stdc++.h>
using namespace std;
constexpr int M = int(5e5);
constexpr int inf = int(1e9);
int dp[M + 1];
void solve(){
int m;
cin >> m;
cout << (dp[m] != inf ? dp[m] : -1) << '\n';
}
int main(){
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
for(int i = 1; i <= M; i++)
dp[i] = inf;
dp[1] = 1;
for(int a = 1; a <= M; a++){
for(int b = 1; b * (a + 2) <= M; b++)
dp[(a + 2) * b] = min(dp[(a + 2) * b], dp[a] + dp[b]);
}
int t; cin >> t; while(t--)
solve(); return 0;
}