daily

每天都做了啥？

属于是要反复拷问这个颓怪了。

过水的题只有一句话题解。

UPD：打 * 的是看了没写的

# 2021-10-14

• [$\color{green}\texttt{APC001C}$]

Links

Sol:

Learn how to use binary search.

• [$\color{purple}\texttt{CF1458\ (4/6)}$]

Links

大概率是不会改到 F 了

• [$\color{blue}\texttt{LGP4748}$]

Links

考虑切 $k$ 条边，能得出 $k+1$ 个子树，故 $k+1 | n$ ，还能得出每棵子树大小 $n\over$

然后考虑切 $fa_u\to u$ 这条边，会拆出一棵 $siz_u$ 大小的子树，合法的 $n\over {k+1}$ 一定是他的因数，而 $siz_u$ 两两不同，所以对于每个 $k$ ，我们只要找倍数符合的 $u$ 是否为 $k + 1$ 就行了。

# 2021-10-15

• 把昨天 $E$ 改了。

• [$\color{blue}\texttt{CF1427E}$]

Links *

难想的数学题。

被提示后可以想到的数学题。

• [$\color{green}\texttt{CF1527E}$]

Links

一眼题。

为啥打绿，因为想撞题然后赢麻

这种分 $k$ 段的问题，十分之经典，然后就是 $dp$ 后转化大胆猜测他有一个决策单调性，然后就四边形不等式优化 $dp$ 了。

# 2021-10-17 $\to$ 2021-10-19

考试，改题

# 2021-10-20

• [$\color{blue}\texttt{CF1442D}$]

Links

注意到最终答案一定最多只有一个数组没有选完。

因为假如有两个的话由于数组是单调不降的，那你把其中一个前面不选选另一个后面一定不劣。

于是就变成了排除一个物品的背包问题，这是经典问题虽然一天前我还不会，考虑分治解决，假如一个在 $l~mid$ 中就把 $mid+1~r$ 加入背包，递归做左边，每个物品会被加入分治树–也就是 $\log$ 次。

# 2021-10-21 $\to$ 2021-10-23

考试，改题，自闭

# 2021-10-24

• [$\color{green}\texttt{LGP4978}$]

sb 题，直接做。

• [$\color{blue}\texttt{CF379F}$]

就这

• [$\color{blue}\texttt{LGP5999}$]

NB Dp!

把挨个经过的元素记做序列 $A$

可以发现：

• $A_1 = s, A_n = t$。
• $A_{i-1}<A_{i}>A_{i+1} \ \texttt{or}\ A_{i-1}>A_{i}<A_{i+1}$。

从小到大的考虑每个元素 $x$ 插入序列，放它时，$1\to x-1$ 都已经放完且一定会形成若干个满足上述条件的连续段，那我们只需枚举一下放在哪里插入，对连续段的影响就好。

由于我每次插入时是当前的最大值，所以连续段两边的意义其实就是波谷，我可以决策的是是否要作为波峰来合并两个连续段。

如何证明这样计数不重不漏？

首先这样计数每个排列都是符合题意的，然后对于每个排列我们都可以从最小的开始依次还原操作。。。。
啊啊啊不是很懂

• [$\color{purple}\texttt{CF702F}$] *

可以想到的 DS ，大概方向上是对了，但平衡树不太熟了。

大概是，你暴力就是对每个人依次看每个物品，那你考虑每个物品的贡献，按质量从大到小排，它肯定是，能买的下的人造成 $1$ 的贡献，然后问题转换为每次把大于 $c$ 的数字减去 $c$ ，问每个数字被操作的次数。

这个可以用平衡树做，具体的，你把平衡树分为三个区间 (0,C), [C,2C), [2C, \infity] ，然后只对第二个区间暴力修改，对第三个区间打 $tag$ 解决，然后利用势能分析，这玩意是对的

# 2021-10-25

• [$\color{red}\texttt{AGC099C}$]

简单贪心

• [$\color{red}\texttt{CF1602A}$]

sb 题

• [$\color{red}\texttt{CF1602B}$]

sb 题

