20241218 部分作业

too hard for me!(2)

Atcoder 链接。

~~感觉其实是把官方题解翻译成中文之后加了点东西。~~

QOJ9875. Don't Detect Cycle

题意

给定一张个点条边的简单图。

现在你需要按照顺序加入这条边，使得加入一条边时，两个端点都不在任何一个环里面。

判断有没有解，有解的话还需要构造方案。

。

题解

正着不好做，考虑倒着做。

初始有一张图，需要找到一个删边的顺序，使得删完边之后的两个点不在一个环里面。

删完一条边的时候显然限制是会变弱的，所以这个时候一定是能删的尽早删。

那么求出这张图的边双，割边放到最后删肯定不劣，那么只需要考虑一个边双内部怎么办。

可以发现，一条边可以删掉相当于这两个点在边双内部度数均为。

考虑这条边删掉之后，整个边双会分裂成若干个边双，形成一条链。

如果度数，就说明分裂完之后所在的新边双里面不只一个点，不只一个点就一定仍然存在一个点。

所以在之前边双内部度数一定恰好是，点同理。

所以直接一条一条删就做完了。复杂度。

提交记录。

QOJ9876. Self Checkout

题意

给定一个由组成的长为的序列。

现在需要计算只包含的序列的数量，满足经过如下过程能够得到：

初始有一个空序列。
若当前不为空，令变量，否则过程结束，返回序列。
若当前中至少有一个，令，然后将序列中第一个删掉。
若当前不为空，将加上序列第一个数字，然后将第一个数字删掉。
将放到的末尾，然后返回第二步

。

题解

首先考虑操作进行了次的情况。

枚举操作进行了次。

那么的前个数字只有，后个数字只有。

先来考虑前面的部分，先来考虑前面全是的情况，可以发现，这种情况只需要开头有个。

然后考虑前面全是的情况，此时需要开头有个和个，需要满足任意前缀中。直接反射容斥。

然后考虑中既有又有的情况，不妨发现，把这些连续段拿出来，段与段之间是独立的。

只有可能最后一段是全，然后和后个数字有一些联动，还是直接反射容斥一下就行。

然后是操作进行了次的情况，此时操作一定进行了次。

也就是说，中一定前面个数字是，最后一个数字是。

那么就只需要管前面即可。

提交记录。

QOJ9877. Segment Tree

题意

现在有一张个点和条边的图。

边有边权，所有边形成一个线段树的样子。

现在需要进行次操作，每一次操作要么修改一条边的边权，要么查询两个点之间最短路。

。。

题解

其实这道题相当于是，有一棵维护了区间和的线段树，每一次可以花费若干代价，询问线段树的一个区间和。

一个询问相当于给你一个区间，查询区间和，最少需要多少代价。

查询有几种方式：

如果查询的区间恰好对应了线段树上一个完整的点，那么可以直接查询这个区间；
将这个区间分成两部分，分别进行查询；
查询这个区间的某个超集，然后再查询超集减掉额外部分。

考虑如何计算代价。

首先，如果一条边的边权比他两个儿子的和还要大，那么我们先给他取一个。

这样的话，方式显然就只有一种可以直接选择。

对于询问，考虑从其中一个点在线段树上一直往上跳，并维护其到每一个祖先的最短路。

另一个点同样处理，两个距离加起来取 min。

提交记录。

QOJ9879. ReTravel

题意

初始有一个机器人在原点。给定个平面上的点，现在需要进行若干次操作，使机器人按顺序访问点。

操作共有以下种，初始有一个空的字符串。

让机器人向轴正方向走一步，将一个字符添加到末尾，花费的代价；
让机器人向轴正方向走一步，将一个字符添加到末尾，花费的代价；
撤销最后一个字符对应的操作，不花费代价。

。

题解

设，同理。

设表示以为起点，按顺序便利这些点，最少的代价是多少。

首先边界状态是。

考虑当的时候如何转移。

假设此时第一个进行的操作为一操作，那么此时会先解决掉这些点，然后撤回这个一操作，继续走后面。

此时一定不会有，因为如果中间一个点都没走到，那么显然进行的一操作就浪费了，直接不走就好了。

此时也一定不会有，因为一定存在一个，进行一操作不撤回的话显然走不到点。

那么我们枚举，就将整个问题拆成了两个子问题和。

时间复杂度。

提交记录。

QOJ9880. Origami Warp

题意

现在有条直线，第条直线以的形式给出，表示这条直线经过和这两个点。

保证第一条直线为轴，第二条直线为轴。

现在有一个点，可以进行若干次操作，每一次操作是选择一条直线，然后把按照直线对称过去。

称点能到达点，当且仅当对于任意的，都能在有限步之内，使得的欧几里得距离。

