¶ CCSP 2023
¶ 准备
原计划从 10 月 7 号开始做恢复性训练，然而赛前一段时间身体和精神都出了问题，导致基本没咋练。
提前买了抗体喷雾以防止在飞机上或者赛场里得新冠。
21 号用 C++ 打了一场 ABC 以重新适应 C++，避免在场上不小心写出 Rust 来。
23 号练了一下 2021 年全国赛比分区赛多的题，结果 T2 都拿不到 100 分 (这还是传统算法题)，心态很崩，觉得要寄了。于是调整心态为去旅游。
24 号出发去沈阳，结果闹钟没响，幸亏自己把自己吓醒了。为了赶时间花了 160 元打车去机场，而且手忙脚乱忘带 HHKB 键盘的 Mini USB 线了。本来计划到沈阳直接去报到再去旅店，结果因为手机快没电，只能先去旅店入住并充电。
然后饿了么下单买键盘线 (因为离得近的手机店都没有)，等键盘线的时间去小卖部买了一堆巧克力和饮料。之后报道，然后吃晚饭。
最后回旅店把一堆资料丢到了 U 盘里，包括我的个人代码模板 (C++ 和 Rust 都带了，因为有的东西只有 Rust 模板里面有，实在不行就当场翻译)，.vimrc，一套 LFS 软件包，一份 C++ 标准，以及若干架构的汇编手册。最后除了 .vimrc 和 C++ 标准以外都没用上。
晚上睡觉一开始忘了关窗户，后来被冰箱的压缩机吵醒半夜起来关电源 (反正冰箱里啥也没有)，总之睡眠质量很差。早上一边走去赛场一边听朝鲜人民军建军 75 周年音乐会以让自己清醒，最后听完金玉珠演唱的《爱国歌》进了赛场。
¶ 比赛
一进场发现选手机事笔记本，觉得自己买键盘线的决定非常正确。因为屏幕很小，直接打开了 GNOME 的大字号模式，并把鼠标指针调大。
因为临走忘了拷题目，下面的题意都是根据人脑记忆和 AC 代码复原的，可能有不准确之处。
¶ T1
开场先做 T1，结果 T1 就被卡了半天。
大概题意：给你 种物品，一些物品可以直接花 块钱买，另一些物品可以用其他物品合成 (合成不花钱)，保证物品的合成关系形成一个森林 (即合成一个节点对应的物品需要该节点所有儿子对应的物品)。在此基础上，有 对物品 表示可以用一个物品 交换一个物品 (每对只能换一次，不能反着换)；有 种礼包，第 种礼包可以花 块钱直接购买物品 各一个 (每个礼包只能买一次)。问凑齐物品 最少要多少钱。，。
首先如果没有礼包和交换就是送分题，但是这种情况有很多种写法，要想推广到有礼包和交换的情况就得想到和出题人心意相通的做法。这种做法是，用 delta[k] 表示物品 在 出现多少次，则我们可以直接树上 DFS (因为是森林所以要把每个树搜一遍再加起来)：
static int dfs(int u, int fa, int acc = 0)
{
acc += delta[u];
int ans = acc * cost[u];
for (int v: ch[u])
if (v != fa)
ans += dfs(v, u, acc);
return ans;
}
这样引入交换和礼包就很简单了：礼包就是 delta[j] -= 1; () 并且最后给答案加 ；交换就是 delta[u[i]] += 1; delta[v[i]] -= 1;。但是这样我们需要把上面的第 行改成：
acc = max(0, acc + delta[u]);
这是因为不能变卖或者拆分物品。这样枚举交换和礼包的所有方案，时间复杂度是 ，足以通过本题。
不知道这题把 或者 改大能不能做。
¶ T2
大概题意：给定 ，问有多少对集合 满足 ，， 且 。
保证 ，。
首先我们发现把 重新定义成
不会影响答案，而这个变换又使得 ，故 ，这样能把最后一个条件改写成
不妨设 (不满足就交换 和 以及 和 )。我们可以把 画一下，大概就是这样：
那么本题就变成在这个区域里面放标记，每个 格子最多放一个标记，每列最多放 个标记，要求放 个标记。从左往右递推是很麻烦的，但是从右往左就很简单：用 表示靠右 列，放 个标记的方案数，则
其中 是从右往左数第 列的长度，即 。边界是 。答案是 。这样做是 的，足以通过本题。
感觉这题放你电校赛都能过 人。另外如果我没记错的话这个变换后的问题 qkoqhh 在某届熊猫杯出过。
¶ T3
大概题意：给 个数 ，允许你选最多 个不重复的位置 ，把 减去 ，求
保证 ，。
首先一看这个 的形式就十成乃至九成是二分答案，这样就能把问题变成给定 求使得
的最小的 。
首先如果 是负的，那么我们就得把每个 都弄到 或者更小：先判断一下有没有 ，有就直接 ，没有就 。后面只考虑 。
先考虑一个简化的问题：如何判定是否不用修改就能满足条件。很明显我们可以递推一个
这样如果 就可以。
假如说在递推到某个 时，我们发现 ，就需要进行至少一次修改操作。假设修改位置 ，可以看出此时 减少的量是
这里我们能让 减少得越多越好。显然
随 的增加单调不减，所以选最大的一个还没选过的 是坠吼的。但是我们发现 一变所有以后 值都可能变，暴力维护会超时，就需要一个数据结构维护 。注意到 这个东西单调不减，可以用一个单调栈存放 ，其中 是一个 值， 是还没选过的使得 的 的个数。我们写的时候使得栈内元素保证 。
这样我们需要修改的时候，就从栈顶直接取一个 (栈空则直接 )，求出 的变化量 。模拟一下会发现维护 的方法是：我们准备把 压栈，按照单调栈的规则，先把 的元素 全弹出来，同时把 全都累加到 上。这样弄完以后如果 则直接丢弃，否则就把 压栈。
修改后 仍大于 就继续改，改到栈空还不行就 为 ，否则把改的次数加到 上。最后判一下 是否超过了题目限制。
这样做解决给定 求 的问题是 的，而二分的范围是 ，所以总的时间复杂度是 ，足以通过本题。
比赛的时候做到这个题时脑子不太清楚，导致 WA 了很多发，到午饭时间也没过，一边吃饭一边暴力对拍结果发现了至少 个错误。
¶ T5
做完了 T3，一开始想先做 T4 (因为我自己出题的时候出过 IEEE-754 浮点的二进制科学计数法输出和数组大小的计算)，但是写了一百行左右就发现坑太多。这时看了一下榜发现 T4 最高分才 分，而 T5 已经有不止一个人 了，赶紧跑路做 T5。
T5 是一个类似 NOIP 初赛 “补全程序” 的题。
¶ Subtask 1
要求你实现两个函数，出题人调用一个函数给你投喂数据，另一个函数问你要一个 watermark。
本题要求 watermark 必须严格递增，且必须是已经喂给你的数据的时间戳的最大值减去一个常数。数据的时间戳未必单调，这导致有时候我们不可能生成一个合法的 watermark，此时返回 std::nullopt。
直接模拟即可：
class TimeLagWatermarkGenerator {
private:
unsigned long long latest_record = 0;
unsigned long long latest_watermark = 0;
/* 题目已经提供的一大堆代码 */
}
void TimeLagWatermarkGenerator::onEvent(Event &event) {
auto t = std::stoull(event.getFieldValue("timestamp"));
latest_record = std::max(latest_record, t);
}
std::optional<Event> TimeLagWatermarkGenerator::onPeriodicEmit() {
if (latest_record) {
unsigned long long wm = latest_record - maxTimeLag;
if (wm > latest_watermark) {
latest_watermark = wm;
return Event(WATERMARK, wm);
}
}
return std::nullopt;
}
¶ Subtask 2
要求你合并两路输入中的 watermark。watermark 在系统中表示“数据的时间戳一定不超过最新收到的 watermark”。
设两路收到的最新 watermark 为 。一般地，我们只能知道数据的时间戳不会大于 。我们维护一下这个最小值，当它增加的时候就发出一个 watermark：
class TwoInputWindowOperator : public TwoInputWindowOperatorInterface {
private:
unsigned long long wm[2] = {0, 0}, wm_last = 0;
/* 题目已经提供的一大堆代码 */
}
void TwoInputWindowOperator::process_event(Event event, int channelId) {
auto tp = event.getType();
if (tp == WATERMARK) {
wm[channelId] = std::max(event.getTimeStamp(), wm[channelId]);
auto wm_early = std::min(wm[0], wm[1]);
if (wm_early > wm_last) {
// TODO: Subtask 3 not implemented
emit(Event(WATERMARK, wm_early));
wm_last = wm_early;
}
} else
abort(); // Subtask 3 and 4 not implemented
}
¶ Subtask 3
在 Subtask 2 的基础上，两路输入中除了 watermark 以外还会有数据 ，其中 是时间戳 (它不可能小于最新受到的 watermark)， 是 URL， 是访问 的次数。要求你在发出 watermark 前，处理所有时间戳小于该 watermark 的数据以得到若干时间窗口内 的访问次数总和。
本题时间窗口的信息由 window 对象提供，题面没给这个说明，需要读代码才能知道。
根据 watermark 的定义，对于窗口 我们必须在发出大于等于 的 watermark 时，才知道已经完全统计了该窗口中的访问情况。也就是说，在发出 这个 watermark 前，要发出所有 的窗口的统计信息。
题目给了一个 std::map<UnixTimeStamp, std::map<std::string, int>> windowState;，它的有序性和本题的要求一致，所以直接枚举并输出就行了：
auto tp = event.getType();
if (tp == WATERMARK) {
if (wm_early > wm_last) {
auto win = window.get_window_length();
while (!windowState.empty()
&& windowState.begin()->first + win <= wm_early) {
auto item = *windowState.begin();
windowState.erase(windowState.begin());
auto t = item.first;
for (auto [url, cnt]: item.second) {
static const std::vector<Field> fields = {
Field("timeWindow", DataType::ULL),
Field("url", DataType::String),
Field("totalNumber", DataType::Int),
};
std::vector<std::string> values = {
std::to_string(t),
url,
std::to_string(cnt),
};
emit(Event(fields, values));
}
}
emit(Event(WATERMARK, wm_early));
wm_last = wm_early;
}
} else if (tp == RECORD) {
auto timestamp = std::stoull(event.getFieldValue("timestamp"));
auto url = event.getFieldValue("url");
auto click_count = std::stoi(event.getFieldValue("clickNumber"));
auto start = window.get_window_start_unix_timestamp(timestamp);
windowState[start][url] += click_count;
} else
abort(); // Subtask 4 not implemented
¶ Subtask 4
在 Subtask 3 的基础上处理 checkpoint barrier 事件。当一路输入出现 checkpoint barrier 事件时，就阻塞该路输入，直到另一路输入出现编号相同的 checkpoint barrier。此时将状态信息保存到 checkpoint 文件中，以便服务器崩溃时恢复。保存结束后转发这个 checkpoint barrier (使得下游也生成 checkpoint 文件)，并且继续正常工作。
就很简单：
void TwoInputWindowOperator::process_event(Event event, int channelId) {
auto tp = event.getType();
if (tp == WATERMARK) {
/* ... */
} else if (tp == RECORD) {
/* ... */
} else if (tp == CHECKPOINTBARRIER) {
auto id = event.getCheckpointId();
if (id != chkpoint_id) {
resumeChannel(channelId ^ 1);
prohibitChannel(channelId);
chkpoint_id = id;
} else {
do_checkpoint(id);
emit(event);
resumeChannel(0);
resumeChannel(1);
}
} else
abort(); // WTF?
}
void TwoInputWindowOperator::do_checkpoint(int checkpointId) {
// 这三行是题目给的
std::string tmpDirectory = SystemConf::getInstance().tmpDirectory;
std::string tmpFileName = SystemConf::getInstance().tmpFileName;
std::string path = tmpDirectory + tmpFileName + "_" + std::to_string(checkpointId);
std::ofstream file(path);
for (auto &[t, stat]: windowState)
for (auto &[url, cnt]: stat)
file << t << ' ' << url << ' ' << cnt << '\n';
}
然后这题就做完了…… 早知道一开场就抢一血。
¶ T4
写了半天拿了 分，太菜了，等数据包放出来补。
¶ 后续
比完赛发现两瓶饮料都没打开于是直接送志愿者。
一边往回走一边总结了一下比赛：
- 首先个人评价题目难度 T2 < T1 < T5 < T3 < T4。
- 然后这场比赛其实对我是比较友好的，因为有多达 个传统算法题，还都是我会做的那种，而且没有我十分讨厌的内卷题。
- 如果个人状态好点且带了之前写的所有代码还能再冲高一些
- 再然后购买键盘线的决定十分正确。
- 最后看来在 10·25 这天听朝鲜音乐确实有加成。조선로동당 만세!
- 可惜比赛不许带耳机，希望以后能够改进一下 (比如允许把公发的耳机插比赛机器上)
然后大概估计自己就是 名上下，感觉要是第 名就成小丑了 (后来发现前 都能上台领奖但是只有前 能去颁奖晚宴)。回去以后接了个电话说是第⑨名。
¶ CNCC
- 26 号上午逛展馆并领了一堆资料，下午开颁奖会，晚上累得不行回去睡大觉。
- 教练前一天让我记得如果有集体奖就领一下，结果妹有 (悲)。
- 你电一金三银两铁，恭喜 szy 获得银牌第一名！
- 我 T2 T3 的做法和 std 都不一样，特别是 T2 出题人给的 std 特别复杂还要预处理阶乘和阶乘的逆什么的，但人家可以把 改大 (而我可以把 改大)。
- 27 号上午听《卫星互联网论坛》，下午听《量子算法》结果完全听不懂，晚上去颁奖晚宴胡吃乱喝，最后回旅店打了 IGVA 杯。
- 28 号早上补 IGVA 杯最后一题，上午摆烂，下午听《宇航智能信息系统》，晚上计划打 ABC。
¶ TODO
- 补 T4
- 报销
- 联系 CCF 把我的账号修一下 (我 480 的 CSP 证书还没下载呢)