CSYZ集训题总解

发表于 | 更新于 | 分类于 | 阅读次数：

回来补一个前言

承蒙老师厚望，第一次出省参加集训（其实也就是和CSYZ的大佬做题。。。）其中不乏有很多不错的题，难度适中，解法自然，也可以回来经常看看温故知新。

第一天的难题（数论）

第一题第二题巨水便不多赘述，第三题肝了我三小时最后还是交了暴力上去。。。

极其具有思维性，写此文以记之。

首先由小学奥数的追及问题（以下所有公式中数组均已排序）：

设两人速度差$delv=v_j-v_i(i<j)$，一圈的距离为$a$则第一次$j$追上$i$是在$fir=a/delv$时候，设速度最大的为$V_m$，则总时间为$T=a*l/V_m$。

于是对于$i,j$两人，追及的次数即为$T/fir=a*l*delv/V_m*a=l*delv/V_m$。其中$k=l/delv$是固定的，于是求出
$$\sum \limits_{i=1}^{n-1}\sum \limits_{j=i+1}^nfloor(k*delv_i^j)$ $=ans$$

便成为我们的目标。我是这样想的结果那个$floor$函数怎么都推不出来，$O(N^2)$50%滚粗。

先回归最纯真的式子 ($[A]$不超过A的最小整数，{$A$}为A的小数部分)：

$$\sum \limits_{i=1}^{n-1}\sum \limits_{j=i+1}^n[l*(V_j-V_i)/V_m]$ $=ans$$

对于现在的我们，在经过大佬的熏陶后可得到这样一个公式：

  • $[A-B]=[A]-[B]+[${$A$}$-${$B$}$]$
  • $A/B=(B*[A/B]+A$%$B)/B=[A/B]+(A$%$B)/B$ （这个好推，只是要用就写了）

对于最上面的式子，可变形：

$$\sum \limits_{i=1}^{n-1}\sum \limits_{j=i+1}^n[l*V_j/V_m-l*V_i/V_m]$ $=ans$$

—由公式（1）—–>

$$\sum \limits_{i=1}^{n-1}\sum \limits_{j=i+1}^n([l*V_j/V_m]-[l*V_i/V_m]+[${$l*V_j/V_m$}$-${$l*V_j/V_m$}$])$ $=ans$$

—由公式（2）—–>

因为$[A/B]$一定是个整数而且是最大的，所以$(A$%$B)/B$一定是他的小数部分。

$$\sum \limits_{i=1}^{n-1}\sum \limits_{j=i+1}^n([l*V_j/V_m]-[l*V_i/V_m]+[(l*V_j$%$V_m)/V_m-(l*V_i$%$V_m)/V_m])=ans$$
就此得到了最终的式子_(:з」∠)_。

  • 先分析前面一部分。

设$k_i=[l*V_j/V_m]$，则原来的式子可变形为：

$\sum \limits_{i=1}^{n-1}\sum \limits_{j=i+1}^nk_j-k_i$，由和式变换（其实就是观察法）可得：
$$\sum \limits_{i=1}^nk_i*(2*i-n+1)$$

为什么呢？

对于任意$K_i$，可以发现它对答案的贡献要么放在式子前是加上，要么是放在式子后减去。

那么对于$i∈[1,j-1]$的区间，$k_j>k_i$加上。而当$i=j$时$k_j$均被减去，为$n-j$次，所以对于一个$k_i$，它的贡献总值就是$(2*i-1-n)*k_i$

  • 对于后面的分析_(:з」∠)

$[(l*V_j$%$V_m)/V_m-(l*V_i$%$V_m)/V_m]$，这种东西一看就不会搞啊_(:з」∠)

但是显然的是，式子的两项都是一个在$[0,1)$区间的小数，所以他们的差值要么是正的，要么是负的。]QwQ没想到]

对于正的差值，还是个小数，贡献当然是0_(:з」∠)_；对于负的差值，是一个负的小数，但向下取整就是$-1$了，对答案有贡献。

所以答案就是问你有多少种$(l*V_j$%$V_m)/V_m-(l*V_i$%$V_m)/V_m<0$的情况嘛，变形得$(l*V_j$%$V_m)<(l*V_i$%$V_m)~~(i<j)$

