[Educational Codeforces Round 141 (Rated for Div. 2)题解

news/2024/12/4 16:25:49/

Educational Codeforces Round 141 (Rated for Div. 2)

A. Make it Beautiful

题意
重排数组判断是否能够不存在任何元素等于其前面的数之和
题解
全部相同则不行,否则排序后最小最大次小次大即可构造出

#include<bits/stdc++.h>
#define io ios::sync_with_stdio(false);cin.tie(0);
using namespace std;int main() {int t, n;cin >> t;while (t--) {cin >> n;vector<int> a(n);for (int i = 0; i < n; ++i)cin >> a[i];sort(a.begin(), a.end());if (a.front() == a.back()) {cout << "NO\n";} else {cout << "YES\n";int i = 0, j = a.size() - 1;int op = 0;while (i <= j) {if (!op)cout << a[i++] << " ";elsecout << a[j--] << " ";op ^= 1;}cout << "\n";}}return 0;
}

B. Matrix of Differences

题意
排列填进一个数组,使得两两绝对值种类最多
题解
显然每一行仍是最小最大次小次大,每一行翻转一次即可

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int maxn = 4e6+10;
const int mod = 1e9+7;void solve() {int n;cin >> n;vector<vector<int>> a(n, std::vector<int>(n));int l = 1, r = n * n;int ok = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {a[i][j] = ok ? l++ : r--;ok ^= 1;}if (i & 1) reverse(a[i].begin(), a[i].end());}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cout << a[i][j] << " \n"[j == n - 1];}}
}int main() {ios::sync_with_stdio(false),cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}
}

C. Yet Another Tournament

题意
你和 n n n个人比赛,第i个人一开始能赢前面 i − 1 i - 1 i1个人,即赢 i − 1 i - 1 i1场,你有 m m m的初始值, m ≥ a [ i ] m \geq a[i] ma[i]即可赢第 i i i个人,按胜场排 r k rk rk,问你的最优 r k rk rk是什么。
题解
显然贪心的选最小的 k k k个人,考虑第 k + 1 k + 1 k+1个人能否替换第 k k k个人,能替换的话等价于原本你, k k k, k + 1 k + 1 k+1的排名由3, 2, 1变成1, 1, 1则排名上升,每个都更新答案即可。

#include<bits/stdc++.h>using namespace std;
const int maxn = 5e5 + 5;
int a[maxn], b[maxn], s[maxn];
int main() {int t;cin >> t;while(t -- ){int n , m;cin >> n >> m;for(int i = 1 ; i <= n ; i ++ ){cin >> a[i];b[i] = a[i];}sort(b + 1 , b + 1 + n);for(int i = 1 ; i <= n ; i ++ ){s[i] = s[i - 1] + b[i];}int res = n + 1; //有 n + 1 个人for(int i = 1 ; i <= n ; i ++ ){if(m >= s[i]){res = min(res , n - i + 1);}if(i < n && m >= s[i] + max(a[i + 1] - b[i] , (int)0)){res = min(res , n - i);}}cout << res << "\n";}return 0;
}

D. Different Arrays

题意
你有 n − 1 n - 1 n1次操作,顺序将 a i a_i ai a i − 1 a_{i-1} ai1流向 a i + 1 a_{i + 1} ai+1或者反过来。问最后 n n n个数的不同方案数。
题解
考虑将操作看成都是从 a i − 1 a_{i - 1} ai1流向 a i + 1 a_{i + 1} ai+1 a i a_i ai或者 − a i -a_i ai, 每次其实相当于从添加一个新的数 b i + 1 b _{i + 1} bi+1同时对 a i − 1 a_{i - 1} ai1修改产生新序列,所以 a i − 1 a_{i-1} ai1具备无后效性, d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i个数字结尾为 j j j的方案数,枚举值域转移即可。时间复杂度 O ( n 3 ) O(n^3) O(n3)

#include<bits/stdc++.h>using namespace std;
using ll = long long;
const int maxn = 303;
const int del = 300 * 300;ll dp[maxn][maxn * maxn * 2];
int a[maxn];
const int mod = 998244353;int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}dp[1][a[1] + del] = 1;dp[2][a[2] + del] = 1;for (int i = 2; i <= n - 1; ++i) {for (int j = -del; j <= del; ++j) {dp[i + 1][a[i + 1] - j + del] = (dp[i + 1][a[i + 1] - j + del] + dp[i][j + del]) % mod;dp[i + 1][a[i + 1] + j + del] = (dp[i + 1][a[i + 1] + j + del] + dp[i][j + del]) % mod;if (!j) {dp[i + 1][a[i + 1] + del] = (dp[i + 1][a[i + 1] + del] - dp[i][j + del] + mod) % mod;}}}ll ans = 0;for (int i = -del; i <= del; ++i) {ans = (ans + dp[n][i + del]) % mod;}cout << ans;return 0;
}

