====== 简况 ====== [[https://codeforces.com/gym/101177|比赛链接]] AC 9题，Rank 21th ====== 总结与反思 ====== ===== cmx ===== 这次还是犯了太急躁的毛病，没有想完全就直接上手了，结果发现问题重重。以后切记耐心。 ===== lpy ===== 以前鸽掉了$FFT$匹配字符串算法,导致C题卡在预处理上 ===== xsy ===== 读题水平还需要大力提升，一个模拟题怎么就能看这么久，大力贡献罚时。 ====== 题解 ====== ===== A.Anticlockwise Motion ===== **题意:** 有一个很大的螺旋矩阵，给出两个数值，求他们在矩阵中的坐标的曼哈顿距离。 **题解:** 可以先暴力枚举找到它在第几圈，然后找它在下边还是右边还是上边还是左边。 by MountVoom ===== B.Balloon Warehouse ===== **题意:** 最开始有无限个0号气球，给出$n$个操作，每个操作是在所有$x$号气球后面插入一个$y$号气球，最后询问$[l, r)$这一段的气球编号。 其中$ l < r \leq 10^6, r - l \leq 10^5$ **题解:** 如果当前这个$x$号气球是在第$i$个操作加入的，考虑插入到它后面的气球。 可以发现是第$i$个操作之后的在$x$后插入的气球的倒序排列。 也就是说我们可以很容易的找到最终序列中，当前气球下一个位置的气球是什么，只需要倒序枚举插入在它后面的气球即可，用递归容易实现。 因为每次递归一定能找到一个最终序列中的气球，所以复杂度为$O(r)$，如果最终长度不够$r$，直接不断复制即可。 by MountVoom ===== C.Crazy Rotations ===== ===== D.Dendroctonus ===== 也是不算很难的一道题，需要一些几何想象，但是一开始想法不完全就开打了。绕了很大弯路TAT。另外审题要仔细！没有注意到题面对于圆形的边界的描述。 其实考虑套住的圆形一个逐步放大和调整的过程，这个圆一般情况下调整过后会够到三个点（例如一般可以先缩小到触碰一个红点，再沿着这条半径反向移动圆心缩小到触碰另一个红点，再把圆心沿着红点中垂线平移，直到触碰一个蓝点，也有其他变化方法）。也就是说我们挑选不共线的三个点来做外接圆就可以了。特殊情况下，比如所有点共线的情况，可以变成以两个点为直径作圆。$n=1$特殊讨论下即可。 三点外接代码见个人页面。 ===== E.Election Frenzy ===== **题意:** 需要给一张无向图黑白染色，使得每个点和他相连的点中既要有黑点也要有白点。 但是边可能会很多，有些点给出的是和它不相邻的点。 **题解:** 如果某一个联通块只有一个点那么无解，否则遍历每个联通块直接染色即可。 至于边很多的处理，zzh鸽鸽曾经指导过。 开一个并查集，如果$i$被遍历过，把它和$i + 1$合并在一起，每个并查集内的最大值表示这个并查集中唯一的一个还没有没遍历到的点。 对于边少的点直接遍历，边多的点也是暴力枚举，不过是按照并查集来枚举，枚举后被合并后会使得并查集个数越来越少，最终复杂度仍然是线性的。 by MountVoom ===== F.False Intelligence ===== **题意:** 给定定义一个新的真值取值$U(Uncertain)$,扩充$\land,\lor,\rightarrow,\equiv$运算符的真值表 然后每次询问给定一个二变量真值表,判断是否有*公式*满足该真值表 **题解:** 考虑实际公式可能有括号如$\mathscr{C}: \mathscr{A} \rightarrow \mathscr{B}$ 可以利用第二数学归纳法思想进行扩展 我们得到了基础命题$\land,\lor,\rightarrow,\equiv$真值表,还需要扩展$x \rightarrow x, x \equiv x; x \land x, x \lor x$两种单变量命题 于是我们得到$\leq 1$个运算符的所有公式真值表,从而可以得到$\leq 2$所有公式真值表 一般的,有$\leq n$个运算符的所有公式,可以枚举得到$\leq 2n$的所有公式 当公式数量不再增加时即得到所有公式以及可能真值表(大概处理4次即可),再处理每次询问 by Hardict ===== G.Graphics Design ===== **题意:** 这个题题意看了很久qwq。 每个学生有一个大项目，每个项目分为许多小项目，每个小项目都有一个优先级，优先级两两不同。 每个学生的小项目必须按顺序完成，每个项目对三种物品都有某种需求，但是每种物品最多只需要一个。 在某一时刻，如果当前的物品满足了某些项目的需求，那么选择优先级最高的项目执行，此时会借走物品。 每个小项目有一个执行时间$t$，如果它在第$x$时间开始执行，那么会在$x + t$时间结束并把物品归还。 求所有同学结束自己的项目的时间。 **题解:** 因为优先级两两不同，最终的顺序一定是确定的，直接模拟即可。 在这里我用一个优先队列维护执行的事项，按完成时间由小到大排序。 用8个优先队列维护待办项目，每个优先队列对应一种需求的项目，比如1维护只需要1号物品的项目，按照优先级由大到小排序。 如果只用1个优先队列维护项目可能会出现很多项目需求不能被满足但是优先级很高，导致反复插入删除引起超时。 by MountVoom ===== H.Hilbert's Hash Browns ===== ===== I.Intuidiff II ===== **题意:** 题面描述诡异 但根据样例分析是给定$n$段$[l,r]$区间,将$[lmin,rmax]$划分成小区间,$[l,r]$可能会相同 然后需要找到一段递增的$l_{i_{1}}\leq r_{i_{1}} \leq l_{i_{2}} \leq r_{i_{3}} \leq ...$,使总长度最大 **题解:** 将区间变为$[l,r]=[l^{'},r^{'})$型,每段贡献就为$r^{'}-l^{'}$,且划分点为$r^{'}$ 根据划分点$r^{'}$离散化后树状数组进行$dp$即可 by Hardict ===== J.Just Terraffic! ===== 首先将这个问题变成一个dp问题，dp值为到这一点的方案情况，如果多于1，则标记为2，否则为0或1,1的话还需要维护当前具体方案。我们观察$\le1000$间隔所组成的每一段，发现转移只能从段的最后一个元素进行，否则不可能。转移最多只有两种可能，$i-2$和$i-3$，并且要注意这连续的间隔不能$\ge 2000$才行，转移的时候，如果源头状态可能性多于1，则直接标记不用求方案，否则要求出新的方案值，为方案值去重合并，再看这一个点的dp值。 总体来说难度不大，注意思路要清晰。 by Max.D. ===== K.Kiwis vs Kangaroos ===== 水题