还是看不清楚啊_(:з」∠)，那就设$B_i=l*V_i$%$V_m$，变形为：

求$B_j<B_i$的个数，其中$i<j$。

逆……逆序对？怎么就变换成逆序对了？？一个好端端的数论怎么就是逆序对了？？？

然后……就没有了，考完花了2小时打了程序，疯狂$WA$，原来被卡了精度，double存不了但是直接在答案中计算稳如老狗，感受到CCF官方的恶意。

愉快的第二天！

被$Nerlci$坑了,明明8：00考试听他说8:30才考，于是到场的时候大佬都应该打了T1暴力了_(:з」∠)_。

第一题（矩阵加速）

被$CSYZ$大佬们嘲讽是入门题，蒟蒻自学矩阵加速感到十分惊慌。

但为了让一些考场上没看出来的孩子们方便理解原理，还是重头分析一遍吧（也是为了我自己）。

首先是个人都会打这道题的暴力（简化版）：

1
2
3
4
5
6
7
int dfs(int n)
{
	int ans=0;
	if (n==0) return 1;
	else for (int i=1;i<=min(n,m);i++) ans+=dfs(n-i);
	return ans%mo;
}

如果你加一个记忆化就可以得到70分，就会很容易看出来这是一个斐波拉契数列的变种，即：
$$F_i=F_{i-1}+F_{i-2}+…+F_{i-m}$$

对于这个式子，一开始没想起来矩阵加速怎么写的蒟蒻我来说，当然就可以直接打一个滚动数组优化DP了，70–>85，性价比还是挺高的。

经过手机查看仔细考虑，搞出了一般斐波拉契的加速矩阵：
$$\begin{bmatrix}0&1\\1&1\end{bmatrix}*\begin{bmatrix}F_{1}\\F_{2}\end{bmatrix}=\begin{bmatrix}F_2\\F_1+F_2\end{bmatrix}$$

打完$m=2$就跑了，但最后半个小时检查的时候发现通项式也很好推。
$$\begin{bmatrix}?\end{bmatrix}*\begin{bmatrix}F_{1}\\F_{2}\\F_3\\
…\\F_m\end{bmatrix}=\begin{bmatrix}F_2\\F_3\\
..\\F_1+F_2+..+F_m\end{bmatrix}$$

矩阵的项处于$i$行时：

  • 若$i<m$,是他的下一行元素。
  • 若$i=m$，是所有元素和。

所以构造出的矩阵$(M*M)$就是：$$\begin{bmatrix}0&1&0&…&0\\0&0&1&…&0\...\\0&0&0&…&1\\1&1&1&1&1\end{bmatrix}$$
跑一边矩阵加速就好。

十年$OI$一场空，不开$LL$见祖宗。

有大佬问我初始的$F_1->F_m$怎么求？这不就是序列前m项吗，递推求一下即可。

第三题（树，分治，贪心）

第二题是一个类似$NOIPD1T2$时间复杂度的题，单纯靠码力，不多赘述。

第三题被我校老师的卷子押中了，但是时间关系没能打完，只好打了一个暴力滚粗（暴力分正解居然是树上$Floyd$，我打了一个暴力判点+LCA，暴力分都没有。。。）

题目简化：在一棵点权树上找两个点，使其他所有点到其中任意点的最小的点权距离和 最小

再说白点，就是一棵带权树上找两个重心使距离最小。对于一个重心的话可以通过递推模拟$O(N)$时间求出。大概就是这样

现在变成了两个点，那不就不会做了嘛我们就考虑能不能通过求出两个树的重心，累加为答案呢？

我们可以分治将一棵大树通过一条边分成两棵小树，对于一个小树求他的重心，可以证明对于答案一定可以有最优解。

对于贪心证明：

  • 因为如果对于一棵子树的节点到另一颗子树的重心最优，那就应该把这个点接到另一个子树里面了，还是只有两棵树。

我们枚举断哪一条边分成两棵树，每次都求两次重心，复杂度$O(N^2)$，期望50~60.（貌似不能每次重建树？炸成40了）

但是还有一个小优化：对于一棵树的重心，如果查询的时候越偏向那边，答案就会越小，反之则会越大（显然的吧）