E. Game of the Yea

题意
A和B轮流 k k k次尝试击杀boss, A在第 a i a_i ai次击杀boss, B B B b i b_i bi次,问对于所有 i i i 1 1 1 n n n, 都是 A A A先击杀 b o s s boss boss的有哪些
题解
不难转化为 ⌈ a i k ⌉ ≤ ⌈ b i k ⌉ \lceil \frac{a_i}{k} \rceil \leq \lceil \frac{b_i}{k} \rceil kaikbi, 显然有个枚举 i i i做数论分块并求前缀和的方案,复杂度 O ( n n O(n\sqrt{n} O(nn 无法通过本题,考虑对于 a i ≤ b i a_i \leq b_i aibi, 该式子显然成立,则讨论 a i > b i a_i > b_i ai>bi的情况,其实就是在询问是否存在 x x x, 使得 b i ≤ k x < a i b_i \leq kx < a_i bikx<ai, 对这种情况做差分前缀和,枚举 k k k及其倍数为调和级数,可以在 n l n n nlnn nlnn复杂度通过此题

#include<bits/stdc++.h>using namespace std;
const int maxn = 2e5 + 5;
int a[maxn], b[maxn], d[maxn];
int main() {ios::sync_with_stdio(false);cin.tie(0);int n, t;cin >> t;while(t--) {vector<int> ans;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i], d[i] = 0;}for (int i = 1; i <= n; ++i) {cin >> b[i];}for (int i = 1; i <= n; ++i) {if (a[i] > b[i]) {d[b[i]]++;d[a[i]]--;}}for (int i = 1; i <= n; ++i) {d[i] += d[i - 1];}for (int k = 1; k <= n; ++k) {bool f = 1;for (int j = k; j <= n; j += k) {if (d[j]) {f = 0;break;}}if (f)ans.emplace_back(k);}cout << ans.size() << "\n";for (auto u : ans) {cout << u << " ";}cout << '\n';}return 0;
}

F. Double Sort II

题意
题解
首先是个非常套路的 t r i c k trick trick, 我们把 i − > p i i -> p_i i>pi转换成一张图,则发现图由多个环组成,每个操作相当于环上断开一个点成自环,并将剩余的链再次成环。考虑假如只有一张图,每个环只有一个点是不用拆的,答案等于 n − 环数 n - 环数 n环数。现在有多个环,我们希望两边不操作的点数尽量多。由于每个环只能选一个点不操作,所以只有某个点最后同时成为环 a a a和另一张图的环 b b b的代表时,才能不操作,考虑把环看成点,a相当于左部点,b为右部点,有相同元素的两个点相连,使用 d i n i c dinic dinic或者匈牙利求出二分图最大匹配即可,答案即为$n - 最大匹配数。输出方案的话,对于最大匹配的两个环任选一个代表点即可。时间复杂度 最大匹配数。输出方案的话,对于最大匹配的两个环任选一个代表点即可。时间复杂度 最大匹配数。输出方案的话,对于最大匹配的两个环任选一个代表点即可。时间复杂度O(n ^ 2 ) or O(n\sqrt{n})$

#include<bits/stdc++.h>using namespace std;
const int maxn = 3005;
int a[maxn], b[maxn], match[maxn << 1], tota, totb, bela[maxn], nxta[maxn], belb[maxn], nxtb[maxn];
bool vis[maxn << 1], va[maxn], vb[maxn];
int mp[maxn][maxn];vector<int> G[maxn];bool dfs(int x) {for (auto v : G[x]) {if (!vis[v]) {vis[v] = 1;if (!match[v] || dfs(match[v])) {match[v] = x;return 1;}}}return 0;
}void getcir(bool* v, int tot, int* bel, int i, int *nxt) {int x = i;while (!v[x]) {v[x] = 1;bel[x] = tot;x = nxt[x];}
}int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];nxta[i] = a[i];}for (int i = 1; i <= n; ++i) {cin >> b[i];nxtb[i] = b[i];}for (int i = 1; i <= n; ++i) {if (!va[i]) {getcir(va, ++tota, bela, i, nxta);}   if (!vb[i]) {getcir(vb, ++totb, belb, i, nxtb);}}for (int i = 1; i <= n; ++i) {if (mp[bela[i]][belb[i]])continue;mp[bela[i]][belb[i]] = i;G[bela[i]].emplace_back(belb[i]);}int ans = 0;for (int i = 1; i <= tota; ++i) {memset(vis, 0, sizeof(vis));if (dfs(i))ans++;}cout << n - ans << "\n";vector<int> p (n + 1, 0);for (int i = 1; i <= totb; ++i) {if (match[i]) {p[mp[match[i]][i]] = 1;}}for (int i = 1; i <= n; ++i) {if (!p[i]) {cout << i << ' ';}}return 0;
}

