526互联

oi memory

发布时间 2024-01-07 17:19:43作者: Gemini7X

CF1817C Similar Polynomials

直接带入

\[\begin{aligned} \sum_{i=0}^{d}b_ix^i&=\sum_{i=0}^{d}a_i(x+s)^{i}\\ &=\sum_{i=0}^{d}x_i\sum_{j=i}^{d}\binom{j}{i}a_js^{j-i}\\ \end{aligned} \]

\[b_i=\sum_{j=i}^{d}\binom{j}{i}a_js^{j-i} \]

观察一些特殊值，发现：

\[s=\frac{b_{d-1}-a_{d-1}\times d}{a_d} \]

观察拉格朗日插值的式子，发现

\[[x^d]\sum_{i=0}^{d}y_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}=\sum_{i=0}^{d}\frac{y_i}{\prod_{j\ne i}(x_i-x_j)}\\ [x^{d-1 }]\sum_{i=0}^{d}y_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}=\sum_{i=0}^{d}(\frac{y_i}{\prod_{j\ne i}(x_i-x_j)}\times \sum_{j\ne i} x_j) \]

这题横坐标是 \(0\sim d\) 所以可以直接 \(O(d)\) 预处理阶乘和阶乘逆元。

CF1817E Half-sum

greedy

把数分成两个集合 \(A,B\)，且 \(A<B\)。令每个集合的数的个数分别是 \(a,b\)。令 \(A_1\dots A_a,B_1\dots B_b\) 分别有序。

定理 \(1\)

\(A\) 集合合并的顺序一定是从大往小的，\(B\) 集合是从小往大的。

应该很好猜到，但是证明需要一点推导。

大概可以局部到 \(x,y,z,w\) 四个数的情况。

几种情况分别是 \(\frac{x+y}{8}+\frac{z}{4}+\frac{w}{2}\)，\(\frac{x+y+z+w}{4}\)，\(\dots\)。比较一下发现第一种情况就是最优的。

定理 \(2\) \(\max A<\min B\)。

由于集合内部贡献的计算是固定，如果存在 \(A_i>B_j\)，显然交换会更优（\(A\) 会变小 \(B\) 会变大）。

于是我们得到一个平方做法：枚举 \(i\) 前面是 \(A\) 后面是 \(B\)，直接模拟计算贡献。Submission #212568859 - Codeforces。

不要害怕推导，考虑 \(i\to i+1\) 会发生什么？\(\Delta=\frac{a_{i+1}-a_{i}}{2^{n-i}}-\frac{a_i-a_{i-1}}{2^{i-1}}\)。

记 \(b_i=a_{i}-a_{i-1}\)。那么就有

\[\Delta_{i\to j}=\frac{b_j}{2^{n-j+1}}-\frac{b_i}{2^{i-1}}+\sum_{k=i+1}^{j-1}(\frac{1}{2^{n-k+1}}-\frac{1}{2^{k-1}})b_k \]

继续分析这个式子，当 \(i<j\le \frac{n}{2}\) 时，由于 \(2^{n-j+1}\) 较大且 \(2^{i-1}\) 较小。所以当 \(i\le \frac{n}{2}-30\)，且 \(b_i\ne 0\) 时就一定不会继续右移。右边同理。所以我们只需要 check 左右各 \(30\) 个数或者之后的第一个 \(b_i\ne 0\) 的位置即可。

Submission #212584916 - Codeforces。

CF1817D Toy Machine

注意，这个做法几乎没有用到任何归纳，以及任何套路的构造方法。也没有用到可能有用的置换群的构造，属于瞪眼瞪出来的。所以可扩展性极差。

一个很自然的想法是我们需要用到一些 LRDU 的“组合技”来让第 \(k\) 块更加靠近答案。

第一步观察，当我们的块是最中间的时候，只需要一步 DL 即可。但似乎没什么用。

仔细思考一下，我们想把一个块不断地往前挪，等价于把它前面的一个数挪到后面去。那么很自然的想法是把数卡到第一个黑格子上面，然后不让它往下走，再把它放到右边去，也就是 LDRU。

你惊喜的试了几次，发现好像不断执行 LDRU 就好了，可是当你试到后面时候发现不太行，原因是卡到了中间黑方格或后面下不来了。

现在我们还是需要往前挪，在通过一些手玩之后，还有一步比较有用的组合：LDLU。这可以把一些数卡到左边下面，这样再执行一遍 DRUR 就可以把原先的数放到等价于中间位置的那个地方了。

你又试了几次，发现太靠后的地方还是不太行，原因是会在 U 的那一步被卡住。换一种思路，把需要搞得数放到最右边，其他数卡到下边。

执行若干次 LDLU 直到它到了中间，然受执行 LDRD，把所求卡到右边下面，然后不断执行 ULDL，这样把左边上面也卡满。发现这样最后一个一定是所求的放个，最后再执行一遍 RDL。

分析一下，一开始会做 \(\frac{n}{2}\) 次 LDLU，然后会做 \(\frac{n}{2}\) 次 ULDL，于是总次数是 \(4n+O(1)\) 的。

我以为我的做法很菜，但是标算好像也是 \(4n+O(1)\) 步，那没事了。

#include <bits/stdc++.h>
using namespace std;
int n, k;
int main()
{
	cin >> n >> k;
	if (k <= n / 2)
	{
		for (int i = 1; i < k; i++) printf("LDRU");
		printf("L");
	}
	else if (k <= n / 2 + (n / 2) / 2)
	{
		for (int i = 1; i < k - n / 2; i++) printf("LDLU");
		printf("DRUR");
		for (int i = 1; i < n / 2; i++) printf("LDRU");
		printf("L");
	}
	else
	{
		for (int i = 1; i < k - n / 2; i++) printf("LDLU");
		printf("LDRD");
		for (int i = 1; i < n / 2; i++) printf("ULDL");
		puts("RDL");
		
	}
	return 0;
}