「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」抛硬币
咕咕咕。