UOJ Logo QAQAutoMaton的博客

博客

UOJ NOI Round #6

2022-07-22 01:20:48 By QAQAutoMaton

转眼间又是一年 NOI 了,为了帮大家备战 NOI,延续 UOJ 的传统保留项目,UOJ NOI Round #6 将在 8 月 5 号到 8 月 7 号隆重举行!

今年的 UOI 将在下山市举行! hehe 蚤是今年 UOI 的参赛选手。因为这场是 hehe 蚤以选手身份参加的最后一次 UOI,他准备在比赛结束之后在下山市旅游几天。本场比赛将以 hehe 蚤旅游时的见闻为主题。

比赛时间

笔试模拟将于 8 月 5 日晚 19 点开始,将进行半个小时。

Day 1 的比赛将于 8 月 6 日上午 8 点半开始,将进行五个小时,共三道题。

Day 2 的比赛将于 8 月 7 日上午 8 点半开始,将进行五个小时,共三道题。

比赛难度

比赛的难度将比 NOI2021 略微简单一些,相信对绝大部分选手来说题目是具有一定的挑战性的。

题目中还有一道交互题,大家可以放心食用。

出题阵容

这次拯救 UNR 的出题人有:

djq_cpp, he_____he, skip2004, xyr2005, 神秘人

这场比赛除笔试外将计入 rating。

我们相信这场比赛,可以给拼搏于 AK NOI 的逐梦之路上的你,提供一个有力的援助。

比赛奖项

这次比赛将会根据三次比赛的总分进行排序(如果存在同分将以两天的罚时总和作为第二关键字),其中比赛的前十五名将成为这次训练的金牌得主,第十六名到第五十名将获得银牌,第五十一名到第一百名将获得铜牌。(得奖人数将根据参赛人数进行调整)

总分前三名将获得 UOJ 萌萌哒的撕烤熊抱枕一只。

UOJ Easy Round #10

2022-03-21 11:32:24 By QAQAutoMaton

UOJ Easy Round #10 将于 3 月 26 日星期六晚上 19:00 举行!比赛将进行 3 个小时,共三道题。

这是 UOJ 第十场 Easy Round,还是一如既往的NOIP~省选难度。

1988 年 3 月 26 日,聂卫平被中国围棋协会授予“棋圣”称号,也是世界围棋史上第一位(也是目前为止唯一一位)由官方授衔的“棋圣”。

2022 年 3 月 26 日,跳蚤国王亲自授予 skip 蚤“码圣”称号,并为此举办了盛大的庆典。本场比赛将以这场庆典为主题。

出题人:xuanyiming, vfleaking, jacder

参加本次比赛将有机会获得 UOJ 抱枕!获奖条件的 SHA256 码是 ba43741ba9421d68e562bdd5dda3b68a8346c93fb4f44e3db1e5100047424619。比赛结束后将公布条件。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD: 恭喜前5名的选手!

  1. peehs_moorhsum
  2. mcfxmcfx
  3. AKEE
  4. hos_lyric
  5. yuyue
echo -n "非0分的计分提交中代码长度极差最大的,如有并列取排名最高的" | sha256sum
ba43741ba9421d68e562bdd5dda3b68a8346c93fb4f44e3db1e5100047424619  -

恭喜 peehs_moorhsum 获得 uoj 抱枕!

Goodbye Xinchou 题解

2022-01-30 20:21:10 By QAQAutoMaton

关羽下象棋

idea, solution from vfleaking, data from hehezhou

大家好,vfk 又来出题了 233 不过好像这次 FST 得有点惨。。哎,感觉这次出得不太好。

这道题既可以是一道猜结论题或者分类讨论题,也可以是一道暴力美学题。如果是我的话,在考场上我可能会当作暴力美学题来做,因为我会比较紧张;如果是平时自己做着玩的话,我会当一道分类讨论题来做。不过看到很多选手选择了分类讨论,却因为漏了情况而丢了不少分,我感到很惋惜。。

