目录
写在前面
比赛地址：https://codeforces.com/contest/1782。
这两天一个人在家自己糊弄饭吃，炒饭切上一整根腊肠实在是太爽了，比杀软大学的杀软小几把腊肠好上十百倍甚至九百倍。
A
先把底的点移动到四条边之一，再移动到顶上。
//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
//=============================================================
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
int dis(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
int w = read(), d = read(), h = read();
int a = read(), b = read(), f = read(), g = read();
int ans = dis(a, b, a, 0) + dis(f, g, a, 0);
ans = std::min(ans, dis(a, b, a, d) + dis(f, g, a, d));
ans = std::min(ans, dis(a, b, 0, b) + dis(f, g, 0, b));
ans = std::min(ans, dis(a, b, w, b) + dis(f, g, w, b));
printf("%d\n", ans + h);
}
return 0;
}
B
显然的结论是 \(a_i\) 相同的人肯定会同时去或者同时不去，先将人按照 \(a_i\) 分段，考虑前 \(k\) 段人能否同去即可。
//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
const int kN = 2e5 + 10;
//=============================================================
int n, a[kN], cnt[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
std::sort(a + 1, a + n + 1);
a[0] = -n;
int ans = 1;
for (int i = 1; i <= n; ++ i) {
if (a[i] == a[i - 1]) continue;
if (i - 1 > a[i - 1] && i - 1 < a[i]) ++ ans;
}
printf("%d\n", ans);
}
return 0;
}
C
\(T\) 组数据，每组数据给定一长度为 \(n\) 的仅由小写字母组成的字符串 \(s\)，可以将 \(s\) 中的任意字母改为其他任意字母，求使得 \(s\) 中每种字母出现次数相同的最小修改次数，同时构造一种修改后的字符串 \(s\) 的形态。
\(1\le T\le 10^4\)，\(1\le n\le 10^5\)，\(\sum n\le 10^5\)。
2S，512MB。
先预处理出 \(s\) 中每种字符出现的次数 \(\operatorname{cnt}\)，考虑枚举最后每种字母的出现次数 \(c\)，有 \(c | n\) 且 \(26 \times c\ge n\)，枚举 \(n\) 的约数即可，然后计算出最后的字母种类数 \(m\)。
容易发现最后的字母一定是 \(\operatorname{cnt}\) 最大的前 \(m\) 个字母（包括 \(\operatorname{cnt}=0\)）。考虑按照出现次数降序记录这些字母，并记录出现次数和位置。之后先将这些字母中出现次数大于 \(c\) 的多余部分改为出现次数较少的，然后将 \(\operatorname{cnt}\) 降序排序后第 \(m+1\sim 26\) 的字母改为上述字母中出现次数较少的即可。求得最小操作次数同时记录使操作次数最少的 \(c\)，按照上述规则即可构造。
但是好他妈难写，赛时 2h 写了依托答辩赛后以为前办妥答辩没错就只重构了后办妥但他妈的调了一上午发现前办妥也挂了我是超级答辩王。
//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
const int kN = 1e5 + 10;
//=============================================================
int n, ans, len, cnt[30];
char s[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
bool cmp1(int fir_, int sec_) {
return cnt[fir_] > cnt[sec_];
}
void Init() {
n = read(), ans = n;
scanf("%s", s + 1);
for (int i = 0; i < 26; ++ i) cnt[i] = 0;
for (int i = 1; i <= n; ++ i) cnt[s[i] - 'a'] ++;
}
void Solve(int length) {
int temp = 0, need = n / length, i = 0, j, cnt1[26];
for (int i = 0; i < 26; ++ i) cnt1[i] = cnt[i];
std::vector <int> ch;
for (int i = 0; i < 26; ++ i) ch.push_back(i);
std::sort(ch.begin(), ch.end(), cmp1);
for (i = 0, j = need - 1; i < j; ) {
int chi = ch[i], chj = ch[j];
if (cnt1[chi] == length) {
++ i;
continue;
}
if (cnt1[chi] < length) break;
if (cnt1[chi] - length > length - cnt1[chj]) {
temp += length - cnt1[chj];
cnt1[chi] -= length - cnt1[chj];
cnt1[chj] = length;
-- j;
} else {
temp += cnt1[chi] - length;
cnt1[chj] += cnt1[chi] - length;
cnt1[chi] = length;
++ i;
}
}
for (j = need; i < need && j < 26; ) {
int chi = ch[i], chj = ch[j];
if (cnt1[chi] == length) {
++ i;
continue;
}
if (cnt1[chj] == 0) {
++ j;
continue;
}
if (cnt1[chj] > length - cnt1[chi]) {
temp += length - cnt1[chi];
cnt1[chj] -= length - cnt1[chi];
cnt1[chi] = length;
++ i;
} else {
temp += cnt1[chj];
cnt1[chi] += cnt1[chj];
cnt1[chj] = 0;
++ j;
}
}
if (temp < ans) {
ans = temp;
len = length;
}
}
void construct(int len) {
int need = n / len, i = 0, j;
std::vector <int> ch, pos[26];
for (int i = 0; i < 26; ++ i) ch.push_back(i);
for (int i = 1; i <= n; ++ i) pos[s[i] - 'a'].push_back(i);
std::sort(ch.begin(), ch.end(), cmp1);
for (i = 0, j = need - 1; i < j; ) {
int chi = ch[i], chj = ch[j];
if (cnt[chi] == len) {
++ i;
continue;
}
if (cnt[chi] < len) break;
if (cnt[chi] - len > len - cnt[chj]) {
for (int k = 1; k <= len - cnt[chj]; ++ k) {
int p = pos[chi].back(); pos[chi].pop_back();
s[p] = chj + 'a';
}
cnt[chi] -= len - cnt[chj];
cnt[chj] = len;
-- j;
} else {
for (int k = 1; k <= cnt[chi] - len; ++ k) {
int p = pos[chi].back(); pos[chi].pop_back();
s[p] = chj + 'a';
}
cnt[chj] += cnt[chi] - len;
cnt[chi] = len;
++ i;
}
}
for (j = need; i < need && j < 26; ) {
int chi = ch[i], chj = ch[j];
if (cnt[chi] == len) {
++ i;
continue;
}
if (cnt[chj] == 0) {
++ j;
continue;
}
if (cnt[chj] > len - cnt[chi]) {
for (int k = 1; k <= len - cnt[chi]; ++ k) {
int p = pos[chj].back(); pos[chj].pop_back();
s[p] = chi + 'a';
}
cnt[chj] -= len - cnt[chi];
cnt[chi] = len;
++ i;
} else {
for (int k = 1; k <= cnt[chj]; ++ k) {
int p = pos[chj].back(); pos[chj].pop_back();
s[p] = chi + 'a';
}
cnt[chi] += cnt[chj];
cnt[chj] = 0;
++ j;
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
// freopen("2.txt", "w", stdout);
int T = read();
while (T --) {
Init();
for (int length = 1; length <= n; ++ length) {
if (n > 26 * length || n % length != 0) continue;
Solve(length);
}
printf("%d\n", ans);
if (ans == 0) {
printf("%s\n", s + 1);
continue;
}
construct(len);
printf("%s\n", s + 1);
}
return 0;
}
/*
1
6
appall
*/
D
写在最后
- 别急，想好再写。
- 油倒多了炒菜好腻歪。