Kevin5307的博客

博客

Tags
None

ZJOI 2015 Day 2 T1 黑客技术

2024-12-19 11:33:42 By Kevin090228🍬

测试点 1

大概是用来让你感受这个奇怪语言的劲的。找到代码中奇怪的数就能拿到 10 分。

一种可以拿到 10 分的输入:

23333333

测试点 2

先运行一次,发现需要输入 10 个整数。用你喜欢的方式在代码中找到 geti 片段。发现每次读入进来之后,如果 $ 1# 0 相等就输出 ok 否则输出 ko。于是我们不需要搞清楚代码的原理,只要修改一下代码,每次打印 # 0 然后复制粘贴即可。

注意代码中存在跳转行号,所以尽量不要一次插入多行输出行,不然可能会导致行号倒闭然后代码乱飞。

一种可以拿到 10 分的输入:

7
47
1965
1915
-2551
-1646938625
-322
-167542220
4346926
1531256182

测试点 3

用你喜欢的方式在代码中找到 putc @ 111 片段,可以发现代码中总共有 10 处输出 ok,按照 1333 的方式分布。运行一下可以发现,它让你输入 20 个数,只要输入了就可以得到第一个 ok。事实上,如果你无脑打了 20 个相同的整数,可以发现输出是 ok fail fail ok ok ok,也就是我们拿到了第四组限制的三分。

观察代码可以发现,后三组限制都是,判断某个量是否和预设量相等,如果是就输出三个 ok。通过打印中间变量,进行一些最基础的尝试可以发现,三个限制分别为:

  • 20 个数至少一个非 0
  • 20 个数的和为 0
  • 20 个数全部相等。

回想题面中描述的关于自然溢出的说明,可以想到,只需要输出 20230 即可。

一种可以拿到 10 分的输入:

1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824
1073741824

测试点 4

尝试几次,根据输出的提示可以发现,读入的是一个字符串可以获得 3 分,字符串长度恰好为 18 可以再获得 2 分。

依然是用你喜欢的方法找到 putc @ 111,发现在代码的末尾有一个可以输出 5ok 的地方。它的判断条件自然在它之前紧跟着它,可以找到第 300 行开始的 9 行一周期循环了 18 次的相似代码块,在其中的判断语句中可以找到一些接近 100 的数,大胆猜测它对应 ASCII 码。查阅题面的表格构造对应的输入即可。

一种可以拿到 10 分的输入:

primaryschoolpupil

测试点 5

代码中出现了功能类似于对 998244353 取模的片段。

测试一下可以发现它需要输入 10 个字符串。在输出 ok 的语句之前可以找到十个判断,发现是判断某运算结果和大整数是否相等。猜测是字符串哈希,打印运算结果,尝试几次后可以发现 az 对应 025,底为 26

于是将判断中的 10 个大整数按照 26 进制分解即可。

一种可以拿到 10 分的输入:

z
x
l
r
p
vfk
lssb
driozw
bqqcgzg
sanuwq

测试点 6

代码和测试点 5 几乎完全一致。进行尝试后可以发现在这份代码中底为 31

直接进行 31 进制分解可能会存在某一位 26 的情况。于是暴力枚举和大整数模 998244353 同余的数直到不存在这种情形即可。

一种可以拿到 10 分的输入:

p
n
nxybfe
bchdeeu
bdaeyow
eimvdvj
cqtmtzr
dcshgqm
djgxcsu
hilgqu

测试点 7

尝试一下可以发现要输入 10 个整数。代码的判断部分和前面两个测试点相似,打印中间变量后可以发现是在模 998244353 意义下求出输入的逆元并进行比较。逆元运算是可逆的,求出参与比较的 10 个整数的逆元即可。

一种可以拿到 10 分的输入:

998244353
1
224032231
204247430
800006205
536388420
830137805
173645564
591950221
212467234

测试点 8

与第 7 个测试点相似,同样是存在某个函数 f(x) 将输入变换后与 10 个整数比较。打印中间变量可以发现 f(0)=0f(1)=1,但 f(2) 很大并且看上去没有规律。