• [$\color{green}\texttt{CF1602C}$]

每位 $1$ 个数的 $gcd$ 的因子就是答案

• [$\color{green}\texttt{CF1602D}$]

做个线性 $dp$ ，用 $SGT$ 优化这个过程

注意转移顺序

# 2021-10-27

• [$\color{blue}\texttt{CF521D Shop}$]

神奇贪心

• [$\color{blue}\texttt{CF734E Anton and Tree}$]

有趣树论

都是 ZROI 搬的题。

• [$\color{blue}\texttt{AGC099H}$]

这种跟完全图有关的东西可以想想补图。

在这题中，拆分为两个完全子图放在补图上就是选出两个点集，内部无边。

不难发现这是一个二分图染色的要求

然后使用 bitset 优化一个背包，设选出的一个合法点集大小为 $x$ ，那答案为 $\binom{x}{2}\times \binom{n-x}{2}$ 。

• [$\color{blue}\texttt{AGC099I}$] *

这个指针移动可以转换成对 $hash$ 值做一些事情。

然后在 $map$ 上搞一下。

• [$\color{blue}\texttt{BZOJ4543}$]

长链剖分优化 dp

• 今天考试挂了 60pts ，十分自闭。

• 感觉晚上效率不够高。

# 2021-10-28

• [$\color{purple}\texttt{WC2010 重建计划}$] *

首先这个带除法的形式可以分数规划。

然后我们要求的就是树上边数 $\in [L,U]$ 的最大路径长

这个可以套路地上淀粉质做

也可以长剖优化 dp

考虑最 naive 的 dp, 设 $dp_{u,j}$ 表示 $u$ 子树往下走 $j$ 条边的最大权值和

这个暴力 $\mathrm O(n^2)$ dp 不难

然后我们优先做长儿子，记录 dfs 序，可以发现每条长链 dfs 序都是连续的，然后我们就可以把 $dp_{x,i} 放到 $dfn_x + i$ 这个 SGT 上，就可以快速从长儿子合并了

# 2021-11-8

• [$\color{red}\texttt{ARC120A}$]

• [$\color{red}\texttt{ARC120B}$]

可以构造发现斜率为 $1$ 的对角线必须相同，然后就随便做了。

• [$\color{blue}\texttt{ARC120C}$]

有趣的题。

首先和不同直接无解，因为交换并不改变总和。

进一步考虑，可以发现一个精彩的结论，令 $a'_i = a_i + i$ 发现你咋换，这个值都不变

想到了证明还是很简单的，于是你就可以知道那些可以匹配了，要构造最短次数想到那个经典逆序对的结论，然后搞搞就好。

• [$\color{blue}\texttt{ARC120D}$]

若排序后前一半后后一半匹配，这样答案最大。

然后考虑构造成立

使用一个类似括号序列的东西就可以了

• [$\color{black}\texttt{ARC120E,F}$]

不会

• [$\color{red}\texttt{ARC125A}$]

简单题

• [$\color{green}\texttt{ARC125B}$]

有趣题。

首先可以转成统计 $x^2-y^2=a$ 其中 $a\in [1,n]$ 。

那把完全平方数序列画出来，就是在其中统计两个数之差满足限制

考虑差，那就差分一下，发现问题转为在一个差分数组上求一段连续区间使得和满足条件。

完全平方数序列的差分序列是个等差数列

然后你把每个长度的区间和写出来，发现也是等差数列，首项还是个完全平方数。

然后你就做完了。

# 2021-11-9

• [$\color{blue}\texttt{ZROI2136}$]

感觉这种遇到 $np$ 问题一定要想想与原问题的区别，毕竟相信出题人与其搞你不如去拿个菲尔兹，有助于想出题。

这题的关联就是 $k$ 是 $1e6$ 级别，直接枚举是可以接受的

于是你考虑从最小团开始每次新增一个点，使用 $\texttt{bitset}$ 即可快速判断是否还成团，用个优先队列维护一下就好。

注意到这样无用状态过多，空间开不下，于是把权值排序后，每次只拓展两个点，一个是把当前最大的消掉换个更大的，一个是直径加个当前最小的。

