ICPC 小白勇闯南京

SUNCHAOYI · 2024-11-02 20:02:34 · 生活·游记

第 49 届 ICPC 南京站游记

【2024.11.2-2024.11.3】

Day -2

下午翘课，VP 了 2022 年南京的区域赛。但是大家打得并不是非常认真，最后只过了 5 题。

开局签到，但是我读题加写题花了 20 分钟。看来还是我英语水平不够的问题，好在没有罚时。队友开了一道比签到稍微难点的题，但是卡在背包的正确性上了。我读题后提出先排序然后前部分背包后部分贪心的写法，然后大胆尝试，一发通过。

然后是数学题，直接丢给队友，他们俩讨论了一下，差不多在一个多小时的时候过了这道题。接着队友开图论，我开到了袋鼠题，发现是大模拟，和另一个队友讨论出了一个解法后就让他写了（于是我开始摆烂）。但是，接下去的一个小时，他还不容易写完以后发现过不了编译。看了好几遍以后发现是数组开到了 10^9，直接无语，又是一顿改。过样例！交！嗯，怎么 \texttt{RE on test2}？于是我们开始猜测是小数据挂还是空间炸，我果断否定空间炸。然而，在写了个数据生成器后发现单组数据运行全部正确，但组数一多直接炸裂，我丢真是 \texttt{vector} 的锅（于是队友开始给我上课--凡事不要过早下结论。我：啊吧啊吧，你倒是过了这题啊）。

接下来一直改啊改，用 swap() 和 shrink_to_fit() 但是还是 \texttt{RE on test2}，直接红温。期间我开了 \texttt{M} 题，发现是数据结构并想到了解法。异想天开用链表去维护，然后直接输出了一堆负数，再次红温...

就这样到比赛结束，写了 7 题，但是只过了 5 题……

Day -1

在 CEC 课上补题，把队友之前模拟写 \texttt{RE} 的代码直接全删了，然后按自己的想法写了一次，20 分钟直接过了。难不成是在课上写题有加成？

定了周五下午的飞机，但在晚上收到飞机延误到傍晚的消息，于是果断（免费）改签到了中午。哎，这不正合我意！

Day 0

趁着队友还没到，先去签到处附近薅羊毛！收获一把雨伞，一件纪念款衣服，一个背包，一个台灯，一个吹风机外加一个多功能闹钟。

快到中午，队友才（一点疲惫地）到酒店，然后直接去签到。同时，也奠定了下午热身赛要烂的节奏。下午赛前在学校里随便逛逛，看了大灰机。

两点进入到体育馆中，收获了属于自己的阔爱袋鼠！听裁判长发言，这次有中文题面好评！但旁边是北京大学，压力拉满差评！然后就开始热身赛了，发现是没用过的 \texttt{linux} 系统，捣鼓了很久才找到 \texttt{vscode}，又弄了很久终于可以输入输出……

热身赛全部都是历年的袋鼠题，胡出来四道题目，然后在写第三题时一直超时（然而在 CF 上也是这么写的却能过），于是直接摆烂不写。我们三人分别开始睡觉、玩手机、发呆……结束时发现不少队伍直接 AK，感觉明天要完（）。

【说句闲话，每人发了 25 元的餐券三张，却发现很难用完，第一次想要食堂的物价高一点……】

Day 2

比赛开始，不知怎的非常紧张。我先开了签到，但是以为是字符串哈希，但是我对字符串哈希并不是特别的熟悉，于是把题目丢给队友。致命的是，我在传达时对子序列和子串没有特别的强调，导致队友在写 \texttt{KMP}，而这一写就是半小时。等我恍然大悟的时候，和队友说了，于是开始修修补补，过样例交上去还挂了。还是我上去写了，最后在 1.5 小时才过。这时候我们其实完全的慌了，毫无节奏可言。

看 \texttt{B} 认为是一道动归，然后疯狂写转移表达式。看 \texttt{G} 又感觉像是动归，认为不会。另一个队友开 \texttt{J}，是简单贪心但是细节超多，不断缝缝补补然后一直过不了样例。我尝试了 \texttt{G}，想了同深度两点询问的做法，但是交上去 WA，发现链的情况直接退化到 n 次。然后想要找重心式询问，但发现链仍能被 hack。

队友写 \texttt{J} 然后一直调不对，直接打印换队友写 \texttt{B}。写了超级久最后被样例 4 卡了，直接发现是假做法。好不容易改过了 \texttt{J}，这时候已经 4 小时了。

我又想了一个每次询问直径两端的做法，但是在细节上并没有处理的很清楚，能不能在 \lfloor \log_2 n \rfloor 完成询问其实心里完全没底，还是上去敲了代码，但是有运行错误，到赛后也调出来。

于是，2 题结束我们第一次的 ICPC，并拿到了铁牌。

后记

总的来说，这是一次完全失败的比赛，我们有效做题的时间不超过 1.5 小时。非常奇怪，我们一上来连签到题都开始讨论。然后，由于我们口胡惯了，想不仔细，所以出现了多次题目想假，代码打补丁的情况，这是致命的。

还有就是比赛的节奏是尤其重要的，像上次网络赛我们打了 7 题，就是非常的顺，机上机下协调的都是非常好，几乎没有出现空机的情况，这也是为什么我们可以做出这么多题目的原因。

还有一周就是 CCPC 重庆站，赶紧趁着这周再练习调整一下，加油吧！

彩蛋

回去的时候在机场和队友玩 QQ 飞车，然后一人一局相互破纪录，简直逆天。

赛后补题

• \texttt{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]);
}

• \texttt{B}

感觉很 \texttt{Ad-hoc}。先将字符串中所有偶数的位置上的数字取反，问题就等价于为每次删去两个相邻且相同的字符。不难发现得到的串一定全部为 0 或 1，而每一次删除的数都是一个 0 一个 1，因此最优情况就是把 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