而且一棵树的重心只有一个，不就等价于对于树的任意一点，只有往重心偏向时才能使答案更小吗？

UPDATE:当n为偶数时最多会有2个重心，且相邻。

于是对于每一次重心答案的更新，只需要判断新旧答案的关系，若变小则继续搜索，若变大或不变就不管它。当往任意一个点走都不能使答案更优，那个点即为重心。

于是我们直接建一个树，枚举每一条断边的情况，在对两个子树跑一边$O(LOGN)$的搜索即可。

但是由于只建了一棵树，必须要考虑以原来根为根节点的情况：为什么呢？

如图，我们现在断掉AC边计算两个子树的贡献，对C为根而言没有变化，但是对于A来说他从中扣去了C子树对其的贡献，直接调用答案就会爆炸。
所以还需要去掉C子树的贡献,通过玄学理解思考，结论就是：

  • 当重心路径不往被删边方向走，贡献：$ANS_B=ANS_A-SIZE_B+(SIZE_A-SIZE_B-SIZE_C)$
  • 当重心路径往被删边走，贡献：$ANS_B=ANS_A-(SIZE_B-SIZE_C)+(SIZE_A-SIZE_B)$

然后就没有了，初始值一定要开INT_MAX,不然答案就爆了。

不愉快的第三天

明明很简单的题目但还是爆炸了。。原因主要还是对代码的理解，一些板子类的东西就是一点小细节才WA了。

第一题（数论）

是一个很简单的组合数问题（答案是$C_{n-k}^{m-1}$），拿到题的我花了$1min$推出来公式，$10min$调了逆元$O(N)$板子，结果忘了把逆元求阶乘硬是肝了$40min$。。

以前写过的小结硬是漏了递推逆元的推导，看来什么知识点都不能疏忽啊。。

没有特判只有90。

第二题（动规）

75分那么水居然会因为板子打错炸了！
权值线段树记录的时候查询没有查到1000而是查到$n$，被炸成傻逼_(:з」∠)_。
就是一个裸的$LIS$，正反两边即可75.

100分的话原来以为可以贪心求LIS路径，手膜几个数据感觉是对的苦于没有对拍程序，不然瞬间被$HACK$_(:з」∠)_

如果正解不是$LIS$，那新的式子是什么呢？

先可以考虑设$f[i]$为到第i个元素均不下降所需要的最小花费，但是经思考可看出后面的元素只能选择前一项为答案，不然就有后效性了。

但是我们发现$a[i]$数组离散化后很小，也可以进行转移，于是考虑设$f[x]$为最后一人的高度是$x$时所用的最小花费。
式子当然也根据当前$a[i]$大小而定：

  • 若$(a[i]<x)$，则一定要往上调整$,f[x]=f[x]+m1$;
  • 若$(a[i]>=x)$，则$f[x]=min(f[a[i]],f[x]+m2)$，即可以不更改，直接转移或者改为$x$的大小。

为了保证序列单调，倒序枚举每一个$a[i]$判断他的贡献，然后就没有了。

答案要正反搜两遍，改一下枚举$a[i]$循环即可。正解多了一位，但是可以滚掉

第三题

大模拟，暴力打的好可以80，正解的话要分治一下，抄了一下过了考试的时候肯定不会打的

五味杂陈的第四天

心里感觉就很难受。。明明第一题那么水却因为没有输出$-1$，$WA$了好几个点；第三题数组开小而且没开$long~long$硬是把$50->15$，总是在这些小细节上爆炸吃枣药丸的。

但幸运的是$CSYZ$的大佬们好像不是很会搞T2的样子，类似的排序题最近做了好几道，上来先推个$1.5h$式子，再根据记忆搞对了（无良出题人卡scanf），所以幸运的拿到了$RANK~5$（之前没有说成绩都是因为没进前十不敢说QwQ）。

$ouuan$发挥出了应有的实力，太强辣QwQ！

第一题（模拟）

大模拟，没啥好讲，最后检查时发现边界没判，不然WA更多。

第二题（排序的$cmp$更换）

排序题，无良出题人出的是原题，详情请见皇后游戏。

第三题（贪心？，数据结构）

终于出了一道最质朴的数据结构题了！