如果你回顾早年 UOJ 的 A 题,会发现都是些猜结论的题,而且还都有大牛十分钟就过了(但这道象棋题比以往的猜结论题复杂了许多)。我确实比较喜欢这类题吧。。因为我自己在赛场上有可能无法在短时间内那么机智地猜出结论,也许只会在做了一个小时之后才慢悠悠地提交上我的程序,所以我是真心觉得十分钟就过了当年猜结论类的 A 题的人很厉害。我一直觉得猜结论的能力本质上是一种计算机科学的直觉,或者数学直觉(类似于物理老师们强调的物理直觉)。真实世界的问题远比 OI 复杂,往往没有办法直接就做出来。很多时候确实是先得有人猜出来一个大致解法,然后再慢慢证明。所以说咯,直觉确实是个很重要的东西。

OIer 出比赛可能会有很多种不同的目的,比如展示自己的水平,比如分享自己的新想法,比如退役纪念。我的话,除了选题造题本身带给我的成就感之外,我会把比赛当作一种交流的途径。所以咯,当时我很喜欢把别人投来的猜结论题放到 UOJ 比赛里。大概想法就是,虽然我知道我有可能只会慢悠悠地做出来,但我就是想看看高手是怎么思考的,并学习学习。

不过这题不是别人投来的哈哈,我不确定我是否真的有出一道难度适中的猜结论题的水平,感觉这次有点翻车 ovo 啊所以,顺便征个题 233 欢迎来投小清新猜结论题呀!

好了下面我来讲讲我的思路(但并不是完全严谨的证明),也欢迎赛场上 AC 的同学们发发博客交流讨论。赛场上第一个用分类讨论的方式 AC 的应该是 Flying2018提交记录链接),还有一位是 Foden47提交记录链接)。所以强的人还是强啊!

算法一

第一个子任务里,车和卒是同一行的,显然车只要直接把卒吃掉即可。我猜肯定会有不想做博弈题直接跑路的选手 🤣 跑路之前这个部分分还是得拿一下呀,20分呢。

算法二

根据算法一的思路,如果卒和车在同一行或者同一列,我们直接输出 $1$。好了下面我们讨论 $x_1 \ne x_2$, $y_1 \ne y_2$ 的情况。

诶,我们接着来看第……第……第四个子任务!为什么直接跳到了第四个呢,因为我们需要想想一般情况下这个题的答案到底是多少。想要分类讨论,就要先想想答案最大是多少。而在第四个子任务里,卒和车都在棋盘靠中心的位置,所以我们至少可以不用考虑棋盘边界对答案的影响。

先看有没有对称性可以利用 —— 诶,有。卒和车都是左右对称的,所以我们不妨设 $y_1 < y_2$,即车在卒右边。如果 $y_1 > y_2$,我们可以做一个水平的镜像对称。虽然不一定会体现在代码里,但至少思考的时候我们不用考虑车在卒左边的情况了。

现在我们随手画一个车在卒右边的情况:

随手画一个

诶,然后我们来试试怎么把卒吃掉。我们先跑到卒的下面一行,这样卒就不敢往下走了,只能左右乱窜。然后我们就像样例一的第二组数据一样做:在卒的下面一行撒一行毒雾出来,卒仍然只能左右乱窜;现在我们跑到卒所在的那一行,卒仍然只能左右乱窜;接下来我们就把它吃掉。这样我们就得到了一个四步将卒吃掉的策略。

怎么把卒吃掉

努力枚举一番,你会发现你不可能找到一个三步的策略。等等,但为什么样例里最大值只有 3 呢。。。这确实是我们故意的,我们只放了答案小于等于 3 的情况。我们的本意是想区分开对着样例调的选手,和从头到尾先自己想再用样例检查正确性的选手,没想到导致了大片的 FST。(俗话说,出题人的嘴,骗人的鬼,所以还是不要轻信样例啊)

思考下这个策略,你会发现无论位置如何,你总能使用该策略。棋盘边界并不会有什么坏的影响,只会进一步压缩卒的移动空间,让答案小于等于 $4$ 而已。

不过我们现在在做第四个子任务,所以我们先不考虑边界的问题。那么,只要不在同一行同一列,就肯定是 4 了吗?如果卒和车离得很远的话,确实没有任何办法再优化 —— 首先如果卒既可以横向走,也可以向下走,那么卒肯定没办法在一步内被你吃掉,所以在吃掉卒之前,我们要么用毒封住卒的左右两侧,要么用毒封住下面。但封住左右两侧是需要走很多步的。因为如果你先封左边,卒可以往反方向走,导致你只能努力把它卡在某两列或者某三列,然后它就可以在里面继续乱走。经过一番尝试你会发现先封左侧或者先封右侧都是不可能比 4 步更优的。如果要封下面,那么晚封不如早封,所以就变成上图的那个策略了。

