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

news/2024/2/21 8:36:09

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;我们将探讨参数与非参数检验之间的区别&#…

享元设计模式解读

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

蓝牙耳机什么品牌的音质好?300左右音质最好的蓝牙耳机推荐

随着蓝牙技术的发展&#xff0c;蓝牙耳机品牌也越来越多。要说什么品牌的音质好&#xff1f;首先还是要根据自己的预算出发。在此&#xff0c;我来给大家推荐几款300左右音质最好的蓝牙耳机&#xff0c;可以当个参考。 一、南卡小音舱Lite2蓝牙耳机 参考价&#xff1a;239 发…

深入探讨Linux驱动开发:Linux设备树

文章目录 一、设备树介绍二、设备树框架1.设备树框架2.节点基本格式3.节点部分属性简介 总结 一、设备树介绍 设备树&#xff08;Device Tree&#xff0c;简称 DT&#xff09;是一种在嵌入式系统中描述硬件设备的一种数据结构和编程语言。它用于将硬件设备的配置信息以树形结构…

不得不说的结构型模式-外观模式

目录 ​编辑 1. 什么是外观模式 1.1外观模式的结构&#xff1a; 2实际案例&#xff1a; 3下面是面试中关于装饰器模式的常见的问题&#xff1a; 3.1下面是问题的答案&#xff1a; 1. 什么是外观模式 Facade模式也叫外观模式, Facade模式为一组具有类似功能的类群&#xff…

ai智能改写文案-ai同义转换

文案创作是现代广告营销中不可或缺的一环&#xff0c;一个好的文案不仅可以提升产品的购买率&#xff0c;还可以实现品牌等方面的推广。但是&#xff0c;文案的创作需要耗费大量的时间和精力&#xff0c;如果能够利用智能化技术进行改写&#xff0c;不仅可以大大缩短文案创作时…

《Java8实战》第8章 Collection API 的增强功能

8.1 集合工厂 如果我想创建一个集合&#xff0c;之前的做法是先new一个list&#xff0c;然后再一个个的add&#xff0c;这样子有点繁琐。现在的方法可以这样&#xff0c;是使用 Arrays.asList()工厂方法&#xff1a;List<String> friends Arrays.asList("Raphael&…

4.23、TCP状态转换(为什么四次挥手)

4.23、TCP状态转换 1.TCP状态转换图2.为什么需要四次挥手&#xff0c;状态转换 1.TCP状态转换图 2.为什么需要四次挥手&#xff0c;状态转换 2MSL&#xff08;Maximum Segment Lifetime&#xff09; 主动断开连接的一方, 最后进入一个 TIME_WAIT状态, 这个状态会持续: 2msl ms…

微信小程序想给每个页面都加上分享功能,可以全局的加吗?

每个页面都设置onShareAppMessage方法&#xff0c;让每个页面都可以分享 然后发现了一个wx.onAppRoute wx.onAppRoute(() >{console.log(当前页面路由发生变化 触发该事件onShareAppMessage)const pages Taro.getCurrentPages() //获取加载的页面const view pages[pages…

Java:JDK对IPv4和IPv6处理介绍

以下以JDK8为例说明对IPv4和IPv6是如何处理的。 一、常用代码 一般情况下&#xff0c;使用如下代码可以获取到域名/主机名对应的多个IP&#xff0c;其中部分是IPv4的&#xff0c;部分是IPv6的&#xff1a; try {InetAddress[] addrs InetAddress.getAllByName(host);for (I…

2023年全国最新二级建造师精选真题及答案60

百分百题库提供二级建造师考试试题、二建考试预测题、二级建造师考试真题、二建证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 51.关于债的基本法律关系的说法&#xff0c;正确的是&#xff08;&#xff09;。 A.债是不特…

6 计时器(六)

6.7 TMI编码器接口 Encoder Interface 编码器接口 编码器接口可接收增量&#xff08;正交&#xff09;编码器的信号&#xff0c;根据编码器旋转产生的正交信号脉冲&#xff0c;自动控制CNT自增或自减&#xff0c;从而指示编码器的位置、旋转方向和旋转速度 每个高级定时器和通…

Linux下C/C++实现(网络流量分析-NTA)

网络流量分析&#xff08;NTA - Network Traffic Analysis) 就是捕捉网络中流动的数据包&#xff0c;并通过查看包内部数据以及进行相关的协议、流量、分析、统计等&#xff0c;协助发现网络运行过程中出现的问题。通过监控和分析网络环境中的流量&#xff0c;来判断流量是用在…

Linux下彻底解决mysql中文乱码

文章目录 Linux下彻底解决mysql中文乱码1.修改 MySQL 服务器的字符集为 UTF-8&#xff0c;可以在 my.cnf 配置文件中添加以下内容&#xff1a;2.使用时修改 MySQL 数据库和表的字符集为 UTF-8&#xff0c;可以使用以下命令&#xff1a;3.在建立数据库连接时&#xff0c;使用 UT…
最新文章