先强烈谴责出题人！50分的部分分居然给$O(NLOGN+M*NLOGN)$过了！！（每次修改完再求一次逆序对）

明明应该是$O(NLOGN+MN)$的优良算法，结果时限三秒，上面的暴力查询修改居然也水过了！那我推式子跟放个屁有啥区别_(:з」∠)_

当然要是想要写正解的话不推一下单次修改的$O(N)$是不行的，本蒟蒻想到了维护最小值修改但是因为每次找一个都求一下感觉会超时所以没敢打（后来CYJian大佬过来说道每个元素修改只会一次时恍然大悟_(:з」∠)_）

整理一下蒟蒻考场上推每次修改$O(N)$的原理：

  • 对于在$p$之前的元素，由于只对他们后面的元素有影响，所以逆序对个数不变。
  • 对于$a_i(p<=i<=n,a_i>a_p)$，易知道对于比他小的元素重排序，排完还是比他小，所以也无变化。

于是只要找到$a_p$之后比$a_p$小的数，直接减去他的逆序对即可。

考场的时候一直想直接沿用求逆序对离线的方法，存储大小为x的逆序对个数并直接修改，但询问明显是在线的，所以我就脑子抽了。。

明明直接存储对于第i个元素的大小，逆序对个数，每次暴力找p之后比$a_p$小的元素直接一个一个减掉即可，但是觉得一个一个减是不是很慢所以又不敢打，又想推推其他的式子，搞得暴力都没时间检查。。

$NOIP$考试难度稍微比这套卷子难一些，对于正解一时想不出来的题，打好暴力并保证暴力无误很重要，不然最后正解也没写哭都哭不出来_(:з」∠)_

爆弹，然后再见（$DAY5$）

第一题

一个裸的不能再裸的DP题硬是被说成了图论？$BFS$？不是很理解大佬的脑回路。

严格来说应该是递推（怎么又是递推）搞出来的，设$f[i]$为从n到i的最小步数，则显然$f[n]=0$。

  • 对于$i<n$的点只能$f[i]=f[i+1]+1;$
  • 对于在n之后的点可以$f[i]=min(f[i/2],f[i-1])+1;~~(i$%$2==0)$
  • 有可能跳过去了所以往回走试试，$f[i]=min(f[i],f[i+1]+1);$

算了。。还是上代码吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <fstream>
#include <cstring>
using namespace std;
int n,k,f[500000];

int main(){
	cin>>n>>k;
	memset(f,0x3f,sizeof(f)); f[n]=0;
	for (int i=n-1;i>=0;i--) f[i]=min(f[i],f[i+1]+1);
	if (k<=n) {
		cout<<f[k]<<endl; return 0;
	}
	for (int i=n+1;i<=2*k;i++) {
		f[i]=min(f[i-1]+1,f[i]);
		if (i%2==0) f[i]=min(f[i],f[i/2]+1);
	}
	for (int i=2*k;i>=k-1;i--) f[i]=min(f[i],f[i+1]+1);
	cout<<f[k]<<endl;
}

第二题

一看就是逆序对，在映射上面总是绕不过一个字母映射多个位置的坎，手膜几个数据都对的，最后好像同桌贪心证明了一下所以还是按着那个写了，100.。

第三题

？？$NOIP$模拟赛考平衡树？就是WH集训那么变态的题至少没超纲，这题是诚心要卡死人啊。。

于是程序分层，一个一个搞暴力分。。

结果好像线段树区间覆盖那几分炸了，加上又忘记开$LL$，滚粗滚粗。

好像这就结束了呢。

时间过得好快，就做了5套题就结束了。算法确乎是没有学到啥，感觉真的就是信心赛，告诉我这个世上还是有良心的题目和良心出题人的（真的是被芜湖的烂题搞怕了）。。

这次集训要是硬说有啥收获的话就是走出了AH省，和全国各地的大佬（事实上真的大佬也就$CSYZ$，$Ouuan$还有隔壁的一两位大佬了）一起做题，也看到其他省搞OI有多狠，氛围还是挺好的。

马上的话就开始进入最后全面的板子复习了，$NOIP$还是注重细节吧，正解不打$WA$，暴力尽可能拿就是最好的祝福了。