特性声明
本次继续尝试把部分题解放进代码的形式。
题意复述在代码里面，外面只会补充一些细节。
A - GamingForces
#include <bits/stdc++.h>
#define long long long
#define fori(n) for (long i = 0; i < n; i++)
#define forj(n) for (long j = 0; j < n; j++)
#define rofi(n) for (long i = n - 1; i >= 0; i--)
#define rofj(n) for (long j = n - 1; j >= 0; j--)
using namespace std;
/* REQUIRED */ const long N = 104;
// 有一堆血量不同的怪物
// 可以随意使用技能
// 1. 打两个怪一滴血
// 2. 直接杀掉一个怪
// 求最少使用技能的次数
// 直接贪心即可
// 存储数据
int t, n, h[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> t;
while (t--) {
cin >> n;
fori(n) cin >> h[i];
// 排序便于贪心
sort(h, h + n);
// 统计次数
int f = 0;
// 从大到小
rofi(n) {
// 血量大于一直接杀
if (h[i] > 1)
f++;
else {
// 否则剩下的全是一
// 一起处理然后弹出
f += (i + 2) / 2;
break;
}
}
cout << f << endl;
}
return 0;
}
要特别注意对血量为一的怪物的处理：
升序排序后从大到小扫，扫到第一个血量为一的怪物时编号为 i，那么 i + 1 是血量为一的怪物的总数，需要攻击的次数是向上取整的 (i + 1) / 2，也就是向下取整的 ((i - 1) + 1) / 2 + 1 = i / 2 + 1。
B - Stand-up Comedian
#include <bits/stdc++.h>
#define long long long
#define fori(n) for (long i = 0; i < n; i++)
#define forj(n) for (long j = 0; j < n; j++)
#define rofi(n) for (long i = n - 1; i >= 0; i--)
#define rofj(n) for (long j = n - 1; j >= 0; j--)
using namespace std;
/* REQUIRED */ const long N = 0;
// 对两个观众满意不满意分为四种笑话
// 每个人有情绪值
// 满意则加一，不满意则减一
// 负数之后离场，直接一切停止
// 要尽可能讲更久的笑话
// 先存好数据
int t, a[4];
// 首先让两个人都满意的笑话肯定先讲
// 那么有两种情况
// 1. 没有这样的笑话 // 总共只能讲一个，因为保证了至少一个笑话
// 2. 有这样的笑话 // 中间两种情况可以一比一抵消
// 抵消之后每讲一个笑话一定有个人恒定减一
// 判断笑话先讲完还是先有个人遗憾立场即可
// 验证样例：
// [0] 2 5 10 6 // 初始
// [2] 0 5 10 6 // 贪心
// [12] 0 0 5 6 // 抵消，每个人满意度都是 2
// [15] 0 0 5 3 // 剩下所有的都一定让某人不满意
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> t;
while (t--) {
fori(4) cin >> a[i];
if (a[0] == 0) {
cout << 1 << endl;
} else {
cout << a[0] + min(a[1], a[2]) * 2 +
min(abs(a[1] - a[2]) + a[3], a[0] + 1)
<< endl;
}
}
return 0;
}
C - Min Max Sort
#include <bits/stdc++.h>
#define long long long
#define fori(n) for (long i = 0; i < n; i++)
#define forj(n) for (long j = 0; j < n; j++)
#define rofi(n) for (long i = n - 1; i >= 0; i--)
#define rofj(n) for (long j = n - 1; j >= 0; j--)
using namespace std;
/* REQUIRD */ const long N = 2e5 + 4;
// 给定排列
int p[N], n;
// 一个操作有以下步骤
// 1. 移除两个数字
// 2. 从头插入两个数字最小值
// 3. 从尾插入两个数字最大值
// 找到最小的升序排序次数
// 感觉会有一些比较恶心的情况
// 比如 1 2 3 5 4 6 7 8
// 目前只能想到最坏的 4 次的解法
// 基本可以证明 4 次也是最优
// 样例中
// 两个 worst case
// 一个 best case
// 一个 average case
// 找到最大的 sorted 内核即可
// 例如 8 3 7 4 5 6 2 1，sorted 内核为 3 4 5 6
// 但是本题不可 n^2 暴力
// 但可以把每个数出现的位置存下来
// 比如 a[8] = 0，表示 8 在第一个位置
int a[N];
// 那么每次出现逆序的时候记录下来
// 偶数时，例如对于 n = 8
// a[5] < a[4] 则无 pairs = 1 内核
// a[4] a[6] 逆序则无 pairs = 2 内核……
// 结果为 f = i - 1 或 n + 1 - i
int f;
// 奇数时，例如对于 n = 9
// 结果也是一样的
// 那么记录题目数据，开始吧！
int t;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> t;
while (t--) {
cin >> n;
fori(n) {
cin >> p[i];
a[p[i]] = i;
}
f = 0;
fori(n) {
if (i == 0)
continue;
// 这里 i + 1 才是指向逆序对后者的指针
if (a[i + 1] < a[i]) {
int m = min(i, n - i);
f = max(f, m);
}
}
cout << f << endl;
}
return 0;
}
D - Fixed Prefix Permutations
前面往置换环的方向想，浪费了不少时间，其实核心就在
- 将排列视为变换
- 使用字典树存储逆排列便于查询前缀
#include <bits/stdc++.h>
#define long long long
#define fori(n) for (long i = 0; i < n; i++)
#define forj(n) for (long j = 0; j < n; j++)
#define rofi(n) for (long i = n - 1; i >= 0; i--)
#define rofj(n) for (long j = n - 1; j >= 0; j--)
using namespace std;
/* REQUIRED */ const long N = 5e4 + 4;
// 给定 n 个长度为 m 的排列
// 这里 a[i][j] 表示第 i 个排列第 j + 1 个数字
// 从 0 开始
int n, m, a[N][16];
// 美丽度 k 是最大的 1, 2, 3... 排列前缀长度
// 可以为 0
// 排列乘积 p x q = 先 p 后 q 复合
// 对于每个排列，找到选任意排列放后面相乘后最大的美丽值
// 挺难的……
// 先存个 t
int t;
// 看看样例吧！
// 还挺充实的
// 但是没有解释，那只能自己解释了
// 第一个样例
// [2 4 1 3] x [2 1 3 4] = [1 4 2 3], k = 1
// [1 2 4 3] x [1 2 4 3] = [1 2 3 4], k = 4
// [2 1 3 4] x [2 1 3 4] = [1 2 3 4], k = 4
// 对于每个排列，要在低于 n 的时间搞定
// 可能要依据排列的性质进行排序
// 字典序排序目前感觉没有大用
// 比较麻烦
// 尝试把排列视为置换
// 那么 3 以上的置换圈不能自己回到原位
// 第一个样例
// [1243] [1 2 34] [12 3 4]
// 21 是 1243 最大重合逆序，因此应用
// 目标从 1 开始似乎是一个好想法
// 如果修改成
// [1243] [3421]
// 那么这两个是最理想的配对
// 现在考虑多个置换圈的情况
// 如果修改成
// [1243 5 678] [34215 876]
// 那么最大匹配长度为 4
// 能否使用 Trie？
// 把每个排列处理成从下到上置换圈字符形式
// 0 代表分界
// 预处理 O(n)，匹配 O(m)
namespace trie {
int nex[N * 10][16], cnt;
int ver[N * 10][16];
// 记录当前版本
int v;
void reset() {
v++;
cnt = 0;
}
void insert(int *s, int l) {
int p = 0;
for (int i = 0; i < l; i++) {
int c = s[i];
// 如果没有，就添加结点
if (ver[p][c] < v) {
nex[p][c] = ++cnt;
ver[p][c] = ***ex[p][c];
}
}
int find(int *s, int l) {
int p = 0;
int f = 0;
for (int i = 0; i < l; i++) {
int c = s[i];
if (ver[p][c] < v)
return f;
p = nex[p][c];
f++;
}
return f;
}
} // namespace trie
// 置换圈断裂的话显然不能这么想
// 应该看目标
// 处理出一个逆排列 b
// 依然从 0 开始，便于匹配
int b[16];
// 然后对逆排列匹配即可
// qwq 亏我想这么久
// Trie 才是关键
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> t;
while (t--) {
cin >> n >> m;
trie::reset();
fori(n) {
forj(m) {
cin >> a[i][j];
b[a[i][j] - 1] = j + 1;
}
trie::insert(b, m);
}
fori(n) {
// 用 b 做临时数组
forj(m) b[j] = a[i][j];
cout << trie::find(b, m) << ' ';
}
cout << endl;
}
return 0;
}
京公网安备 11010502036488号