当前位置：首页 > news >正文

Educational Codeforces Round 169 (Rated for Div. 2)(A-D)

news 来源：原创 2024/9/20 18:29:49

题目链接

A

根据题意，需要新增一个点，使得该点到集合中每一个点的距离最近。
分情况讨论：

集合元素大于2个：一定不存在这样的点
集合元素等于2个（不能小于，题目范围给定最少2个）：当这两个元素之差大于1时，存在一点满足要求。该点的位置可以位于两点之间任意位置。

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
using namespace std;
using ll = long long;
void slove()
{int n; cin >> n;vector<int> a(n, 0);for(int i = 0; i < n; i++) cin >> a[i];if(n > 2) { cout << "NO" << endl; return; }if(abs(a[1] - a[0]) >= 2) { cout << "YES" << endl; return; }cout << "NO" << endl;
}  int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t; cin >> t;while(t--) slove();return 0;
}

B

对于两个人位于的区间重合情况分类讨论：

重合区间左右端点都在整个区间内部，应该将这个重合区间的所有门，包括边上两个门也关闭
重合区间左右端点有一边在整个区间边上，那么这个边上的门不需要关闭，比情况1少一个门
重合区间左右两个端点都在整个区间边上，等价于重合区间就是整个区间。那么两边的门都不需要关，比情况1少两个门。

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
using namespace std;
using ll = long long;
void slove()
{int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;if(r1 < l2 || l1 > r2) { cout << 1 << endl; return; }int l = max(l1, l2), r = min(r1, r2);int x = min(l1, l2), y = max(r1, r2);if(l > x && r < y) cout << r - l + 2 << endl;else if(l > x || r < y) cout << r - l + 1 << endl;else cout << r - l << endl;
}  int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t; cin >> t;while(t--) slove();return 0;
}

C

保证分数最大，a、b每次取最大值。对于b来说，可以提前改变数组，累加增加k。b每次取值在a之后，那么b只能依次取次大值，所以b需要改变数组的依次次大值，并且不能超过依次最大值，否则a就会取该值，会导致分数变大。

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
using namespace std;
using ll = long long;
void slove()
{int n, k; cin >> n >> k;vector<int> a(n + 1, 0);for(int i = 1; i <= n; i++) cin >> a[i];sort(a.begin() + 1, a.end(), greater<int>());int res = 0;for(int i = 1; i <= n; i++){if(i & 1) res += a[i];else{int add = min(k, a[i - 1] - a[i]);a[i] += add;k -= add;res -= a[i];}}cout << res << endl;
}  int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t; cin >> t;while(t--) slove();return 0;
}

D

城市 x，和城市 y，之间的最短路径为 | x - y |；一共四种颜色，有相同即可达；那么最多只会通过一个城市进行中转，这样才能保证路径最短。
证明：
为了不失一般性，设四种颜色分别为（a，b，c，d）；城市 x 的颜色为（a，b），城市 y 的颜色为（c，d）（当两个城市不能直达）。设两个中转城市 A、B，为了保证能够中转，需要 A 和 B 中的颜色应该包括 x 和 y 中的至少一个颜色，并且 A 和 B 需可直达。设路径为 x -- > A -- > B -- > y，那么 A 中至少有一个颜色和 x 相同，B 中至少有一个和 y 相同。不妨设有一个颜色相同。
A（a，b）or （a，c）；B（d，b） or （d， c）。观察发现不需要两个中转城市，通过一个中转城市即可达到目标城市。

设中转城市为 z。x -- > z -- > y。对于 z 的存在与否，位置，有下面四种情况：（设 x < y）

不需要中转，res = y - x
z 位于 x 和 y 之间， res = y - x
z 位于 x 之前，res = y - x + 2 * （x - z）
z 位于 y 之后，res = y - x + 2 * （z - y）

情况1和情况2的路径是最短的。

当 x 和 y 不可直达时，需要借助中转城市 z，z 的颜色情况可以通过 x 和 y 的颜色情况暴力枚举得出。
首先预处理，将每一种颜色的城市下标保存 map<int, vector<int>> 中，得到 z 的颜色情况之后；根据情况2、3、4，计算每种情况的路径，取最短。
对于情况3：越靠近 x ，路径越短
对于情况4：越靠近 y ，路径越短

如何判断 z 的位置？
对于城市 z 的颜色情况，可以得到该种颜色情况的所有城市下标，并且是升序的（在预处理阶段，是从左往右遍历）。存储在 vector 中，这些城市都是 z 的可能。
那么可以在 vector 中二分查找第一个大于等于 x 的位置（使用lower_bound)。当这个位置存在，且小于等于 y ，对应情况2。
查找第一个大于 y 的位置（upper_bound)，对于情况4
在情况2的基础上，假如 z 位置前还有小于 x 的元素，那么这个元素就是最靠近 x 的元素（左边靠近）

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
using namespace std;
using ll = long long;
const int N = 2e5 + 10, INF = 1e9;
string s[N];void slove()
{map<string, vector<int>> hs;int n, q; cin >> n >> q;for(int i = 1; i <= n; i++){cin >> s[i];hs[s[i]].push_back(i);  // 保证 vector 都为升序排列}while(q--){int x, y; cin >> x >> y;int res = INF;if(x > y) swap(x, y);  // 规定x < yfor(int i = 0; i < s[x].size(); i++){bool f = false;for(int j = 0; j < s[y].size(); j++){if(s[x][i] == s[y][j])  // 当 x 和 y 可直达，y - x 一定为最短；可提前结束{res = min(res, y - x);f = true;break;}string str;str += s[x][i];str += s[y][j];if(str[0] > str[1]) swap(str[0], str[1]);  // 根据题目给出的颜色组合情况，两个颜色是升序排列if(!hs.count(str)) continue; // 假如城市 z 的该种颜色组合不存在，可丢弃vector<int>& nums = hs[str];auto mid = lower_bound(nums.begin(), nums.end(), x);  // 当 z 位于 x 和 y 的中间if(mid != nums.end() && (*mid) <= y) res = min(res, y - x);auto pre = mid;auto suf = upper_bound(nums.begin(), nums.end(), y);if(pre != nums.begin()) { pre -- ; res = min(res, y - x + 2 * (x - (*pre))); }  // x 的左边第一个if(suf != nums.end()) res = min(res, y - x + 2 * ((*suf) - y)); // y 的右边第一个}if(f) break;}if(res == INF) res = -1;cout << res << endl;}}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t; cin >> t;while (t--) slove();return 0;
}