尝试打印 f(1) 发现会 Runtime Error,于是尝试 f(998244351)f(998244352)f(998244353)f(998244354),发现有周期 998244353,并且是奇函数。猜测是指数函数,写暴力验证可以得到 f(x)=x77977

由于 gcd,所以可以直接求出 77977 次方根。或者可以写一个暴力来枚举,跑五分钟不到可以跑出来。

一种可以拿到 10 分的输入:

0
1
43409364
171593339
879723643
750576725
275034811
464166077
503262602
826391194

测试点 9

还不会。

测试点 10

还不会。

2024 年 KAIST 第 14 次 ICPC 模拟赛题解

2024-10-11 14:20:56 By Kevin090228🍬

A

杜老师做的,听说是烂题。

B

签到题,先咕了。

C

做法一

倒过来模拟染色过程,考察联通块数的变化量。可以发现,倒过来模拟这个过程时,右边界有相同的颜色,下边界也有相同的颜色,所以染色会增加连通块当且仅当新的颜色与右边界和下边界都不同。

容易想到用线段树维护 DDP,每个节点要记录 2^2 个值,表示不翻转/翻转行,不翻转/翻转列时的 DDP 状态。维护是简单的。

时间复杂度 O(n\log n),有 36 的常数,能跑过去。

做法二

先咕着。

D

不是我做的,咕了。

E

存在一个暴力的费用流做最小权完美匹配的做法,用 Cost Scaling 和匈牙利可以做到 O(n^3\log V),常数比较大,应该是过不去的。

分析菱形覆盖的形态,发现对于上半部分,第 i 行与第 i+1 行间的竖直菱形数量恰好为 i,且相邻两层间的竖直菱形插空分布。于是可以把竖直菱形按照斜向分组,建出一个新的费用流,每一组对应 1 的流量。此时只需限制点的流量和边的流量 \leq 1 就可以保证竖直菱形插空分布。分类讨论一下边权的值暴力跑费用流。

注意到这个新图流量只有 O(n) 大小,于是跑暴力即可,时间复杂度 O(n^3\log n),可以通过。

F

签到题,求出每一层的 SG 函数,异或起来就做完了。

G

签到题,二分答案之后排序来 check 即可。

H

还没完全会,等过了再补。

I

杜老师做的签到题。

J

容易发现 (1,0),(0,1),(-1,-1) 可以构造所有点,故答案 \leq 3。先特判答案为 1 的情况。

要让答案 \leq 2,至少需要所有点在同一个半平面内。此时需要特判如果存在两个点方向恰好相反,如果还有不在直线上的点就答案为 3,否则答案为 2

然后对于所有点在同一个半平面内的情形构造。对于所有点都 x\geq 0 的情形,可以构造 (0,1)(1,-10^{18}) 作为答案。类比到所有情形,只需要半平面对应的直线的一个方向选择一个向量,然后找到半平面内尽量接近直线的点,往另一个方向拉到无穷远处即可。

尽量接近直线的点可以 exgcd 求出。

时间复杂度 O(n+\log V)

K

可以建出一个差分约束模型,于是可以得到如果有解,那么存在一种方案每个点的值要么是 0 要么是 K

对于两个有包含关系的区间,可以确定大区间减去小区间的部分全是 0,并删除大区间。得到一个位置是 0 之后需要把剩余的区间缩起来然后继续考虑包含关系,同时判掉区间被删空的情形。

对于不存在包含关心的情形,排序之后贪心即可,一定有解。

时间复杂度 O(n\log n)。需要注意实现的细节。

L

树上背包模板。

M

将代价拆到每条边上,变成 这条边交换的次数 + 这条边两侧均出现了的颜色种类数。如果不进行交换,一条边的代价 \leq 2。对于初始存在一条边代价为 0 的情形,显然取到理论最小值 n-2,特判即可。

然后可以发现,要让一条初始为 2 代价的边变成 1 代价,必须要用它进行一次交换,并且最终它恰好隔开黑色和白色。于是这样的边最多一条,只需要判这种边存不存在。