所以就是要考虑卒和车靠得很近的情况。可以发现,只要初始的时候不在卒所在的下一行,好像都没什么意义,还是得走到那行放毒。。如果在卒所在的下一行,那么上图的策略就可以省掉第一步了,于是 3 步就可以吃掉卒。(当然你看样例也会发现有这个情况)

特判掉这个情况,就可以过第四个子任务了。

if (x1 == x2 || y1 == y2) {
    return 1;
}
if (x2 == x1 + 1) {
    return 3;
}
return 4;

结合算法一,期望得分 40 分。

算法三

通过上述思路理清楚答案不超过 $4$,或者通过看样例之类的其他方式攒足了对“答案很小”的信心之后,你就可以使用暴力美学解决本题了。我认为也是比赛时最经济的一种做法。

因为答案不超过 $4$,所以卒之多只会走 $3$ 步,而车走到离卒太远的地方也毫无意义。

所以我们就可以在卒的初始位置附近,向各个方向延申常数格(仔细想想会发现常数取 $4$ 就足够了,不够自信也可以取一点,再逐步减小看看是否影响答案),然后只在这个小范围内进行搜索。如果车初始时不在这个范围内,不妨把车直接挪到离车最近的格点。

好的,迭代加深!博弈搜索!游戏规则也不是很复杂,按照题面把代码写出来就好了!赛场上大部分 AC 的选手正是用的这一暴力美学。

要注意的是搜索时我们要标记哪些位置是车曾经走过的。如果用布尔数组来存储,回溯时不方便还原。所以你可以用 int 数组存储每个位置被车经过的次数,这样递归时加加,回溯时减减就好了。

至于时间复杂度,你可以把所有可能的数据都试一遍,就会发现跑得贼快。这样大胆交一发,就直接过了。如果你使用的是这种做法,本题难点其实是你如何在尽量短的时间内,写出一份正确的博弈搜索代码。我看到有些选手的实现方式十分简洁,大家可以找来看看 233

一种实现下,搜索树的一个上界是 $1+39+39^2$,因为每一步为车的决策数最大为 $13$,卒最大为 $3$,并且如果第三步不能直接吃掉则可以剪枝。

期望得分 100 分。

算法四

下面我继续讲讲怎么通过分类讨论解决本题。

算法二已经解决了远离边界的情况,所以下面我们只用考虑边界问题。

由于卒不能往上走,所以上边界并没有什么用。而左右边界又是对称的,所以我们只用考虑左边界和下边界。(回忆下我们之前已经讨论过,只用考虑 $y_1 < y_2$ 的情况)

思路大致如下。我们已知答案小于等于 4,而 1 的情况已经被我们判掉了,所以我们只用找出那些答案为 2 或者 3 的情况,剩下的就是 4。

首先思考一下什么情况会出现 $2$。已知车和卒不在同一行同一列,又已知车直接吃掉卒才会获得胜利,所以要想两步内取得胜利,那肯定一步也不能浪费。肯定是第一步先移动到卒所在的行或者列,然后再吃掉。但卒人家也不傻,如果他万一在车走了一步之后动了下,车就吃不到了。所以只有可能是卒的初始位置不佳,导致卒只能横向或者纵向移动,才会出现答案为 2 的情况。

那么只有两种可能。要么卒的下边是棋盘边界,要么卒的左边是棋盘边界,如下图所示。一种情况是卒在最后一行,只能左右走。此时车走到卒所在的那一行,然后再花一步吃掉就好了。另一种情况是卒在第一列,比如 $(x, 1)$,并且车跟 $(x+1, 2)$ 要么在同一行要么在同一列。此时车花一步走到 $(x+1, 2)$(或者该步选择不动),然后卒只能往右或者往下,但无论怎么走都会被车吃掉。

只有两种可能

还有别的情况吗?如果卒在第一列且不在最后一行,车跟 $(x+1, 2)$ 既不在同一行也不在同一列,是否可以 2 步吃掉卒呢?枚举一番发现不行,但能发现一个 3 步的策略。首先我们把车移动到第二列。然后卒就只能往下走了,否则就会被立马吃掉。现在卒在 $(x+1, 1)$,车在第二列。这瞬间就变回了前面讨论的 2 步吃卒的第二种情况:把车移动到 $(x+2, 2)$ 的位置,那么接下来无论卒往下还是往右都会被车一步吃掉。

