「LOJ2000~2023」各省省选题选做

「LOJ2000~2023」各省省选题选做

「SDOI2017」数字表格

莫比乌斯反演。

「SDOI2017」树点涂色

咕咕咕。

「SDOI2017」序列计数

多项式快速幂。

我们将超过 \(p\) 的部分加到 \(0\sim p-1\) 中。

「SDOI2017」新生舞会

分数规划+费用流。

记得 \(eps\) 设为 \(10^{-7}\)

「SDOI2017」硬币游戏

咕咕咕。

「SDOI2017」相关分析

线段树好题。

我们要化一下式子，发现维护四个值：

struct node{

	int sum[4],cov,add[2],len;

	//sum[0]=x*y sum[1]=x*x sum[2]=x sum[3]=y

}t[maxn<<2];

「SCOI2015」小凸玩矩阵

二分+最大流。

「SCOI2015」国旗计划

姿势奇怪的倍增。

「SCOI2015」小凸想跑步

咕咕咕。

「SCOI2015」小凸玩密室

神仙树形 \(dp\) + 倍增。

\(f[i][j]\) 表示 \(i\) 的 \(j\) 级祖先（从 \(1\) 开始），\(dis[i][j][0/1]\) 表示 \(i\) 的子树点亮后去 \(j\) 级祖先/另一个儿子。预处理完后可以枚举每一个开始的点，然后倍增计算贡献。

for(int i=n;i>=1;i--)

	for(int j=1;~fa(i,j);j++){

		dp[i][j][0]=dp[i][j][1]=inf;

		if(lson>n){

			dp[i][j][0]=dis[i][j]*val[fa(i,j)];

			dp[i][j][1]=(dis[i][j]+dis[bro(i,j)][1])*val[bro(i,j)];

		}

		else if(rson>n){

			dp[i][j][0]=dp[lson][j+1][0]+dis[lson][1]*val[lson];

			dp[i][j][1]=dp[lson][j+1][1]+dis[lson][1]*val[lson];

		}

		else {

			dp[i][j][0]=min(dp[i][j][0],dp[lson][1][1]+dp[rson][j+1][0]+dis[lson][1]*val[lson]);

			dp[i][j][0]=min(dp[i][j][0],dp[lson][j+1][0]+dp[rson][1][1]+dis[rson][1]*val[rson]);

			dp[i][j][1]=min(dp[i][j][1],dp[lson][1][1]+dp[rson][j+1][1]+dis[lson][1]*val[lson]);

			dp[i][j][1]=min(dp[i][j][1],dp[lson][j+1][1]+dp[rson][1][1]+dis[rson][1]*val[rson]);

		}

	}

ll ans=inf,tmp;

for(int i=1;i<=n;i++){

	tmp=dp[i][1][0];

	for(int x=i,y=fa(x,1);~y;x=y,y=fa(y,1)){

		if(bro(x,1)<=n) tmp+=dis[bro(x,1)][1]*val[bro(x,1)]+dp[bro(x,1)][2][0];

		else tmp+=dis[y][1]*val[fa(y,1)];

	}

	ans=min(ans,tmp);

}

「SCOI2015」小凸解密码

线段树。

破链成环后瞎搞喽。

「SCOI2015」情报传递

树剖+线段树+二分 \(O(n\log^3 n)\) 都过了。。。

「SCOI2016」背单词

将问题转化为在 \(trie\) 树上找一个拓扑序使父亲减去儿子最小，这个可以贪心解决。

「SCOI2016」幸运数字

线性基+倍增 \(O(n\log^3 n)\)

「SCOI2016」美味

主席树+贪心。

「SCOI2016」围棋

咕咕咕。

「AHOI / HNOI2017」单旋

咕咕咕。

「AHOI / HNOI2017」影魔

离线+线段树。

关于一个问题的证明

「AHOI / HNOI2017」礼物

FFT。

「AHOI / HNOI2017」大佬

神题。

「AHOI / HNOI2017」队长快跑

咕咕咕。

「AHOI / HNOI2017」抛硬币

咕咕咕。