A . B . C . D
Codeforces Round #823 (Div. 2)
A. Planets - 签到
题意
题意是一些卫星在一些轨道上，操作1花费1摧毁一个卫星，操作2花费\(y\)摧毁一个轨道上的所有卫星，问摧毁所有卫星最少花费多少。
分析
对于一个轨道上的卫星，若个数\(x\)超过了\(y\)则花费\(x*1>y\)，则用操作2更优，反之操作1。
AC 代码
void solve() {
int n, c;
cin >> n >> c;
map<int,int> mp;
for(int i = 1;i <= n; i ++) {
int x;
cin >> x;
mp[x] ++;
}
int res = 0;
for(auto v : mp) {
if(v.second > c) res += c;
else res += v.second;
}
cout << res << '\n';
}
B. Meeting on the Line - 二分
题意
居民住在数轴上，每个居民住在\(X_i\)，他们要在\(X_0\)处聚会，每个人要打扮\(T_i\)时间， 每个居民到聚会处花费\(|X_i - X_0|\)时间，问在哪聚会，可以使用时最少（不是所有用时之和）。
分析
结果是求最小的时间的位置，那么可以考虑如何求出最小的时间，如果时间无限大，则可以聚会，同时当时间小于某个值的时候，无法聚会，满足单调性，可以使用二分来求解，具体操作是，二分时间\(T\)，定义当前可以到达的区间\([L, R]\), 对于每个居民\(X\), 都可以求出\(X\)在\(T\)时间内可以走到的区间范围，不停的归并区间，考虑每个居民，若所以居民都可以走到，就更新答案，继续二分时间\(T\)，直到最小的时间。
注意\(eps\)别开太小，会\(T\)。
AC 代码
const int N = 100010;
double t[N], a[N], eps = 1e-6, ans;
int n;
bool calc(double x) {
double l = -1e18, r = 1e18;
for(int i = 1;i <= n;i ++) {
if(x <= t[i]) return false;
else {
double y = x;
y -= t[i];
double L = a[i] - y, R = a[i] + y;
if(r < L || l > R) return false;
l = max(l, L);
r = min(r, R);
if(l - eps > r) return false;
}
}
ans = l;
return true;
}
void solve() {
cin >> n;
for(int i = 1;i <= n;i ++) cin >> a[i];
for(int i = 1;i <= n;i ++) cin >> t[i];
double l = 0.0, r = 1e9;
while(l + eps < r) {
double mid = (l + r) / 2;
if(calc(mid)) r = mid; else l = mid;
}
printf("%.12f\n", ans);
}
C. Minimum Notation - 贪心
题意
给定一个字符串只有0-9，每一次可以选择一个字符\(x\)删除并将\(min(x+1,9)\)放到末尾，问若干次操作后可以得到的最小的字符串是多少。
做法
从尾开始遍历，定义一个当前最小的字符\(mn\)，当枚举的\(x\)比\(mn\)大时，就将\(min(x+1,'9')\)加入末尾，不断更新，得到最小的字符串。对于这一做法的正确性，首先，小的数一定尽量在前，这步的实现就是将小数之前的数丢到末尾，比如22221一定小于13333，要保证的就是小的数尽量在前，故，从尾考虑保证了将所有的小数提到最前，同时，通过合理的顺序，最后可以得到一个非降序列。
AC 代码
void solve() {
string s;
cin >> s;
char mn = '9';
for(int i = s.size() - 1; i >= 0; i --) {
mn = min(s[i], mn);
if(s[i] > mn) s[i] = min(char(s[i] + 1), '9');
}
sort(s.begin(), s.end());
cout << s << '\n';
}
D. Prefixes and Suffixes - Math
题意
给定两个字符串\(a，b\), 和任意次操作：将\(a\)的前缀和\(b\)的后缀交换，问最终是否可以将\(a, b\)变成同一个字符串。
分析
交换前缀和后缀的操作使，两串的下标具有对应关系，即：当\(a_i\)在\(b\)串中的位置确定，则与\(a_i\)对应的\(b_j(pair)\)在\(a\)串中的位置也随之确定，具体的关系为\(b_x → a_{n-x+1}\)(下标从1开始)，即：当\(a_i\)在\(b\)中的最终位置为\(x\)，对应的\(b_j\)在\(a\)中的位置在\(n-x+1\)，同时\(i\)和\(j\)满足\(i+j=n+1\)，就是头尾对应。
在这个基础上，现在只需要统计出每种对(\(pair\))的个数，元素相同的\(pair(same)\)以及元素不同的\(pair(no)\)， 首先不同元素的对一定不能是奇数，其次当\(n\)为偶数时，相同元素对必须是偶数，不同元素对必须为0，\(n\)为奇数时，相同元素对数不能超过1。
AC 代码
int t[30][30];
int cnt[30];
void solve() {
memset(t, 0, sizeof t);
memset(cnt, 0, sizeof cnt);
int n; cin >> n;
string a, b; cin >> a >> b;
a = "@" + a;
b = "@" + b;
int same = 0;
bool no = true;
for(int i = 1; i <= n;i ++) if(a[i] == b[n - i + 1]) cnt[a[i] - 'a'] ++; else {
int x = min(a[i] - 'a', b[n - i + 1] - 'a');
int y = max(a[i] - 'a', b[n - i + 1] - 'a');
t[x][y] ++;
}
for(int i = 0; i <= 25; i ++) if(cnt[i]&1) { same ++;}
for(int i = 0; i <= 25; i ++) for(int j = 0;j <= 25; j ++) if(t[i][j]&1) { no = false; break;}
if((n % 2 == 0 && same ) || (n % 2 && same > 1) || !no) cout << "NO\n";
else cout << "YES\n";
}