只有两种可能

综合上述讨论,虽然我们原本是想解决一下所有 2 步吃卒的情况,但似乎我们顺带解决了所有卒在第一列或者最后一行的情况了。这样就解决了第二和第三个子任务。

if (x1 == x2 || y1 == y2) {
    return 1;
}
if (y1 > y2) {
    y1 = m - y1 + 1;
    y2 = m - y2 + 1;
}
if (x1 == n) {
    return 2;
}
if (y1 == 1) {
    return x2 == x1 + 1 || y2 == 2 ? 2 : 3;
}
if (x2 == x1 + 1) {
    return 3;
}
return 4;

结合算法一算法二,期望得分 80 分。

算法五

我们离 AC 只有一步之遥了!这里只需要进一步讨论靠近棋盘边界的情况。但因为我们已经理清了答案小于等于 4 这一点,也找到了所有答案为 2 的情况,所以现在我们现在只用找出剩下的所有三步吃卒的情况就好了。

因为已经解决了第一列和倒数第一行的情况,所以我们只用接着考虑第二列和倒数第二行就好了。如果卒到边界的距离超过了 2 的话,只有卒在走第三步的时候边界才可能产生影响。然而我们讨论的是车是否可以三步吃卒,所以卒只能走两步。因此我们并不用考虑卒到边界的距离超过 2 的情况。

首先我们来讨论卒在倒数第二行的情况。我们只用枚举一下看看有没有三步吃卒的方案,结果发现还真有。我们只要把车挪到倒数第二行,那么卒如果左右动就会被立马吃掉,所以卒只能往下。这就变回了卒在最后一行的情况,我们只需要两步即可把卒吃掉:把车挪到最后一行,然后卒无论怎么动都会在下一步被吃了。

卒在倒数第二行

接下来我们来讨论卒在第二列的情况。类似卒在第一列的情况,我们可以注意到,如果卒在 $(x, 2)$,并且车跟 $(x+1, 3)$ 要么在同一行要么在同一列,那么车可以在一步之内移动到 $(x+1, 3)$,然后卒只能往左边走;车也往左边追一步,卒就只能往右或者往下了,然后就会被车在下一步吃掉。

卒在第二列

除此之外,只要第一步不通过某种方式阻止卒往右走,好像卒就会跑到第三列,然后就很难用所剩的 2 步吃掉卒了。所以就没办法了?

我出题的时候,第一次分类讨论就想到了这么多。然后码了一个暴力美学,结果发现 WA 了!

我漏掉的是这个情况:

第二组的解释

眼熟吗?眼熟。因为这是样例一的最后一组数据。我发现自己都漏了这个情况之后灰溜溜把这种情况加入了样例,防止大家 FST。。。哎但最后发现样例还是给得太弱了。

这个情况下也是 3!为什么呢?这种情况不是没法阻止卒往右走吗?

确实,但这种情况可以绕个圈把卒困住!我感觉这实在有点妙 233 可能也是这道题最有趣的地方了。首先车先走到卒下方那一行,然后卒只能左右走,否则就会被吃掉。然后无论往左还是往右,车都移动到第二列。如果卒是往左走的,那么下一步无论向右还是向下都会被一步吃掉;如果卒是往右走的,那么卒现在向右和向下都被死死地封住了,所以只能往左,结果就会被一步吃掉。所以样例里的这种情况,三步就能吃掉卒。

最有趣的情况

仔细想想,这种先围住然后再吃的情况只会发生在 $x_2 \le x_1$ 且 $y_2 = 4$ 的时候。如果不是这种情况,卒第一步往右走之后,枚举一番可以发现至少会有一个不会被车立马吃掉的移动方向,所以就没法三步吃卒了。

综合上述所有情况,我们就可以写出代码,获得 100 分了:https://uoj.ac/submission/531552

写在最后

如果不是放在比赛时做,心平气和地分类讨论一番,再结合样例的提示,应该是可以一次写对的。个人也确实很喜欢这种抽丝剥茧的分类讨论,写对了还蛮开心的。但现在这么出导致了一大片 FST,好像确实不太好。。再次谢罪.jpg