• [$\color{blue}\texttt{ZROI2137}$]

由于并没有改完题就没有新开一个 $test$ 了。

可以证明最终答案中出现的序列每个元素只可能是它能影响的 $3$ 个中位数之一。

每个位置只有常数个选择这激起了我们的 $dp$ 欲望，于是考虑设 $dp_{i,j,k}, j\in [1,3], k\in [1,3]$ 表示当前决策到了第 $i$ 个位置，第 $i-1$ 个位置选择第 $j$ 个数字，第 $i$ 个位置选择第 $k$ 个位置的可行性，记录一个 $nxt$ 方便构造解即可。

• [$\color{yellow}\texttt{ARC111A}$]

由于意识到一起床就听讲题效率不够高，总是需要重播于是在 $14:00\to 16:00$ 来了一场 $vp$，感觉自己还是菜的离谱

虽然这题很简单但我第一遍没做出来于是还是推一遍柿子。

$$10^n = \lfloor{10^n\over m}\rfloor + r$$

记 $k=\lfloor{10^n\over m}\rfloor$，

$$k=a\times m + r'$$

$r'$ 即为所求，于是代入：

$$10^n = a\times m^2 + r'm + r$$

注意到 $r'm+r$ 相当于是 $10^n$ 膜 $m^2$ 的余数，而 $r<m$ 所以有：

$$\lfloor {r'm + r\over m}\rfloor = r'$$

• [$\color{yellow}\texttt{ARC111B}$]

反着考虑每种颜色是否能出现到答案中，可以把一对颜色连条边，每条边表示两端只能取 $1$ 。

对于每个联通块，若为一棵树，贡献为 $siz-1$ ，否则贡献 $siz$.

• [$\color{green}\texttt{ARC111C}$]

有一个 $trick$ 已多次使用，那就是对于一个排列，$i\to p_i$ 这样连边，一定能连出若干条环。

这题也是一样，对于每个联通块（一定是一个环），在环中使用 $a$ 最大的一个人当工具人用它帮助其他人。

• [$\color{green}\texttt{ARC111D}$]

考虑一条边 $x, y$ ， 一定是 $c$ 大的连 $c$ 小的，因为若反过来的话 $c$ 大的点能到的点小的一定能到，就 $GG$ 了。

对于 $c$ 相同的边，我们建出图来，由于一定有解，这些边构成的每个联通块一定是一个个环，然后任意定向即可。

• [$\color{blue}\texttt{51Nod 1598}$] *

别被演了！！！

!$\sum |k_ix+b_i|$ 就是坑人的，把你引到二维上，实际上，考虑一对绝对值之和取最小，有个经典初中几何意义是数轴上一堆点取一个点到其它所有点的距离最小。

那这个柿子可以变成 $\sum |k_i| |x+{b_i\over k_i}|$ 是个带权的问题，可以看做在 $b_i\over k$ 出撒了 $k$ 个点，离散化一下考虑维护区间中位数和距离和，可以用线段树上二分解决（？） 没写

• [$\color{purple}\texttt{大吉大利今晚吃鸡}$]

见题解

# 2021-11-10

云了套联考题～

• [$\color{black}\texttt{KT1 NOIP2021}$]

• [$\color{black}\texttt{ZROI Day17}$]

• [$\color{blue}\texttt{CF372D}$]

二分然后 172E

# 2021-11-16

• [$\color{blue}\texttt{zroi446}]

数独的奇异性质。

对于每种 $1$ 的排列，对应的数独最终局面数是相同的。

枚举多少种合法的放 $1$ 的排列即可得知当前局面数与总局面数之间的比例。

总局面数怎么算？通过样例可以反推。

• [$\color{blue}\texttt{zroi447}$]

直接最短路即可。

注意处理路的边权时的一些细节。

# 2021-12-25

• [\color{}]

# 2021-12-26

• [$\color{red}\texttt{CF109C}$]

把 $\texttt{lucky edge}$ 拆开，然后是个简单计数题。

• [$\color{red}\texttt{CF432C}$]

哥猜一下。