2025 年 10 月日祭

Codeforces Round 1055 (Div. 1 + Div. 2)

Link

我好菜。

• D - Division Versus Addition

  赛时比较早就想到了大概的做法，但是没写（？）。首先发现 的数显然没有贡献（操作它则严格不优），而其它数是可以有贡献的。但是观察样例发现 可以没有贡献，即满足 的 ，若 A 先操作一次，那么这个数就没有贡献了；而对于其它数，就算 A 操作了也依然可以有贡献。对于上述这类数，A 可以让其中的一半（向上取整）取消贡献。所以答案就应该是原本的操作次数 + 有贡献的数的数量 - 特殊数的数量的一半向上取整。

• E - Monotone Subsequence

  好难绷的题。第一次考虑对于全局询问，如果答案序列的长度 直接返回。然后你发现要是再询问答案序列中的元素好像没什么用，所以下一次就询问除它们以外的元素。于是这样询问 次，如果中途答案序列长度 就直接返回。如果 次之后依然没有答案，那么现在一定还剩下一个元素。考虑构造一个下降子序列。发现对于一个在第 轮中被询问的元素，在它左侧一定存在一个在第 轮中被询问的元素，且这个元素一定比它小。所以从剩下的元素中的一个开始，每次向左找第一个上一轮被询问的元素，即可构造出答案。

多校联考 20251007

Link

• B - 中心极限定理

  我唐。发现难点在于把马吃了怎么处理，于是考虑状压一下当前位置前几步即可。

• C - 散步

  将题面稍作转化，变成：给定一个无向联通图与偶数个关键点，要求将关键点两两匹配并选择一条路径，使得任意两条路径（边）不交，构造方案。发现这个问题在树上就可以做。对于一棵子树，它最多有一个点未被匹配。于是对于一个节点，先将它子树中剩下的点与它本身（若有）两两匹配，最后最多剩下一个点，将这个点传递给父亲即可。

多校联考 20251008

Link

• B - 围棋

  赛时死磕导致根本没看 T3 和 T4。以后再死磕我是狗。

  发现难点在于翻转一个白棋，因为翻转后可能会新增一些死的白棋。发现这个东西差不多是割点，于是跑塔尖即可。另外集中情况分讨一下即可。

• C - 相互抵消

  化简发现原式至于 与 有关，维护即可。

多校杂题选讲 20251010

Link

• A - 帐篷

  凭啥我只会 。设 表示格子大小为 时的方案数，考虑横着一组占用一行两列，竖着一组占用两行一列，单独一个占用一行一列，直接转移即可。

因为一些原因后面的就不写了。

多校联考 20251011

Link

美好的一天从饭堂开始。

• A - 询问

  发现 5 次询问之后就是 ， 了，矩阵快速幂即可。话说我赛时写了个什么神秘 的分块做法？

• B - k-绍兴序列

  分讨一下就做完了，倒着 DP 即可。赛时为啥我要正着 DP？

• C - 二次根式

  什么猎奇打表题。发现 所以只用计算 。对于 ，枚举 以内的质数计算贡献即可。发现需要快速阶乘但是又发现模数固定，于是打表即可。

Codeforces Round 1058 (Div. 1, Div. 2)

Link

Div. 2 Rank 8，紫名祭。

只能说是前一天晚上睡太好了，这天晚上状态好。要是我每次晚上状态都这么好 2200 也不是不可能。

• F - Twin Polynomials

  赛时做这题的时候有点飘了，要是我认认真真手模一下样例说不定真能场切。

  容易想到对于 连边并考虑图的性质。发现对于每个点（除 号点外），要么向 号点连边，要么形成自环，要么属于一个二元环。特别地， 号点不能向 号点连边。容易举反例证明这一点。于是考虑先把图建出来，判断一下是否合法。接下来，只需要考虑剩下的点，并进行一个 DP。设有 个点时有 种分配方案，那么 ，初始状态是 。如果是 号点那么需要特判一下。于是就做完了。

  赛时先是认为图是由若干个环组成的（不一定是二元环或自环）于是耽误了好久。后来想到了这一点，可是又没想到可以向 连边，又没有静下心来手模样例，于是 5 题 rk 8 遗憾离场了。

• G1 & G2 - Inverse Minimum Partition

  好神的题。Solution。

  值得一提的是，BINYU 自己把这道题改出来了，然后他又给 Zi_Gao 讲了，然后我又参考了他们的代码。直到我写题解的时候，才发现这个做法是假的，然后把我们三个 hack 了。

多校联考 20251014

Link

除了之前没有区分度的那场之外考得最好的一场。

并且获得了 1.25 瓶冰红茶。

只能说还在稳定开挂吧，之前 的运气还没用完。

• A - Happy · Lovely · Everyday!

  每次选择相邻的两个异或听起来比较困难，所以考虑转化一下，将原序列分成若干个子段，让每个子段变成这个子段的异或和。依然感觉不是特别能发现性质，于是考虑如果已知最终状态，如何判断合法，发现是贪心判断，那么这道题的做法就比较显然了。初始状态为 ，每次 可以转移到 ；若存在 使得 是 右侧第一个满足 的位置，那么 还可以转移到 。若 的异或和为零，那么将 累加进答案即可。其实挺唐的，主要还是没改掉赛时喜欢乱猜结论的坏习惯导致耽误了好久。