张飞卷精兵

idea by LMoliver, vectorwyx, solution,std,data by hehezhou

算法一

爆搜所有安排方案。可以证明安排方案总种类数为 $\frac{2^n!}{2^{2^n-1}}$。

复杂度 $O(\frac{2^n!}{2^{2^n}})$,可以通过子任务 $1$,期望得分 $10$ 分。当然略高的复杂度也可以打表提交来拿到相同分数。

算法二

考虑把对战建一棵树。每次对拼让赢家成为输家的父亲,点权即为初始卷力。那么答案就是奇数层权值之和减去偶数层权值之和。可以发现填数方案是合法的当且仅当父亲权值都大于儿子权值。考虑把权值从大到小填入,则这个过程可以看作:初始只有根解锁,一个被解锁的节点填入权值可以使它的儿子被解锁。

考虑一个贪心策略,如果当前能填入偶数层节点则直接填入,否则选一个节点填入,使得被解锁的节点数最多,如有多个任选即可。

这个策略是正确的!因为实际上如有多种选择,以这些节点为根的子树是同构的。考虑这棵树的构造方式。令 $T_n$ 为 $n$ 对应的树,显然有 $T_0$ 是单个节点,$T_n$ 的形态是一个根节点下挂了 $n$ 棵子树 $T_0,T_1,T_2,\ldots,T_{n-1}$。树上的所有节点可以按照儿子个数分成 $n+1$ 类,则同类节点代表的子树彼此同构。

时间复杂度 $O(2^n)$,可以通过子任务 $1,2$,期望得分 $35$ 分。

算法三

考虑优化上述过程。将儿子个数为 $x$ 的节点称为 $x$ 类节点。

删去一个奇数层 $x$ 类节点将解锁偶数层 $0,1,\cdots,n-1$ 类节点各一个,删去偶数层同理。那么在填入一个奇数层 $x$ 类节点后,会立刻填入 $x$ 个偶数层节点并解锁 $\frac{x(x-1)}{2}$ 个奇数层节点:$x-1$ 个 $0$ 类节点,$x-2$ 个 $1$ 类节点,$\ldots$,$1$ 个 $x-2$ 类节点。

维护出当前解锁的奇数层每类节点有多少个,依次将 $n,n-1,\ldots,0$ 类节点加入答案。计算贡献是等比数列求和的形式,可以在 $O(\log mod)$ 的复杂度内完成,维护的信息需要对 $mod-1$ 取模。处理完节点贡献后,需要将产生节点加入已解锁节点。

时间复杂度 $O(n^2+n\log mod)$,可以通过子任务 $1,2,3$,期望得分 $60$ 分。

算法四

考虑优化 $O(n^2)$ 部分,即计算每类节点的贡献次数,显然可以通过维护若干信息的后缀和降至 $O(n)$,或通过打表发现较为简单的规律。

时间复杂度 $O(n\log mod)$,可以通过本题,期望得分 $100$ 分。

赵云八卦阵

idea by orbitingflea, solution,std,data by QAQAutoMaton

算法一

我会记搜枚举所有合法方案!

期望得分$10$分。

算法二

设最后得到的序列为$b_1\dots b_n$。

注意到$b_i$是$a_i\oplus$ $a_1\dots a_{i-1}$的一个子集。

对于每个$i$枚举这个集合,然后算出lis。

时间复杂度$O(n^2 2^{\binom{n}{2}})$,期望得分$10$分。

算法三

我会dp!

dp[i][j]表示前i个位置,长度为j的上升子序列,末尾的位置的最小值。

从i转移到i+1的时候枚举$b_{i+1}$的值,时间复杂度$O(n^2 2^n)$,期望得分$30$分。

算法四

我会线性基!

我们发现,$b_i$取值是$a_{1}\dots a_{i-1}$的线性基能表示出来的值$\oplus a_i$。

则我们可以在算法三的基础上,在线性基里查询满足$\gt x$的最小$b_{i}$。

时间复杂度$O(n^2\log a)$,期望得分$50$。

算法五

注意到当$a_i$不能被加入线性基时,$a_i$能被前面的线性基表示出来,即可以认为$a_i=0$。这样的$i$不超过$\log a_i$ 段,每一段的线性基都一样。而$a_i$能加入线性基的$i$也不超过$\log a_i$段。