容易发现存在的充要条件是这条边:

  1. 将树分成了两个区域,大小分别是黑色点个数和白色点个数。
  2. 黑色区域有恰好一个白点。
  3. 白色区域有恰好一个黑点。
  4. 这个黑点与这个白点都不是叶子。

判断这四个条件即可,时间复杂度 O(n)

时光荏苒

2024-08-30 20:07:22 By Kevin090228🍬

时光荏苒,小 S 和小 Y 也会散去。而我们和一个人保持连接的方式就是把小 S 和小 Y 变成 S 接 Y,仅此而已。

Universal Cup Season 3 Stage 7 Problem I 题解(锤子做法)

2024-08-25 23:00:57 By Kevin090228🍬

先进行一些分析。假设需要让 (a,b,c) 分别是冠亚季军,那么:

  1. a 会尽量多过题且不会罚时;
  2. c 只会过一个题,且是最后一次提交才通过;
  3. 除了这三个人之外的所有人都不过题。

更进一步的分析可以得到,b 可行的过题情况有两类:

  1. 在一次提交通过了唯一一个题,之前可能有罚时;
  2. 过了两个题,最后两发提交才通过。

预处理出每个人作为冠军和季军的罚时,称为 l_i,r_i。只需要对于所有人作为亚军时的所有可行罚时情况,统计对应的 (冠军, 季军) 对的个数即可。

注意到,亚军过一个题且罚时大于 L 的所有可行罚时中只需要保留最小的那个即可。所以可以根号分治统计所有人作为亚军的可行罚时情况。时间复杂度是 O(n\sqrt L) 的,具体地,可以 O(c^2)O(c+L) 来统计可行罚时情况。

然后计算出合法的数量。可能存在统计的时候多算冠军和季军是同一个人的情况,此时需要减掉。

查询需要减掉的情况数,本质是进行 O(n \sqrt L) 次如下询问:对于 [l,r],查询有多少 i 满足 [l_i,r_i]\subseteq [l,r]。这是一个二维数点问题,可以离线下来做可持久化分块。更简单的做法是,容易发现,这 O(n\sqrt L) 次询问中,只有 O(n) 次询问的区间 [l,r] 长度大于 20,所以可以提前预处理较短的区间的答案,对于较长的区间用主席树回答。

总时间复杂度是 O(n\sqrt L + n\times 20^2 + n\log n)。代码不是很难写,但是细节比较多。实现的时候不需要精细实现,复杂度多一点 \log 或者 20 也没卡。

关于 std:我偷看了一眼,看上去就没有根号分治,应该是 polylog 的。大概可以,每个人作为亚军时,每个提交对应了罚时情况中的一个公差为 20 的等差数列,维护出区间之后大概处理一下,可以做到 O(n\log n) 或者 O(20\times n\log n)

kenji:明天就是 NOI 笔试了,他们都在打隔膜,我该干什么呢?

2024-07-16 11:56:47 By Kevin090228🍬

杜老师,我们喜欢你

我们喜欢你呀

我们喜欢你

阿皮阿杜老师,我们喜欢你

我们喜欢,插优第歪爱吃

UNR #8 D2T2 的一个估计没有什么用的线性做法

2024-07-14 22:40:45 By Kevin090228🍬

先咕一下,闲下来写。

是我场上写的做法,只不过场上我以为它的复杂度是 O(n \log n) 状物。

中间复杂度分析的部分有大量我的扯淡,请在看中间的分析之前先跳到最后查看正确的复杂度分析。


来写一下。

由于我不会 SMAWK,所以只能随机二分,自然询问次数为 O(n\log n)

考察瓶颈所在的位置:二分提供 O(\log n),双指针提供 O(n)。由于二分显然不可能被继续优化,考察如何减少双指针的次数。我的想法是设置步长 s,每一次指针移动的时候,相比于每次移动 1 个位置,我们可以每次移动 s 个位置。