• B - 敬启，致那时的我

  虽然按理来讲这题应该评蓝（因为矩阵快速幂都是绿）但是我觉得 B < A。

  发现斐波那契数列实在是一点性质都没有了，popcount 相同的数对应的斐波那契值也是一点性质都没有，于是想想关于计算斐波那契数列的第 项还有什么做法，于是显然只能想到矩阵加速。你发现矩阵满足结合律与分配律，于是这道题就做完了。设 表示考虑到第 位，填了 个 ，当前值是否等于上界 时的答案。直接转移即可。

• C - Lead to shine more

  好奇我赛时是如何切掉这题的。

  先观察一下，发现能走的路只有倍增这一条。一个天真的想法是，设 分别表示初始 ，达到 所需要的步数以及总步长。发现无法转移，需要添加 这一维表示初始 。发现还是无法转移，需要添加 这一维表示每次更新是 。然后就可以转移了。对于每次询问，发现高位是容易处理的，然而低位不容易。所以用倍增处理出高位，留下最后 位直接暴力地推即可。

  值得一提的是，赛时代码中我不小心让下标出现了 ，导致 CWOI 上挂完了。幸运的是，虽然本地测试也用的 Linux，但应该是因为环境不同，本地并没有挂。赛时我其实注意到了那里会出现 ，但是 Windows 上没挂，我也没有意识到它会被作为下标，就忽略了这个问题。总之还是不够严谨导致的，而且在 NOI Linux 上测一下样例也是很有必要的。（这段话好人机。）

多校联考 20251015

Link

• B - 捐赠

  两只 跑得快，甚至 草过了 。

  正解显然是一只 的。你会发现 A 选的个数与 B 没选的个数之和恰好是 B 的个数，下文记作 （废话），那么转化一下，对 B 物品的权值取相反数，那么答案就是选权值前 大的物品，再加上 B 物品的权值和即可。

• C - 染色

  不错的树上启发式合并题，可是我并不会。

  然后写日祭的时候发现一车人的启发式合并是假的，包括我。当然如果精细实现也能过，但是我不想改了。

多校联考 20251021

Link

BINYU Zi_Gao Rong7 模拟赛，内部提前到了 20251017 考。

A 是唐，C 的 分只用发现 （ 表示斐波那契数列的第 项），其它不会。

多校杂题选讲 20251017

Link

不想写。

多校联考 20251018

Link

紫紫黑黑 NOIP 模拟赛。

不想写。

并非多校联考 20251021

Link

运动会，没打。

多校联考 20251022

Link

• A - 石头人

  因为没判 导致挂分。

• B - 炒鱿鱼

  要求在一种特殊图上对图进行三分图染色。

  做法是，直接 dfs 染色，但是优先遍历编号大的点。至于为什么是对的我也不知道

  赛时因为有点细节问题导致挂分。话说这个构造甚至我最后 20min 想出来的。

• C - 适格者

  纯唐。

多校联考 20251025

Link

• A - 剖分

  唐氏树形 DP / 贪心。

• B - 海啸

  不带修是 ARC201B。

  带修也是好做的，维护一下当前每一“层”中的元素即可。

并非多校联考 20251027

可是牢祝依然算了这场的成绩。

Link

• A - 大骑士领一瞥

  分讨题。

• B - 流放阿卡胡拉

  注意到路径一定是 ，其中 或 是质数。然后你发现，我们只需要关注以 为右下角的一个矩形中的 ，所以在矩形中跑暴力 DP 即可，矩形长宽取到 就行了。虽然不知道哪里来的正确性，但是靠感觉它就是对的。

多校联考 20251028

Link

• A - 排序

  唐。

• B - 重排

  唐。

多校联考 20251029

Link

• A - 初恋

  唐。

• B - 奥瑟罗

  没我唐。随便乱维护一下即可。

CSP-S 2020 并非 VP

• A - 儒略日

  屎。

• B - 动物园

  屎。

• C - 函数调用

  好。没一眼秒的原因是没有注意到加乘可以转化成加和全局标记乘，也没想到正难则反。我咋这么唐。

  后来一直写挂的原因是，拓扑时理所应当地只加了 号点，也是糖丸了。包括记忆化搜索的时候，应当令初值为 ，因为乘数可能为 。

CSP-S 2021 并非 VP

• A - 廊桥分配

  唐。

• B - 括号序列

  唐。

• C - 回文

  屎。

CSP-S 2022 并非 VP

• A - 假期计划

  好。你发现如果我们确定了 和 ，那么就可以贪心地选择 和 ，其中 需要满足从 与 均可达， 同理。于是我们可以 预处理出可达关系，与对于一个确定点，有哪些点可从 与它可达。接下来，枚举 和 ，贪心地选择最优的 和 。发现 和 可能会和其它点重复，于是考虑放缩一下。容易发现我们只关注前 大的 和 ，于是预处理的时候求出前三大的即可。

• B - 策略游戏

  唐。

CSP-S 2023 并非 VP

• A - 密码锁

  唐。

• B - 消消乐

  唐。难点在于证明时间复杂度。

• C - 结构体

  屎。

CSP-S 2024 并非 VP

• A - 决斗

  唐。

• B - 超速检测

  屎。

• C - 染色

  唐。这题咋跟 Chicken Jocky 一模一样啊，虽然自己还是瞪了好久，还因为饭堂调了好久。