考虑我们对前一种情况整段转移。

由于有更新的dp值一定在线性基中,所以我们可以对原来的dp值算出在线性基里的排名,然后比它大的最小值就是排名+1,以此类推。

整段转移直接用单调队列优化即可。

时间复杂度$O(n\log^2 a_i)$,期望得分$70$。

算法六

算法五的瓶颈在于在线性基里查询。

注意到任何时候$b_i$都在$a_1\dots a_i$的线性基中,所以我们dp只需要记末尾最小值在线性基中的排名。

对于整段转移的部分,我们就可以直接+1,对于更新线性基的情况,我们需要把排名转为新的排名。

注意到把线性基写成等价的最简形式(即每个元素的最高位依次为 $h_1 > h_2 > \cdots > h_k$ 且除第 $i$ 个元素外其它元素的第 $h_i$ 位均为 $0$)后,一个数的排名就是它仅保留$h_1\cdots h_k$位后形成的$k$位二进制数。

那么当一个数被插入线性基后,对旧元素的影响是让某些更高的位异或上了$x$,则更新排名时只需要把更高位平移,并用builtin_parity求出$x$对应位的取值即可。

接下来的单点转移,只需要求出最小的比某个dp值大的,满足某几位异或和是定值的数。可以类似的O(1)求出。

时间复杂度$O(n\log a_i)$,期望得分$100$。

算法七

by QAQAutoMaton

$b_i$的取值是$i-1$前缀线性基能表示出来的所有值$\oplus a_i$,则如果$a_i$没被插入线性基,$b_i$的取值就是$i$前缀线性基能表示出来的所有值

先从前往后把每个$a_i$加入线性基,然后从后往前每次考虑加入一个新的$b_i$。

对于一个没在线性基中的$i$,可以注意到如果$b_i$能被加入,把$b_i$加入lis而非等到更小的$j$再加入一定不劣,原因是对于所有$j\lt i$ $b_j$的取值都是$b_i$的子集。

所以只需要考虑在线性基中的i是否在lis中。

设在线性基中的位置为$1=k_1\lt k_2\dots k_m\leq n$。

可以发现相邻两个$k_j$之间的$i$取值集合是一样的,可以整段转移。

考虑dp[i][j]表示只考虑$k_i\dots n$这一段后缀,在线性基的位置有$j$个在lis中,不在的位置全在lis中,lis开头的最大值。

则我们整段转移的时候只需要定位到$x$的排名$y$,然后直接$y,y-1\dots $即可,如果到1了就直接更新答案。

时间复杂度$O(n\log a_i+\log^3 a_i)$,期望得分$100$。

马超战潼关

idea by byqx, solution,data by he_____he , std by hehezhou

显然题意即为求一个经典二分图建图中的最小割个数。

算法 1

我会暴力!枚举每条边选或不选,检查是否是一个最小割即可。

时间复杂度 $O(2^{2n+m}n^2)$,可以通过子任务 1,期望得分 $5$ 分。

算法 2

我会比较好的暴力!令 $1$ 号点为源点,$2n+2$ 号点为汇点。

枚举每条与源点和汇点相连的边是否在割中,就能知道中间的边是否需要割。

时间复杂度 $O(2^{2n}n^2)$,可以通过子任务 1 和子任务 2,期望得分 $15$ 分。

算法 3

枚举左侧割了哪些边。对于右侧一个点,考虑有哪些左侧未被割开的点向这个点连边。如果总连边数量超过 $1$ 条,那么发现一定要割这个点与汇点之间连的边。如果总连边数量恰好为 $1$ 条,那么在这条边和到汇点的边之中一定恰好割其中之一。如果没有连边,不需要割边。发现右侧所有点均独立,直接相乘即可得到方案数。

时间复杂度 $O(2^nn^2)$,可以通过前四个子任务,期望得分 $45$ 分。

算法 4

换一种方式看待问题。考虑先求出一种最大匹配的方案。可以发现,对于其中一个匹配 $(x,y)$,$S\rightarrow x\rightarrow y\rightarrow T$ 这三条边一定恰割一条。

枚举割哪条,看是否是个合法方案即可。

时间复杂度 $O(3^n n^2)$,可以通过前三个子任务,期望得分 $35$ 分。

