Codeforces Round 1002 (Div.2)
codeforces-round-1002(A-D)
A. Milya and Two Arrays#
题目描述#
给你两个长度为n的数组a和b，a,b中的每个元素都至少出现两次。你可以重新排列a，最后要使得ai+bi的不同种类大于等于3。
解题思路#
统计a和b的种类数cnt1,cnt2，因为长度为n且每个种类的数至少出现两次，所以a中每个数贡献的种类数就是出现次数，出现次数，min( 出现次数，cnt2)，只要cnt1∗cnt2>=3就行。赛时没想的很清楚写的cnt1+cnt2>=4，其实一样。
参考代码#
void solve() {
int n;
std::cin >> n;
std::set<int> a, b;
for (int i = 0; i < n; ++ i) {
int x;
std::cin >> x;
a.insert(x);
}
for (int i = 0; i < n; ++ i) {
int x;
std::cin >> x;
b.insert(x);
}
if (a.size() + b.size() >= 4) {
std::cout << "YES" << endl;
} else {
std::cout << "NO" << endl;
}
}B. Cost of the Array time limit per test1 second#
B. Cost of the Array time limit per test1 second ↗
题目描述#
给你一个长度为n数组a和一个偶数k。你要把a分成k份。然后把所有偶数份按顺序拼到一起，得到b，求可以得到的bi!=i的最小的i。
解题思路#
我们让所有的k−1份都只占一个位置，第二份占多个位置，看能不能不让1开头，如果有我们可以把前面的1都给第一份，那么答案就是1。否则就全部都是1，那么全部给第二个份，那么答案就是2。
注意要特判n==k的情况
参考代码#
void solve() {
int n, k;
std::cin >> n >> k;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
if (n == k) {
for (int i = 1, j = 1; i < n; i += 2, j ++ ) {
if (a[i] != j) {
std::cout << j << endl;
return;
}
}
std::cout << k / 2 + 1 << endl;
return;
} else {
for (int i = 1; i < n - (k - 2); ++ i) {
if (a[i] != 1) {
std::cout << 1 << endl;
return;
}
}
std::cout << 2 << endl;
}
}C. Customer Service#
题目描述#
给你n个长度为n的数组，你要给每一个数组截断一次，且所有数组截断的位置凑起来正好是一个排列。然后每个数组的值就是截断的后一部分的和。你要让所有数组和的mex最大。
解题思路#
记录每个数组的后缀和与后缀长度相等的位置，那么保留这一段位置可以得到一个数字。于是我们从小到大枚举mex只要有一个没有被操作过的数组可以贡献这个值，就可以继续操作，否则就是答案。然后考虑每个值由哪个数组贡献，应该让可以贡献的最大值最小的数组来贡献这个值。因为其他数组都可以贡献更大的值，应该留下来。
参考代码#
void solve() {
int n;
std::cin >> n;
std::vector a(n, std::vector<int>(n));
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < n; ++ j) {
std::cin >> a[i][j];
}
a[i].push_back(0);
std::reverse(a[i].begin(), a[i].end());
}
std::vector<std::set<std::pair<int, int> > > s(n + 1);
std::vector<int> b(n);
for (int i = 0; i < n; ++ i) {
i64 t = 0;
for (int j = 0; j <= n; ++ j) {
t += a[i][j];
if (j == n || t != j) {
b[i] = j;
break;
}
}
for (int j = 0; j < b[i]; ++ j) {
s[j].insert({b[i], i});
}
}
for (int i = 0; i <= n; ++ i) {
if (s[i].empty()) {
std::cout << i << endl;
return;
}
auto [_, x] = *s[i].begin();
s[i].erase(s[i].begin());
for (int j = 0; j < b[x]; ++ j) {
s[j].erase({b[x], x});
}
}
}D. Graph and Graph#
题目描述#
给你两个由n个顶点的图，你在图一和图二各有一个起点，你每次要在这两个图上移动，假设从图一移动到了u, 图二移动到了v，移动代价是|u−v|。你要进行无限次操作，求操作的最小代价。
解题思路#
显然我们让两个图都到一个相同的点u，使得有一个v在图一和图二上都和u有边。那么可以在这两个点上反复横跳，代价是0。否则代价是正无穷。 那么可以考虑最短路，dist[i][j]表示图一在i，图二在j时的最小代价。最后枚举每个i，看有没有一个j使得在两个图上都有边，然后取最小值即可。
参考代码#
void solve() {
int n, s1, s2;
std::cin >> n >> s1 >> s2;
-- s1, -- s2;
std::vector g1(n, std::vector<int>(n));
std::vector g2(n, std::vector<int>(n));
std::vector<std::vector<int> > adj1(n);
std::vector<std::vector<int> > adj2(n);
int m1, m2;
std::cin >> m1;
for (int i = 0; i < m1; ++ i) {
int u, v;
std::cin >> u >> v;
-- u, -- v;
g1[u][v] = g1[v][u] = 1;
adj1[u].push_back(v);
adj1[v].push_back(u);
}
std::cin >> m2;
for (int i = 0; i < m2; ++ i) {
int u, v;
std::cin >> u >> v;
-- u, -- v;
g2[u][v] = g2[v][u] = 1;
adj2[u].push_back(v);
adj2[v].push_back(u);
}
const int inf = 1e9;
std::vector dist(n, std::vector<int>(n, inf));
std::vector vis(n, std::vector<int>(n));
using A = std::array<int, 3>;
std::priority_queue<A, std::vector<A>, std::greater<A> > heap;
dist[s1][s2] = 0;
heap.push({0, s1, s2});
while (heap.size()) {
auto [_, x, y] = heap.top(); heap.pop();
if (vis[x][y]) {
continue;
}
for (auto & i : adj1[x]) {
for (auto & j : adj2[y]) {
if (dist[i][j] > dist[x][y] + std::abs(i - j)) {
dist[i][j] = dist[x][y] + std::abs(i - j);
if (!vis[i][j]) {
heap.push({dist[i][j], i, j});
}
}
}
}
}
int ans = inf;
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < n; ++ j) {
if (g1[i][j] && g2[i][j]) {
ans = std::min(ans, dist[i][i]);
}
}
}
if (ans == inf) {
ans = -1;
}
std::cout << ans << endl;
}