G. Weighed Tree Radius

题意
给定一颗 n n n个点,点权为 a i a_i ai的树,定义 w v ( u ) = d i s ( v , u ) + a u w_v(u) = dis(v, u) + a_u wv(u)=dis(v,u)+au, e ( v ) = m a x 1 ≤ u ≤ n w v ( u ) e(v) = max_{1\leq u \leq n}w_v(u) e(v)=max1unwv(u), 定义半径为 r = m i n ( e ( u ) ) r = min(e(u)) r=min(e(u))
题解
这种问题也可以看成是 t r i c k trick trick吧, 我们考虑往每个点挂个虚点,定义 w ′ ( u , v ) = d i s ( u , v ) + a ( u ) + a ( v ) , w ′ ( u , u ) = 2 ∗ a u w'(u,v) = dis(u,v) + a(u) + a(v), w'(u, u) = 2 * a_u w(u,v)=dis(u,v)+a(u)+a(v),w(u,u)=2au。 在这种树的直径上我们有很多优美的性质可以解决问题,显然对于原问题我们考虑其应该是与中点相关,所以我们考虑对于新树的直径的中点,容易证得在原树上必定存在一个点为直径的中点,使得 r = e ( m i d ) = ⌈ d 2 ⌉ r = e(mid) = \lceil\frac{d}{2}\rceil r=e(mid)=2d, 下证,首先

  • 假如中点在原树上,由于 d i s dis dis是连续的,所以显然满足。否则假如中点不在原树上,设 m i d mid mid u u u所在链上,我们考虑此时 e ( u ) = a ( u ) e(u) = a(u) e(u)=a(u) e ( u ) > d i s ( u , v ) + a ( v ) e(u) > dis(u, v) + a(v) e(u)>dis(u,v)+a(v), 而这时中点取 u u u则满足 d = e ( u ) = a ( u ) d = e(u) = a(u) d=e(u)=a(u), 这也是为什么我们要挂上2个虚点的原因。

  • 其次对于任意顶点 z z z来说 e ( z ) = m a x ( w z ( x ) , w z ( y ) ) e(z) = max(w_z(x), w_z(y)) e(z)=max(wz(x),wz(y)), 由于直径的性质,这很显然。所以显然直径上的中点所得的 e e e为最小值, e ( v ) m i n = ⌈ d 2 ⌉ e(v)_{min} = \lceil\frac{d}{2}\rceil e(v)min=2d

现在问题就是怎么维护树的直径及修改,对于同一颗树上的多个联通块的合并,其树的直径的端点仍然等于这两个连通块的直径端点4选2。所以现在这是一个naive的问题,树上随便定义一个顺序,直接用线段树暴力合并修改即可。使用 R M Q RMQ RMQ L C A LCA LCA时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)