这可能会带来误差,考察误差的影响。形象的思考带步长的双指针的过程。普通双指针实际上是找到了一个分割线/轮廓线,使得左上角是 \leq mid 的数,右下角是 > mid 的数。带步长的双指针找到的轮廓线是对这个轮廓线的一个粗略近似,但是它相比原轮廓线的误差不会超过步长 s

那么我们二分再往两边递归的时候,如果想往左上递归,就将轮廓线往右下平移 s 个位置,想往右下递归,就将轮廓线往左上平移 s 个位置。这样所有当前可能成为第 k 大的位置就仍然会被包含在待确定的区域中。


分析一下这个东西的询问次数。

我场上认为这个东西仍然是 O(n\log n) 的,没有什么实质优化,所以一直在尝试调整步长 s 并对拍。现在可以仔细分析一下询问次数了。下面的分析过程不太严谨,但是感性理解足够了。

f(x) 表示当前待确定区域的左上到右下的斜向宽度(这里默认左下到右上方向的宽度为 n,显然不可能超过这个值)为 x 的时候需要的询问次数。设步长为 s,有:

f(x)=\min_{s} f\left(\frac{x}{2}+s\right)+O\left(\frac{n}{s}\right)

由于是随机二分,所以实际应该是一个概率分布,但是我正在感性理解,于是当成 x/2 计算了。取 s=\log x,进行 \log x 轮,由于 s 远小于 x,暂时忽略这个 f(x/2+s) 中的 s。那么有粗略的递推式:

f(x)=f(\log x)+O(n)

然后大概就能得出 f(n)=O(n\log^{*}n) 了。

虽然忽略 s 这个事情看上去就不严谨,但是感性理解大概能得到一个这样的结果。然后这里不一定取到了下界,所以可能还会更优。


没有分析复杂度的常数,因为这东西本来就复杂度不优。并且我分析不明白,就这样。


感觉分析其实可能是错的,如果每一步都取 s=\log x,且忽略 s 的话,只能得出:

f(x)=f\left(\frac{x}{2}\right)+O\left(\frac{n}{\log x}\right)

然后这个解出来是 f(x)=x\log \log x

请懂的人教我一下。@monstersqwq 教我一下谢谢。


其实是线性的,取 s=x/2,感谢咋克。


仔细分析各种乱七八糟的东西,最后可以得到 15.5n 的复杂度上界。哈哈,没有任何意义。

ROI 2023 简要题解

2024-07-12 11:13:29 By Kevin090228🍬

Day 1

A

行列分别处理,随便枚举一下哪个坐标转完之后最小即可。

B

一种构造方案是:将 1 看成 (0 看成 ),然后跑一个循环的括号匹配,把匹配上的右括号传过去。