算法 5

仔细观察上一个算法,考虑什么样的方案是合法的。构造一个图,每个点代表一对匹配,用点权 $0,1,2$ 分别代表割 $S\rightarrow x$,$x\rightarrow y$,$y\rightarrow T$。设 $a_x$ 为 $x$ 所在匹配的点权。对于一条不在匹配的边 $(x,y)$,显然由匹配的最大性,$x$ 与 $y$ 至少有一个在匹配中。

  1. 如果 $x$ 与 $y$ 都在匹配中,则相当于不能有 $a_x=1,2$ 且 $a_y=0,1$,即 $a_x=0$ 或 $a_y=2$。
  2. 如果只有 $x$ 在匹配中,则相当于要求 $a_x=0$。
  3. 如果只有 $y$ 在匹配中,则相当于要求 $a_y=2$。

对于第一种情况,我们在 $x$ 和 $y$ 的匹配代表的点之间连一条有向边。

可以发现如果有一条边 $(u,v)$,那么 $a_u\leq a_v$ 并且不等于 $1$。所以相当于在这个有向图的任意一条链上,边权一定形如 $0,0,\ldots,0,(1),2,2,\ldots,2$ 的形式。要求的即为分配点权的方案数。

枚举选 $0$ 的集合,需要满足不存在一条集合外连向集合内的边。发现 $1$ 只能放在所有集合外入度为 $0$ 的点中,并且对于所有点独立。只需检查集合外入度为 $0$ 的点个数即可。容易发现这实际上和算法 3 本质相同。

时间复杂度 $O(2^nn^2)$,可以通过前四个子任务,期望得分 $45$ 分。

算法 6

我会爆搜!每次挑度数最大点爆搜,出现不同连通块就分开计算。

时间复杂度:???

期望得分 $35\sim 100$。

算法 7

观察 $u_{2i-1}=u_{2i},v_{2i-1}=v_{2i}$ 的条件有什么用。如果这两条边不在匹配中,那么和一条边没有区别。如果这两条边中有一条在匹配中,那么在算法 5 的有向图中会出现自环。自环说明这个点不能选 $1$ 作为点权。所以所有点点权只能为 $0$ 或 $2$。

再考虑图中的环。可以发现环上的所有点一定权值都相等,并且不能为 $1$。所以可以缩点,将图变为一个 DAG。将拓扑序求出,分为前一半和后一半。

枚举前一半哪些选 $0$ 哪些选 $2$,对于后一半的限制即为限制某些点必须选 $2$。预处理后一半的情况,做一次高维前缀和即可。

时间复杂度 $O(2^\frac{n}2n^2)$,可以通过子任务 5,结合算法 5 可以获得 $65$ 分。

算法 8

现在每个点点权可以为 $1$,类似的,将图缩点之后分为拓扑序前一半和后一半。枚举前一半的情况,对于后一半的限制即为限制某些点必须选 $2$。一样高维前缀和预处理即可。

时间复杂度 $O(3^{\frac{n}2}n^2)$,结合算法 7 可以通过前六个子任务,期望得分 $80$ 分。

算法 9

再仔细观察分为两半之后的过程。

如果只枚举前一半哪些选 $0$ 哪些选 $1$ 或 $2$,考虑以下两个问题:

  1. 前一半对后一半的影响
  2. 前一半内部的方案数

先看前一半内部的方案数如何求出。类似的,只有 $0$ 后面能选 $1$,$1$ 和 $2$ 后面不能选 $1$,所以选 $1$ 的只能是在 $1,2$ 对应的导出子图中入度为 $0$ 的点。同样类似算法 5 中的分析,这些点互相独立,方案数即为 $2$ 的这么多次方。

再看前一半对后一半的影响。如果一个点为 $0$,那么对后面的点没有影响。如果一个点为 $1$ 或 $2$,那么要求出边对应的点只能选 $2$。所以相当于后一半中有一些点必须选 $2$。那么可以预处理出固定一些点选 $2$ 剩余点选 $0$ 或 $1$ 的方案数(这与前一半类似),再高维前缀和一次即可。

时间复杂度 $O(2^{\frac n2}n^2)$,期望得分 $100$ 分。

黄忠庆功宴

idea, solution, std, data from djq_cpp

