Codeforces Round #812 (Div. 2)
A.Traveling Salesman Problem
题目大意
有一些在$x$轴,$y$轴上的点,现要求你从原点出发经过所有点并最后返回原点,求最小步数
解题思路
签到题
具体代码
#include <bits/stdc++.h>
int main()
{
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
int T;
std::cin >> T;
while (T--)
{
int n;
std::cin >> n;
int l = 0, r = 0, u = 0, d = 0;
while (n--)
{
int x, y;
std::cin >> x >> y;
if (x == 0 && y > 0)
u = std::max(u, y);
else if (x == 0 && y < 0)
d = std::max(d, -y);
else if (y == 0 && x > 0)
r = std::max(r, x);
else if (y == 0 && x < 0)
l = std::max(l, -x);
}
std::cout << 2 * (u + d + r + l) << '\n';
}
return 0;
}
B.Optimal Reduction
题目大意
给定一个正整数数组$a$,你可进行无限次操作,每次选择一段连续区间使其中所有数减一
定义$f(a)$为将$a$中所有元素变为零的最少操作数
对于$a$的任意排列$b$,判断是否有$f(a)\leq f(b)$,有则输出$YES$
解题思路
在任意排列中,把数组按升序或降序排序得到的排列$b$显然有最小的$f(b)$
但也可以发现样例给的$2,3,5,4$也是$YES$
容易想到$2,3,5,4,6$就不行了,因为$4$比$5$和$6$先到$0$,阻断了$5$和$6$继续变零
因此判断原数组$a$是否是单峰的即可
第一眼因为给的样例,想的是判断是否有一个数的左右两边都有比它大的数,所以写了个单调栈
其实可以写的简单点
具体代码
#include <bits/stdc++.h>
const int N = 1e5 + 10;
int a[N];
int s[N]; //单调栈
int l[N], r[N]; // l[i]存a[i]左侧第一个比它大的数,不存在就是-1,r[i]同理
int n;
int main()
{
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
int T;
std::cin >> T;
while (T--)
{
std::cin >> n;
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
memset(s, 0, sizeof s);
int tt = 0;
for (int i = 1; i <= n; ++i)
{
while (tt && s[tt] <= a[i])
--tt;
if (tt)
l[i] = s[tt];
else
l[i] = -1;
s[++tt] = a[i];
}
memset(s, 0, sizeof s);
tt = 0;
for (int i = n; i >= 1; --i)
{
while (tt && s[tt] <= a[i])
--tt;
if (tt)
r[i] = s[tt];
else
r[i] = -1;
s[++tt] = a[i];
}
/*
for (int i = 1; i <= n; i++)
std::cout << i << ": " << l[i] << ' ' << r[i] << '\n';
*/
bool flag = true;
for (int i = 1; i <= n; i++)
if (l[i] != -1 && r[i] != -1) //不是单峰就不行
{
flag = false;
break;
}
if (flag)
std::cout << "YES\n";
else
std::cout << "NO\n";
}
return 0;
}
C.Build Permutation
题目大意
构造一个$0$到$n-1$的排列$p$,使得$p_i+i$是完全平方数
解题思路
根据给的样例其实就能猜这些完全平方数是块状递增的
先给出做法:
现考虑构造一个$0$到$12$的满足条件的排列,
黑色的是下标,蓝色的是要填入的数
先找到不小于$12$的最小的完全平方数,是$16$,那么在$12$填入$16-12=4$
相应的,在$4$处填入$12$,那么一个块就构造好了
再往前重复,构造这些块,就得到了答案
再给出证明:
我们的做法是对于块的每个右端点$r=x$,找到一个$a^2,(a-1)^2 < x\leq a^2$,让$l=a^2-x$作为左端点
那么只要这样做得到的$l\leq r$恒成立,就说明我们构造的块都一定存在
证明$l\leq r$如下:
具体代码
#include <bits/stdc++.h>
const int N = 1e5 + 10;
int n;
int ans[N];
int square[N];
int get(int x) //二分得到不小于x的最小的完全平方数
{
int l = 0, r = 1000;
while (l < r)
{
int mid = l + r >> 1;
if (square[mid] >= x)
r = mid;
else
l = mid + 1;
}
return square[l];
}
void fill(int r)
{
if (r < 0)
return;
int t = get(r);
int l = t - r;
fill(l - 1);
for (int i = l; i <= r; ++i)
ans[i] = t - i;
}
int main()
{
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
for (int i = 1; i <= 1000; ++i)
square[i] = i * i;
int T;
std::cin >> T;
while (T--)
{
std::cin >> n;
fill(n - 1);
for (int i = 0; i < n; ++i)
std::cout << ans[i] << ' ';
std::cout << '\n';
}
return 0;
}
D.Tournament Countdown
题目大意
交互题,有一个$2^n$个人参加的比赛,这个比赛已经结束了
要求在$\frac{2}{3}\times 2^n$次询问内问出谁是冠军
每次询问能知道两个人谁的获胜次数多
解题思路
每四个人一组,两次询问,问出这四个人里谁晋级了
等比数列求和可以知道这样是不会超过询问次数限制的
$(\frac{1}{2}+\frac{1}{8}+\cdots)\times 2^n$
具体代码
#include <bits/stdc++.h>
int ask(int x, int y)
{
std::cout << "? " << x << " " << y << std::endl;
int res;
std::cin >> res;
return res;
}
int main()
{
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
int T;
std::cin >> T;
while (T--)
{
int n;
std::cin >> n;
n = 1 << n;
std::vector<int> q;
for (int i = 1; i <= n; ++i)
q.push_back(i);
while (q.size() > 1)
{
std::vector<int> t;
if (q.size() == 2)
{
int res = ask(q[0], q[1]);
if (res == 1)
t.push_back(q[0]);
else
t.push_back(q[1]);
}
else
{
for (int i = 0; i < q.size(); i += 4)
{
int res1 = ask(q[i], q[i + 2]);
if (res1 == 0)
{
int res2 = ask(q[i + 1], q[i + 3]);
if (res2 == 1)
t.push_back(q[i + 1]);
else
t.push_back(q[i + 3]);
}
else if (res1 == 1)
{
int res2 = ask(q[i], q[i + 3]);
if (res2 == 1)
t.push_back(q[i]);
else
t.push_back(q[i + 3]);
}
else
{
int res2 = ask(q[i + 1], q[i + 2]);
if (res2 == 1)
t.push_back(q[i + 1]);
else
t.push_back(q[i + 2]);
}
}
}
q = t;
}
std::cout << "! " << q[0] << std::endl;
}
return 0;
}
E.Cross Swapping
题目大意
给定一个矩阵$g$,每次操作可以选择一个$k$进行$move$
void move(int k)
{
for (int i = 1; i <= n; ++i)
std::swap(g[i][k], g[k][i]);
}
问操作能得到的最小字典序的矩阵是什么
解题思路
最小字典序,那么多半是要贪心了
根据矩阵字典序的定义,依次考虑矩阵主对角线上方的这些元素
可以发现对于一个元素$g[i][j]$,当$k=i$或$k=j$时,都会交换$g[i][j]$
因此若想交换$g[i][j]$和$g[j][i]$,$i$和$j$只能选一个
若不想交换$g[i][j]$和$g[j][i]$,$i$和$j$要么都选要么都不选
想到这里其实可以发现就是一道带权并查集或者扩展域并查集维护关系的题了
不是很懂并查集维护关系的话或许可以点这里
具体代码
#include <bits/stdc++.h>
const int N = 1010;
int p[N * 2];
int g[N][N];
int n;
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
void move(int k)
{
for (int i = 1; i <= n; ++i)
std::swap(g[i][k], g[k][i]);
}
int main()
{
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
int T;
std::cin >> T;
while (T--)
{
std::cin >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
std::cin >> g[i][j];
for (int i = 1; i < N * 2; ++i)
p[i] = i;
for (int i = 1; i <= n; ++i)
{
for (int j = i + 1; j <= n; ++j)
{
if (g[i][j] > g[j][i]) //根据贪心,应该是尽量换
{
if (find(i) == find(j)) //发现i和j已经是要么都选要么都不选的关系,只能作罢
continue;
p[find(i)] = find(j + N);
p[find(i + N)] = find(j);
}
else if (g[i][j] < g[j][i]) //根据贪心,应该是尽量不换
{
if (find(i + N) == find(j)) //发现i和j已经是必须选一个的关系,只能作罢
continue;
p[find(i)] = find(j);
p[find(i + N)] = find(j + N);
}
}
}
std::set<int> S;
for (int i = 1; i <= n; ++i)
if (find(i) == i) //找出所有代表元素
S.insert(i);
for (int i = 1; i <= n; ++i)
if (S.count(find(i)))
move(i);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
std::cout << g[i][j] << ' ';
std::cout << '\n';
}
}
return 0;
}