第二遍把 1 看成 )0 看成 ( 做一个对称的操作即可。

杜老师告诉我,这个模型是一个 Hypercube,然后做 Hypercube 的 symmetric decomposition,找到输入集合的补集在链上的对称点即可。

C

考虑分的两个子序列,它们值域有交的第一个位置,容易发现之后一定可以取到理论上界,也就是答案为:该位置前的答案 + 满足所有元素小于子序列 1\min 的最长下降子序列长度 + 满足所有元素大于子序列 2\max 的最长上升子序列长度。

在这个位置之前,两部分值域不交,一定只有 O(n) 种情况,用线段树维护转移,每次将一个状态分裂成两个状态。对于最长上升子序列和最长下降子序列,倒着用线段树做一遍这个过程,把修改看做一些区间加,然后正着做的时候倒过来模拟这些区间加即可。

时间复杂度 O(n\log n)

D

把集合放到 Trie 上考虑 mex-极限。不妨设当前子树中有数不存在于集合中,分类讨论:

  1. 左儿子没有满:mex-极限和左儿子的 mex-极限相等;
  2. 左儿子满了,右儿子中最小的数 2^k 存在:mex-极限和右儿子的 mex-极限相等;
  3. 左儿子满了,右儿子中最小的数 2^k 不存在,最大的数 2^{k+1}-1 不存在:mex-极限是 2^k
  4. 左儿子满了,右儿子中最小的数 2^k 不存在,最大的数 2^{k+1}-1 存在:此时一次操作后会将整个子树翻转,且翻转后的左子树不满,所以 mex-极限和右子树翻转之后的 mex-极限相等。

于是容易写出 DP 状态,使用 NTT 转移。

时间复杂度 O(2^k k^2)

Day 2

A

没咋看,看上去就是简单题。

B

跑一遍 DP,保留所有起点 DP 值为奇数或偶数(选择个数较多那个奇偶性)的区间,注意在最优方案中的区间需要保留,不能让答案小于 \frac{m}{2}。正确性显然。

C

将答案转化为 n(n-1)m 减去每个人到达终点之后其他人走到检查点的次数求和。注意到检查点坐标的和不大,所以可以将其按照前缀长度 \max 分成若干段,每一段贡献其实相同。

然后随便做一下,复杂度 O(n\sqrt x)

D

给一个点点权增加 1,答案最多增加 1。于是可以从全 l_i 慢慢增加到全 r_i。每个点增加的过程中一定是一段前缀对答案没影响,剩下来的后缀每次给答案 +1。用全局平衡二叉树做修改点权,查询全局最大独立集,然后容易找出这个前缀和后缀的分界点。

时间复杂度 O(n\log n)

PKUSC 2024 最短路径

2024-05-17 17:33:23 By Kevin090228🍬

考虑从 s,t 开始双向 Dijkstra 跑最短路,直到两边经过的点集出现公共点为止,设为 p。由于数据随机,所以每个点会等概率地被 st 增广到,由生日悖论可以得出,此时经过的点的数量是 O(\sqrt n) 级别的。

考虑此时如何统计答案,容易发现会被算进答案的路径形态一定是:s\to u\to v\to t,其中 u,v 之间直接由边相连,uv 分别属于刚才的最短路过程中被 s,t 增广到的集合。该结论证明是简单的,因为如果路径形态是 s\to u\to x\to v\to t,由最短路过程的性质有 dist(s,x)\geq dist(s,p),dist(x,t)\geq dist(p,t),这样的路径必然是不优的。事实上需要特殊考虑 s\to p\to t,不过这是 trivial 的。

此时我们得到了一个 O(qm\log m/ \sqrt n) 的做法。

为了优化掉复杂度中的 m,我们对 Dijkstra 应用一个优化:将一个点所有出边按照边权排序,在松弛时不要全部同时加入优先队列,而是当上一条边出队之后再加入下一条边。这样,第一部分的复杂度就变成了 O(q\sqrt n\log n)

对于第二部分,我们枚举路径中的 u 和它的出边,去更新答案,总共需要考虑 O(m/\sqrt n) 条边。但是事实上,我们可以考虑在 dist(s,u)dist(v,t) 中较小的那一侧去枚举。若 dist(s,u)+e(u,v)+dist(v,t)\geq dist(s,p)+dist(p,t),那么这条路径必然不优。所以我们只需要枚举到 e(u,v)\leq 2(\max\{dist(s,p),dist(p,t)\}-dist(s,u)) 即可,较小的那一侧是 t 那一侧的情况是对称的。

那么这一部分总共有多少条边呢?感性理解,对于 e(u,v)\leq 2(\max\{dist(s,p),dist(p,t)\}-dist(s,u)) 的边中,满足 e(u,v)\leq \max\{dist(s,p),dist(p,t)\}-dist(s,u) 是所有在第一部分最短路过程中被处理过的边,而这两个值域恰是两倍关系,故第二部分的边数也是 O(\sqrt n) 级别的。

这个感性理解事实上有潜在的漏洞,因为涉及到的概率不一定独立。钱哥声称,第二部分的边数的上界为第一部分边数乘 O(\log n),那么第二部分的边数是 O(\sqrt n\log n) 级别的。总时间复杂度是 O(q\sqrt n\log n)

关于这个问题,钱哥有一个绝妙的证明,但是后面忘了。

共 8 篇博客