给定组询问，每一组询问给定两个点，询问是否能到达。

数据组数，。

题解

首先这个可达性有一些性质。

神秘小性质

性质：点可以到达自己。

废话。

性质：若点能到达点，则点能到达点。

证明：若能到达，则对于任意的，都能在有限步内，令的欧几里得距离。

那么把整个操作步骤倒过来，就能让在有限步内到的欧几里得距离。

性质：若点能到达点，点能到达点，则点能到达点。

证明：若能到达，则对于任意的，都能在有限步内，令的欧几里得距离。

到也同理，两个操作序列拼起来就能得到一个到的欧几里得距离的方案。

不妨设现在有两条直线，这两条直线的交点为原点，第一条直线是轴，第二条直线的倾角为。

假设当前有一个点，他的倾角为。

那么我们首先可以知道，如果只使用这两条直线，则的长度永远不会变。

考虑把点先按照第一条直线对称，得到的倾角为。

再把点按照第二条直线对称，得到的倾角就是。也就是说，只用这两个操作可以得到所有的。

画出一个以为圆心，为半径的圆。

此时，若是一个无理数，则一定可以到达，上的每一个点。

考虑题目的直线是以两个整数点的形式给出的，那么一定也是一个有理数。

在这个条件下，可以发现，若为有理数，那么一定是的倍数。

那么，若两条直线的夹角不为的倍数，则称这两条直线的交点为好的交点。

这样一个好的交点，就可以让我们把一个点移动到一个圆上的任何一个点去。

那么初始的时候，若至少存在一个好的交点，则说明存在至少一条直线，倾斜角不是的倍数。

考虑此时若存在不为原点的好的交点，则平面上任意两点都可以到达。

否则，平面上只有原点一个好的交点，此时一个点可以到达所有和原点距离相同的点。

那么问题在于，如果此时没有好的交点，如何判断答案。

此时只会有倾斜角为的直线，设他们分别为型直线。

先来考虑一个一维的问题，现在有一个数轴，数轴上有个点。

初始时有一个点，每一次可以进行的操作是把转到某一个点的对称点去。

现在问能不能把点对称到另外一个给定的点去。

的情况特判掉，然后设。

那么能到当且仅当或。

证明的话和上面某部分差不多，考虑把一次对两个点对称，那么可以到去。

后面就比较容易能证出来恰好是那两种情况能走过去。

有趣的事情是，如果我们将这个点替换为两个点，那么答案不变。这个结论后面要用。

那么回到原题，此时若没有型直线，那么横纵两维就是两个独立的一维问题，可以分开做。

再来考虑有型直线的情况。

假设现在有三条直线交于一个点，三条直线分别为型，那么删除型的直线，答案不会变化。

为什么呢，假设一个点（相对于点）的倾斜角为，那么操作一次型可以变成。

那么按照的顺序操作，也能达成目标。

所以删除这条型的直线，不影响答案。其他方向是同理的。

那么也就是说三条直线里面，他们的效果有，也就是说我们可以把一条型直线替换为一条型直线。

初始的时候我们至少有一条型直线（轴），那么我们就可以将所有的型直线都转为型直线。

根据上面一维问题的相关证明，我们可以假设此时型直线最多只有两条。

那么我们现在至少有一条型直线，考虑将所有的型直线都转为型直线。特殊的，不删除轴这条直线。

（将型直线转为型需要借助一个型直线，注意如果此时有两条型直线，那么两种转过去的方式都要进行）

设为当前所有型直线两两位置差的，那么我们任意加型直线都不影响答案。

特殊的，还可以发现我们任意加一条型直线也不影响答案。

为什么呢，因为你可以看成把所有型直线换成型，可以发现求出来的值是相同的。

此时，如果我们有两个型直线，把其中一条转化为型。

那么现在，我们拥有所有或形式的型直线，并且我们有至多一条型和至多一条型直线。

此时有一种神奇的判断方式，考虑先枚举型和型是否使用，此时有种情况。

然后后面的过程中，只使用型两种直线，可以证明这样判断是正确的。

首先，这样能操作到的点，肯定是正常情况下能操作的。

我们现在需要证明，所有可达的点，都能通过这种方式操作得到。

考虑，假如我们现在有一个由构成的操作序列。

若现在有一个操作，他的前面是一个操作，设这两条直线的交点为，则我们一定有一条型直线经过点。

那么我们就可以将一个操作替换为一个操作，操作都可以这样替换。

这样我们就把一个操作往前提了一个位置，这样我们就能把所有操作都堆在序列的最前面。

由于型直线是完全垂直的，所以这两种操作是完全独立的，操作顺序不受影响，所以两个操作最多各进行一次。

时间复杂度。

提交记录。

QOJ9878. A xor B plus C

题意

给定四个数字。

