2023.01.05

已经想不出标题了，今天就是atcoder瞎做（把之前的部分也补上）

但其实有的题可能不是今天（指2023.01.05做的）。

今天没有模拟赛所以早上又睡过去了，好想有规律的作息啊啊啊啊。但是明早又有模拟赛，一打就一天没掉，吐血。不过好像就算不打比赛也干不了什么。

感觉atcoder的题目锻炼思维是真的可以，感觉不是很难的算法的题但是思维却不是很好想。通常做完都会有一种恍然大悟的感觉。

ABC260G

化一下式子得到 \(2u+v<2M+2s+t\)，也就是说对于一个 piece，我在 \(2M+2s+t\) 这个加一，然后对于一个位置 \(X_i,Y_i\)，只需统计大于 \(2X_i+Y_i\) 的个数即可。但这样有一个问题，就是前两个条件没有满足。

三维偏序，我会 \(O(N^2\log ^2n)\)。

官方题解给到了一个更妙的做法，假设我们现在在做前缀和，那么我们想要的情况其实是这样的：

+.........-
+.......-..
+.....-....
+...-......
+.-........

这个直接分成两个部分，第一个部分是正常的列前缀和。

第二个部分这么做前缀和：\(s_{i,j}+=s_{i-1,j+2}\)。这样就可以差分了。

复杂度 \(O(N^2+NM+Q)\)。

提交记录

ABC260Ex

nb题。

先转换为计数恰好有 \(n\) 个不同相邻小球的方案数记为 \(g_n\)。然后答案就很好算了 \(f_k=\sum\limits_{i=0}^{N-1}i^kg_i\)，将其看做生成函数，有 \(F(n)=\sum _{k\ge 0}\sum\limits_{i=0}^{N-1}i^kg_ix^k=\sum\limits_{i=0}^{N-1}g_i\sum_{k\ge 0}i^kx^k=\sum\limits_{i=0}^{N-1}\frac{g_i}{1-kx}\)。这个东西呢是可以分治 ntt 然后复杂度就是 \(O(n\log^2n)\)。

接下来考虑如何计算 \(g_n\)。

二项式反演后，考虑计算 \(q_n\) 代表钦定 \(n\) 对相同的相邻小球的方案数。设颜色 \(c\) 的小球一共有 \(m_c\) 个。

AGC024B

显然答案不超过 \(n-1\)，方法也很简单就是固定一个数，然后把剩下的部分按顺序放到后面。那显然有的时候不需要动，也就是一段连续的值。于是我们求出最长的一段连续的值即可。

code

AGC018B

贪心，先假设所有项目都有，然后找出最大的那个把他删掉。对于每个人维护一个指针，这样子的复杂度是 \(O(nm)\)。

code

AGC017B

挺有思维难度的题，我一开始想的是维护区间，但是发现这个区间指数级增长根本维护不了。考虑换一种角度，我们记录差分数组，即要求每个值在 \([-D,-C]\cup [C,D]\) 中。而又差分数组的和是 \(B-A\)，你不妨设有 \(i\) 个位置的差分是负数，那么就有 \(C*(n-1-i)-D*i\le \sum d_i\le D*(n-i-1)-C*i\)，那么只要这个满足，很容易用调整法调整成合法的序列。

code

AGC004B

同一个颜色是可以抓多次的，而魔法的使用次数可以等价于使用最多的那只，所以可以枚举魔法使用次数，而每个动物可以在其魔法可以到达的范围内选择最小值。

code