这道题出处其实是 chasedeath 问我的一道多项式题(?)大家似乎不太资瓷今年 Goodbye 出多项式,但感觉这个求和的部分本身也挺趣味就出出来了。原定是 D,由于出题人实在出不出困难而有趣的 E 就直接放 E 了,向广大 OIer 谢罪(雾

算法 1(std)

每次查询即求下标为模意义等差数列的 $a$ 之和。

考虑公差 $k$:若 $k \leq \sqrt{p}$,可以直接对每种 $k$ 预处理前缀和,复杂度 $O(p \sqrt{p} + q)$;另外,容易发现公差为 $k$ 的等差数列可以写成 $k^{-1}$ 个公差为 $1$ 的等差数列的并,故若 $k^{-1} \bmod p \leq \sqrt{p}$,原问题也可以用前缀和在 $O(p + q\sqrt{p})$ 时间解决。

进一步地,考虑将 $k$ 写成 $\frac{x}{y} \bmod p$ 的形式,其中 $1 \leq x, |y| \leq \sqrt{p}$。所有的 $k$ 均可写成这样的形式,这可以通过对集合 $\{x - yk\}$ 使用抽屉原理得到。进而只需对所有 $x$ 求出 $b_i = a_{ix \bmod p}$ 及其前缀和,再在序列 $b_i$ 上以 $O(y^{-1})$ 的复杂度解决每个当前 $x$ 对应的询问,即可在 $O(p \sqrt{p} + q \sqrt{p})$ 的复杂度解决原问题。事实上,当 $p, q$ 不同阶时,通过调整 $x, y$ 的上界,易得一个 $O(p \sqrt q)$ 复杂度的算法。

算法 1.1

根据观察场上许多选手的做法都与算法 1 基本一致,但选取的 $x$ 不是 $[1, \sqrt{p}]$ 而是 $O(\sqrt{p})$ 个随机值。事实上,这并不影响算法的期望复杂度,因为对每个公差 $d$,它对应的最小 $y$ 的期望都是 $O(\sqrt{p})$ 的。(虽然针对程序使用最劣的公差大概可以卡到多一个 $\log$)

(不过很多选手都因为常数问题只获得了 $55$ 分?这可能是因为随机化或者因为对下标模 $p$ 的处理不太漂亮?std 只要 1.1s,不过我是不是还是成为屑卡常出题人了)

算法 2 一些想法

笔者并未发现与算法 1 本质不同的可 AC 做法,不过从欧几里得算法的角度看,原问题等价于每次求 $a$ 与一个万能欧几里得序列的内积,从而或许还存在更本质的解法。遗憾的是,从这条路线出发,笔者目前只知道 $O((p + q)p^{\frac{2}{3}})$ 的解法。感兴趣的选手可以自行思考,也欢迎与笔者讨论。

UOJ Round #22

2021-09-26 17:56:55 By QAQAutoMaton

UOJ Round #22 将于 10 月 2 日星期六晚上 19:00 举行!比赛将进行 3 个小时,共三道题。

这是 UOJ 第二十二场 UOJ Round,还是一如既往的省选及以上难度,欢迎大家来玩!这也是新一批鸽子上任后的第一场比赛

公元 1909 年 10 月 2 日,由詹天佑领导修建的京张铁路正式通车,这也是首条完全由中国人自主筹资、勘测、设计、建造的铁路。

最近,跳蚤国正在尝试开辟月球基地,需要修建铁路,于是跳蚤国王找到了得力助手伏特。你能不能帮助伏特完成铁路修建工作呢?

出题人:he_____he,wangziji,jiqimao

参加本次比赛将有机会获得 UOJ 抱枕!获奖条件的 SHA256 码是 d3c2e90298c0fc0c0b25603e322198a6c7a4d9b76ed3a0c4a76f836d81344ae2。比赛结束后将公布条件。

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

UPD: 恭喜前五名的选手!

  1. big_isonan

  2. csy2005

  3. feecle6418

  4. hos_lyric

  5. lqs2015

echo "使得总分变低的提交数最多的,如有多个取减少分数总和最大的,如还有多个取排名最高的" -n | sha256sum
d3c2e90298c0fc0c0b25603e322198a6c7a4d9b76ed3a0c4a76f836d81344ae2  -

恭喜 gyh20 获得 uoj 抱枕!

QAQAutoMaton Avatar