定义序列为：。

求。

，。

题解

下文中使用代表二进制下按位异或运算。

令表示二进制下的第位，即。特殊的，有。

设表示计算时第位是否有进位，即。

考虑的计算过程，那么我们还能得到。

观察一下，可以发现这还能说明。

首先来观察一下，那么因为，所以直接就是。

那么还有。

所以有长为的周期，这也说明了有长为的周期。

同时我们也可以使用数学归纳法证明，所有都有长为的周期。

首先设。则也应有的周期。那么：

这说明如果有长度为的周期，就可以证明有长度为的周期。

而的情况已经证明过了，所以可以数学归纳法证明都有的周期。

此外，还可以得到应该有。

那么考虑一下这道题应该怎么做。

如果想要知道，我们可以考虑去维护，但是这显然是不好搞的。

但是若我们知道了，那么我们就能知道，进而得出。

所以有一个自然的想法，就是我们去维护。

根据前面的讨论，我们知道的周期是，那么考虑去维护里面的分别在哪里。

令，那么对于的部分，我们可以暴力去维护。因为此处长度最多也就。

那么后面的部分呢，我们仍然考虑暴力维护的位置，所以下面我们证明，中的数量不会特别多。

如果全都是的话，最低一位和上面是完全独立的，可以分开去做。

那么不妨假设不全为，下面证明对于有，此处的表示可重集。

首先我们知道。还有：那么我们可以发现当的时候有。这说明。

如果，那么就等价于。

此时如果，那么时，时恰好有一个。

这说明的时候有。

同理，此时如果，那么时两个数字都是，当时两个数字里面恰有一个。

那么说明时有。

那么当的时候，就可以推出，那么自然成立。

而根据我们的假设，不全为，那么推一下就能知道一定有。

而这恰好又能推出。所以结论成立。

对于的部分，此时有。

那么根据我们之前的式子，此时就有。

那么可以发现，这等价于和同时满足。

考虑令，那么就是中的数量。我们希望证出这个数字不是很大。

先来考虑第一个条件，首先因为，那么。

那么就完全由上一位的进位即决定。

那么可以得到。

那么就有。

不妨设。

那么考虑，的周期长度是，的周期长度是，考虑怎么计算。

首先如果，那么一定会有。

否则，则有，。

根据之前的证明，我们知道恰好存在一个满足，我们令这个为唯一的这个。

特殊的，从之前的证明还可以看出，所有的所对应的都是相同的。

那么若，则有，。这说明。

这是好的，因为这部分情况下中的个数并没有增加。

而当的时候，有。

那么问题在于，和的差距有多大。

考虑如果，那么此时会有。

只有的时候，才可能为，而若又一定会导致。

所以此时应该有。

那么去掉这个限制，可以发现一定有。

对于的情况，我们首先知道有。

那么对于的情况，就有和。

所以说时中的数量不超过。（你妈的终于推完了）

设为最小的满足，则内至多有个。

令为剩余的的个数，则这个数字是级别的。

那么在里面，我们只需要维护的的位置。

然后用 set 瞎模拟一下每一个数字消失的时间，能做到。

直接暴力模拟最坏是的，其中表示多少轮之后所有都消失了。

最坏可能是级别的，但是显然卡不到，实际运行中应该是这个级别的。

提交记录。

QOJ9881. Diverge and Converge

题意

给定两棵个点的数，边集分别是。

现在需要构造两个长为的排列。

然后会进行次操作，第次操作为将第一棵树里的边删掉，然后加上。

第二棵树同理，要求每一次操作完之后，得到的仍然是两棵树。

。

题解

考虑归纳进行构造，那么显然啥都不用输出。

设两棵树分别为，那么考虑将两张图并到一起。

并起来的图一共有条边，那么度数总和就是。

这说明图中至少存在一个点，满足的度数。

那么的度数只有可能是或，考虑分类讨论。

若的度数是，则其一定在中各连了一条边。

那么我们考虑第一步把这两条边交换，然后把从图中删除得到两棵树。

则都是有个点的树，存在一个合法的方案，那么我们就构造出了的方案。

那么如果的度数是，我们不妨设在的度数为，在的度数为。

设在中与有连边，在中与两个点有连边。

那么我们令为删掉得到的树，为删掉并加入边得到的树。

则应该能构造出一组解。设这条边在时刻被交换。

不妨假设，在时刻交换之前，中去掉这条边之后，连通。

那么对于之前的时刻，加入点和边后，仍然合法，因为恰有一个来自一个来自。

那么考虑在时刻之前我们额外加入一个交换的操作，显然加入之后仍然合法。

那么下一步的操作是交换一条边和边。那么在中，我们交换和这两条边。

手动模拟一下，可以发现这样是合法的。

提交记录。