Codeforces Round #823 (Div. 2)
A.Planets
题目大意
有$n$个星球,第$i$个星球的轨道是$a_i$,现在要摧毁所有星球
有两个机器可以摧毁星球:
第一个机器可以用代价$1$摧毁任意一个星球
第二个机器可以用代价$c$摧毁同一轨道上的所有星球
解题思路
如果一个轨道上的星球数大于$c$,用第二个机器摧毁完
否则,用第一个机器摧毁完这个轨道上的星球
具体代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 2e5 + 10;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q, c;
LL a[N], b[N];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
while (T--)
{
memset(b, 0, sizeof b);
std::map<int, int> S;
std::cin >> n >> c;
for (int i = 1; i <= n; ++i)
{
std::cin >> a[i];
++b[a[i]];
}
LL ans = 0;
for (int i = 0; i <= 100; ++i)
{
if (b[i] >= c)
ans += c;
else
ans += b[i];
}
std::cout << ans << '\n';
}
return 0;
}
B.Meeting on the Line
题目大意
$n$个人住在一个数轴上,第$i$个人住在$x_i$,他们现在想选一个点$x_0$来集合,由于每个人出门前都要打扮,第$i$个人的打扮时间是$t_i$,因此第$i$个人到达$x_0$所需要的时间为$t_i+|x_i-x_0|$,问$x_0$选在哪可以最小化最后那个到达的人所需要的时间
解题思路
可以实数二分时间,把每个人变成一个区间,但是精度容易写挂
正解是把每个人拆成两个人$x_i-t_i$和$x_i+t_i$,因为要最小化的是最后到达集合点的那个人的时间,所以可以这么拆
然后就简单了,取最大最小值的平均数即可
具体代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 2e5 + 10;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q;
int x[N], t[N];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
while (T--)
{
std::cin >> n;
for (int i = 1; i <= n; ++i)
std::cin >> x[i];
for (int i = 1; i <= n; ++i)
std::cin >> t[i];
std::vector<int> p;
for (int i = 1; i <= n; ++i)
{
p.push_back(x[i] + t[i]);
p.push_back(x[i] - t[i]);
}
int minx = p[0], maxx = p[0];
for (auto i : p)
{
minx = std::min(minx, i);
maxx = std::max(maxx, i);
}
int sum = minx + maxx;
std::cout << sum / 2;
if (sum & 1)
std::cout << ".5";
std::cout << '\n';
}
return 0;
}
C.Minimum Notation
题目大意
有一个字符串由数字$0$到$9$组成,可执行以下操作任意次:
删去下标$i$上的数字$d$,然后插入$min(d+1,9)$到任意位置
问能得到的最小字典序的串是什么
解题思路
最小字典序,那么又是贪心套路题
感觉比$B$还简单些
具体代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 20;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q;
LL fre[M];
std::string str;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
while (T--)
{
memset(fre, 0, sizeof fre);
std::cin >> str;
n = str.size();
str = "?" + str;
for (int i = 1; i <= n; ++i)
{
if (str[i] - '0' + 1 == 10)
++fre[9];
else
++fre[str[i] - '0' + 1];
}
LL np = 1;
for (int i = 0; i <= 8; ++i)
for (int j = np; j <= n; ++j)
if (str[j] - '0' - i == 0)
np = j, --fre[i + 1], ++fre[i];
for (int i = 0; i <= 9; ++i)
for (int j = 1; j <= fre[i]; ++j)
std::cout << i;
std::cout << '\n';
}
return 0;
}
D.Prefixes and Suffixes
题目大意
给定两个长度为$n$的字符串$s_1$和$s_2$,可执行以下操作任意次:
选定一个$k$,$1\leq k\leq n$,交换长度为$k$的$s_1$的前缀与$s_2$的后缀
问能否使$s_1=s_2$
解题思路
(我习惯让两个字符串的下标从$1$开始)
注意$s_1[i]$和$s_2[n-i+1]$不管怎么换都不在同一个串里
而且它们的位置永远对称
那么统计无序对$(s_1[i],s2[n-i+1])$(两个字母不相等)的数量,必须是偶数
对于两个字母相等的情况,如果有奇数次这个情况,多出来的一组放中间,那么要求$n$是奇数
具体代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 2e5 + 10;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q;
std::string a, b;
int f[M][M];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
while (T--)
{
memset(f, 0, sizeof f);
std::cin >> n;
std::cin >> a >> b;
a = "?" + a, b = "?" + b;
for (int i = 1; i <= n; ++i)
++f[std::min(a[i] - 'a' + 1, b[n - i + 1] - 'a' + 1)][std::max(a[i] - 'a' + 1, b[n - i + 1] - 'a' + 1)];
/*
for (int i = 1; i <= 26; ++i)
{
for (int j = 1; j <= 26; ++j)
std::cout << f[i][j] << ' ';
std::cout << '\n';
}
*/
// 1.
bool impossible = false;
for (int i = 1; i <= 25; ++i)
for (int j = i + 1; j <= 26; ++j)
if (f[i][j] & 1) //矩阵右上
impossible = true;
if (impossible)
{
std::cout << "NO" << '\n';
continue;
}
// 2.
LL tmp = 0;
for (int i = 1; i <= 26; ++i)
if (f[i][i] & 1) //对角线
++tmp;
if ((n & 1) && tmp >= 2)
std::cout << "NO" << '\n';
else if ((n % 2 == 0) && tmp)
std::cout << "NO" << '\n';
else
std::cout << "YES" << '\n';
}
return 0;
}
#### 附B的二分代码,方便自己收藏大佬的文章学习