#include<bits/stdc++.h>
#define ls p << 1
#define rs p << 1 | 1
#define lson p << 1, l, mid
#define rson p << 1 | 1, mid + 1, r 
using namespace std;
using ll = long long;
const int maxn = 2e5 + 5;
int n, a[maxn], dfn[maxn], d[maxn], st[maxn << 1][21], lg[maxn << 1], ti, m;
vector<int> G[maxn];
void dfs(int x, int f) {dfn[x] = ++ti;d[x] = d[f] + 1;st[ti][0] = x;for (auto v : G[x]) {if (v == f)continue;dfs(v, x);st[++ti][0] = x;}
}
void RMQ() {for (int i = 2; i <= ti; ++i)lg[i] = lg[i >> 1] + 1;for (int j = 1; j <= lg[ti]; ++j) {for (int i = 1; (i + (1 << j) - 1) <= ti; ++i) {int r = i + (1 << (j - 1));st[i][j] = d[st[i][j - 1]] < d[st[r][j - 1]] ? st[i][j - 1] : st[r][j - 1]; }}
}
int query(int l, int r) {if (l > r)swap(l, r);int k = lg[r - l + 1];return d[st[l][k]] < d[st[r - (1 << k) + 1][k]] ? st[l][k] : st[r - (1 << k) + 1][k];
}int LCA(int x, int y) {return query(dfn[x], dfn[y]);
}ll dis(int x, int y) {return d[x] + d[y] - 2 * d[LCA(x, y)];
}struct TreeDIA {int x, y;ll len;TreeDIA() { //默认构造x = y = len = 0;}TreeDIA(int _x, int _y) : x(_x), y(_y) {len = dis(x, y) + a[x] + a[y];}bool operator<(TreeDIA b) {return len < b.len;}};
TreeDIA merge(TreeDIA A, TreeDIA B) {TreeDIA p[] = {A, B, TreeDIA(A.x, B.x), TreeDIA(A.x, B.y), TreeDIA(A.y, B.x), TreeDIA(A.y, B.y)};return *max_element(p, p + 6);
}struct SegmentTree {TreeDIA dia[maxn << 2];void pushUp(int p) {dia[p] = merge(dia[ls], dia[rs]);}void update(int p, int l, int r, int x) {if (l == r) {dia[p] = TreeDIA(x, x);return;}int mid = l + r >> 1;if (x <= mid)update(lson, x);elseupdate(rson, x);pushUp(p);}void build(int p, int l, int r) {if (l == r) {dia[p] = TreeDIA(l, l);return;}int mid = l + r >> 1;build(lson);build(rson);pushUp(p);}
}tr;int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; ++i)cin >> a[i];for (int i = 1; i < n; ++i) {int u, v;cin >> u >> v;G[u].emplace_back(v);G[v].emplace_back(u);}dfs(1, 0);RMQ();tr.build(1, 1, n);cin >> m;for (int i = 1; i <= m; ++i) {int v, x;cin >> v >> x;a[v] = x;tr.update(1, 1, n, v);ll ans = max({(tr.dia[1].len + 1) / 2, (ll)a[tr.dia[1].x], (ll)a[tr.dia[1].y]});cout << ans << '\n';}return 0;
}

http://www.ppmy.cn/news/49495.html

相关文章

Spring MVC 接收 json 和返回 json (14)

目录 总入口 测试case 源码分析 1. 针对RequestBody的参数解析 2. 针对 ResponseBody 的返回值处理 总入口 通过上一篇Spring MVC 参数解析&#xff08;13&#xff09;_chen_yao_kerr的博客-CSDN博客的说明&#xff0c;相信大家对Sping MVC的参数解析有了一定的了解&…

人生是一个长期的均值回归

到了现在这个阶段&#xff0c;总想说点什么。 我一直觉得记录并收藏每个阶段的状态是一件很有意义且奇妙的事&#xff0c;尤其是多少年后还能清晰地回忆其当初的心境&#xff0c;联想到曾经所设立的一些目标以及为之做出的努力&#xff0c;这些人生经历的脉纹清晰而完整&#x…

itop-3568开发板驱动学习笔记(19)内核工作队列

《【北京迅为】itop-3568开发板驱动开发指南.pdf》 学习笔记 文章目录 工作队列简介共享工作队列工作结构体初始化 work_struct调度工作队列函数共享工作队列实验 自定义工作队列创建工作队列函数调度和取消调度工作队列刷新工作队列函数删除工作队列函数 内核延时工作队列延时…

Docker 网络

一、Docker 网络实现原理 Docker使用Linux桥接&#xff0c;在宿主机虚拟一个Docker容器网桥(docker0)&#xff0c;Docker启动一个容器时会根据Docker网桥的网段分配给容器一个IP地址&#xff0c;称为Container-IP&#xff0c;同时Docker网桥是每个容器的默认网关。因为在同一宿…

函数栈帧的创建和销毁【汇编语言理解】

&#x1f339;作者:云小逸 &#x1f4dd;个人主页:云小逸的主页 &#x1f4dd;Github:云小逸的Github &#x1f91f;motto:要敢于一个人默默的面对自己&#xff0c;强大自己才是核心。不要等到什么都没有了&#xff0c;才下定决心去做。种一颗树&#xff0c;最好的时间是十年前…

【场景生成与削减】基于蒙特卡洛法场景生成及启发式同步回带削减风电、光伏、负荷研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

参数与非参数检验:理解差异并正确使用

数据科学是一个快速发展的领域&#xff0c;它在很大程度上依赖于统计技术来分析和理解复杂的数据集。这个过程的一个关键部分是假设检验&#xff0c;它有助于确定从样本中获得的结果是否可以推广到总体。 在这篇文章中&#xff0c;我们将探讨参数与非参数检验之间的区别&#…

享元设计模式解读

目录 问题引进 展示网站项目需求 传统方案解决网站展现项目 传统方案解决网站展现项目-问题分析 享元模式基本介绍 基本介绍 享元模式的原理类图 对类图的说明 内部状态和外部状态 享元模式解决网站展现项目 应用实例要求 思路分析和图解(类图) 代码实现 享元模式…