第 49 届 ICPC 南京站游记
【 2024.11.2 − 2024.11.3 2024.11.2-2024.11.3 2024.11.2−2024.11.3】
Day − 2 -2 −2
下午翘课，VP 了 2022 2022 2022 年南京的区域赛。但是大家打得并不是非常认真，最后只过了 5 5 5 题。
开局签到，但是我读题加写题花了 20 20 20 分钟。看来还是我英语水平不够的问题，好在没有罚时。队友开了一道比签到稍微难点的题，但是卡在背包的正确性上了。我读题后提出先排序然后前部分背包后部分贪心的写法，然后大胆尝试，一发通过。
然后是数学题，直接丢给队友，他们俩讨论了一下，差不多在一个多小时的时候过了这道题。接着队友开图论，我开到了袋鼠题，发现是大模拟，和另一个队友讨论出了一个解法后就让他写了（于是我开始摆烂）。但是，接下去的一个小时，他还不容易写完以后发现过不了编译。看了好几遍以后发现是数组开到了 1 0 9 10^9 109，直接无语，又是一顿改。过样例！交！嗯，怎么 RE on test2 \texttt{RE on test2} RE on test2？于是我们开始猜测是小数据挂还是空间炸，我果断否定空间炸。然而，在写了个数据生成器后发现单组数据运行全部正确，但组数一多直接炸裂，我丢真是 vector \texttt{vector} vector 的锅（于是队友开始给我上课–凡事不要过早下结论。我：啊吧啊吧，你倒是过了这题啊）。
接下来一直改啊改，用 swap() 和 shrink_to_fit() 但是还是
RE
on
test2
\texttt{RE on test2}
RE on test2，直接红温。期间我开了
M
\texttt{M}
M 题，发现是数据结构并想到了解法。异想天开用链表去维护，然后直接输出了一堆负数，再次红温…
就这样到比赛结束，写了 7 7 7 题，但是只过了 5 5 5 题……
Day − 1 -1 −1
在 CEC 课上补题，把队友之前模拟写 RE \texttt{RE} RE 的代码直接全删了，然后按自己的想法写了一次， 20 20 20 分钟直接过了。难不成是在课上写题有加成？
定了周五下午的飞机，但在晚上收到飞机延误到傍晚的消息，于是果断（免费）改签到了中午。哎，这不正合我意！
Day 0 0 0
12 : 50 12:50 12:50 的飞机是 13 : 15 13:15 13:15 飞的，问题不大。
看到今晚有 CF div2 \texttt{CF div2} CF div2，果断报名，希望别掉分。
晚上 CF \texttt{CF} CF， B \texttt{B} B 题看错题目，然后变成一道超难题，于是一直在死磕直到……一小时后突然发现是中位数而非平均数。
戏剧性的，每道题都有罚时，然后 D \texttt{D} D 赛后才对，于是降大分。（是不是从另一方面说明后天不再会看错题了）
Day 1 1 1
趁着队友还没到，先去签到处附近薅羊毛！收获一把雨伞，一件纪念款衣服，一个背包，一个台灯，一个吹风机外加一个多功能闹钟。
快到中午，队友才（一点疲惫地）到酒店，然后直接去签到。同时，也奠定了下午热身赛要烂的节奏。下午赛前在学校里随便逛逛，看了大灰机。
两点进入到体育馆中，收获了属于自己的阔爱袋鼠！听裁判长发言，这次有中文题面好评！但旁边是北京大学，压力拉满差评！然后就开始热身赛了，发现是没用过的 linux \texttt{linux} linux 系统，捣鼓了很久才找到 vscode \texttt{vscode} vscode，又弄了很久终于可以输入输出……
热身赛全部都是历年的袋鼠题，胡出来四道题目，然后在写第三题时一直超时（然而在 CF 上也是这么写的却能过），于是直接摆烂不写。我们三人分别开始睡觉、玩手机、发呆……结束时发现不少队伍直接 AK，感觉明天要完（）。
【说句闲话，每人发了 25 25 25 元的餐券三张，却发现很难用完，第一次想要食堂的物价高一点……】
Day 2 2 2
比赛开始，不知怎的非常紧张。我先开了签到，但是以为是字符串哈希，但是我对字符串哈希并不是特别的熟悉，于是把题目丢给队友。致命的是，我在传达时对子序列和子串没有特别的强调，导致队友在写 KMP \texttt{KMP} KMP，而这一写就是半小时。等我恍然大悟的时候，和队友说了，于是开始修修补补，过样例交上去还挂了。还是我上去写了，最后在 1.5 1.5 1.5 小时才过。这时候我们其实完全的慌了，毫无节奏可言。
看 B \texttt{B} B 认为是一道动归，然后疯狂写转移表达式。看 G \texttt{G} G 又感觉像是动归，认为不会。另一个队友开 J \texttt{J} J，是简单贪心但是细节超多，不断缝缝补补然后一直过不了样例。我尝试了 G \texttt{G} G，想了同深度两点询问的做法，但是交上去 WA，发现链的情况直接退化到 n n n 次。然后想要找重心式询问，但发现链仍能被 hack。
队友写 J \texttt{J} J 然后一直调不对，直接打印换队友写 B \texttt{B} B。写了超级久最后被样例 4 4 4 卡了，直接发现是假做法。好不容易改过了 J \texttt{J} J，这时候已经 4 4 4 小时了。
我又想了一个每次询问直径两端的做法，但是在细节上并没有处理的很清楚，能不能在 ⌊ log 2 n ⌋ \lfloor \log_2 n \rfloor ⌊log2n⌋ 完成询问其实心里完全没底，还是上去敲了代码，但是有运行错误，到赛后也调出来。
于是， 2 2 2 题结束我们第一次的 ICPC，并拿到了铁牌。
后记
总的来说，这是一次完全失败的比赛，我们有效做题的时间不超过 1.5 1.5 1.5 小时。非常奇怪，我们一上来连签到题都开始讨论。然后，由于我们口胡惯了，想不仔细，所以出现了多次题目想假，代码打补丁的情况，这是致命的。
还有就是比赛的节奏是尤其重要的，像上次网络赛我们打了 7 7 7 题，就是非常的顺，机上机下协调的都是非常好，几乎没有出现空机的情况，这也是为什么我们可以做出这么多题目的原因。
还有一周就是 CCPC 重庆站，赶紧趁着这周再练习调整一下，加油吧！
彩蛋
回去的时候在机场和队友玩 QQ 飞车，然后一人一局相互破纪录，简直逆天。
赛后补题
- K \texttt{K} K
其实就是简单贪心。显然的是每次在黑色块的地方切开，就像是多组数据。对于每个需要处理的区间，先从左往右扫，每次放纸条的地方显然是有红色的块最优。放完以后需要检验右端是否在范围内。若在范围之外，则需要从右往左再次扫一遍，进行纸条的调整。可以发现，即使纸条经过调整，数量仍然是不变的。最后，如果最左侧的纸条仍在范围内，则有解。核心代码如下：
void solve (int l,int r,int &w)
{
if (l > r) return ;
int cnt = 0,p = l;
while (w <= n && a[w] <= r)
{
paper[++cnt] = a[w];
p = a[w] + k;
while (w <= n && a[w] < p && a[w] <= r) ++w;
}
if (!cnt) return ;
paper[cnt] -= max (0,paper[cnt] + k - 1 - r);
int tmp = cnt;
while (tmp > 1) paper[tmp - 1] -= max (0,paper[tmp - 1] + k - paper[tmp]),--tmp;
if (paper[tmp] < l)
{
ok = 0;
return ;
}
for (int i = 1;i <= cnt;++i) ans.push_back (paper[i]);
}
- B \texttt{B} B
感觉很 Ad-hoc \texttt{Ad-hoc} Ad-hoc。先将字符串中所有偶数的位置上的数字取反，问题就等价于为每次删去两个相邻且相同的字符。不难发现得到的串一定全部为 0 0 0 或 1 1 1，而每一次删除的数都是一个 0 0 0 一个 1 1 1，因此最优情况就是把 2 2 2 尽可能给数量少的一方。最后的答案即为差值。但如果写动态规划，就会发现状态的转移非常的复杂，反正赛场上是没写出来。
核心代码如下：
for (int i = 1;i <= n;++i)
{
if (s[i] == '2') ++cnt[2];
else if (i % 2 == 0) ++cnt[(s[i] - '0') ^ 1];
else ++cnt[s[i] - '0'];
}
for (int i = 1;i <= cnt[2];++i)
{
if (cnt[0] < cnt[1]) ++cnt[0];
else ++cnt[1];
}
printf ("%d\n",abs (cnt[0] - cnt[1]));
类似题目 Folding Strip
标签：cnt,int,texttt,CF,ICPC,RE,小白,队友,勇闯 From： https://blog.csdn.net/scy923/article/details/144996280