板子（大体按代码长度排序） ST表 板子题传送门 预处理部分： int n,nl[maxn],f[maxn][maxl],lg[maxn];//nl：原数组lg[0]=-1;fru(i,1,n)f[i][0]=nl[i],lg[i]=lg[i>>1]+1;fru(i,1,lg[n])fru(j,1,n-(1<<i)+1)f[j][i]=max(f[j][i-1],f[j+(1<<i-1)][i-1]); 干活部分： max(f[l][lg[r-l+1]],f[r-(1<<lg[r-l+1])+1][lg[r-l+1]]) 左偏树 板子题传送门 struct tree{ int lc,rc,w,d;}nl[maxn];inline bool bgood(int a,int b){ return nl[a].w==nl[b].w?a>b:nl[b].w<nl[a].w;}int heap_merge(int x,int y){ if(!x||!y)return ...

前言 看到一个比较牛（sao）的复杂度证明，记一下。 基本的树上背包问题长这样（就是把花费为1的0-1背包搬上了树）：现在有 nnn 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 mmm 门课程学习，问他能获得的最大学分是多少？（1≤N,M≤30001 \leq N , M \leq 30001≤N,M≤3000） 树形背包的复杂度是 O(nm2)O(nm^2)O(nm2)，比起平时背包的 O(nm)O(nm)O(nm) 差多了去了。但树形背包真的可以 O(nm)O(nm)O(nm)。 代码与思想 核心代码（优化后，选自OIWIKI）： int dfs(int u) { int p = 1; f[u][1] = s[u]; for (auto v : e[u]) { int siz = dfs(v); // 注意下面两重循环的上界和下界 // 只考虑已经合并过的子树，以及选的课程数超过 ...

这题算是一道比较神奇的背包，记一下。 思路 这道题很明显叫我们用时间换高度，而换的条件还是时间，就很烦。 因此考虑使 fif_ifi​ 表示高度 iii 可以活的最久时间，用刷表法，当第一次刷到 ⩾\geqslant⩾ 目标高度时说明我们第一次可以活在目标，成功了。 转移的式子在有了逆向的思路后是很好想的： f[j+nl[i].d]=max(f[j],f[j+nl[i].d]);f[j]+=nl[i].l; 代码 const int maxn=152;int dep,n,f[maxn],ans;struct garage{ int t,l,d;}nl[maxn];inline bool cmp(garage x,garage y){ return x.t<y.t;}int main(){ dep=in();n=in(); fru(i,1,n) { nl[i].t=in(); nl[i].l=in(); nl[i].d=in(); } ...

题目链接 大体思路 把 111 作为起始点，将 i(0⩽i⩽x−1)i(0\leqslant i\leqslant x-1)i(0⩽i⩽x−1) 与 (i+y)mod  x(i+y)\mod x(i+y)modx 连权值为 yyy 的边以及与 (i+z)mod  x(i+z)\mod x(i+z)modx 连权值为 zzz 的边，跑一遍最短路，就会发现到 iii 的最短路（记作 disidis_idisi​）会表示 %x==i 的楼中可以走到的最低的楼的层数。 坑点 全部要开long long x=1x=1x=1 时，111 是 mod  x=0\mod x=0modx=0 的最低楼层，所以要把 111 向 000 建边（其他时候都不用）。 代码 #include<iostream>#include<iomanip>#include<cstdlib>#include<cstdio>#include<string>#include<cstring>#include<cmath>//757602 ...

这里放了最基础的图论内容在本文中maxn为最大点数，maxm为最大边数. 链式前向星 以下代码存图所用链式前向星皆用这个模板 注意访问时的顺序与输入时是相反的。 struct edg{ int next,to,w;}edge[maxm];//无向图是这里要<<1int head[maxn],cnt=1;inline void getin(int a,int b,int w)//加边{ edge[cnt]=(edg){head[a],b,w}; head[a]=cnt++;}for(int j=head[tmp];j;j=edge[j].next)//访问tmp发出的边 拓扑排序 在建边时先预处理入度，即代码中的vin int vin[maxn];//这个vinqueue<int>que;for(int i=1;i<=n;i++)if(!vin[i])que.emplace(i);while(!que.empty()){ int dc=que.front(); ...

Hello World! 没错，梦开始的地方，但是开门就寄。 DAY -1 请了一整个下午的假去试机，结果忘了加用准考证号命名的文件夹，直接把程序放在了E盘。吓死了，辛好是试机。 DAY 0 今天去比赛…… T1:看起来是很水的DP，期望 100100100。 T2:完了，太难了，连模拟都不会，交了样例，期望 000（有分就恐怖了）。 T3:除了暴力什么都没想出来，打了一条链+纯暴力（对，就是前3个点），期望252525。 T4:发现纯暴力加上st表一点用都没有，索性暴力到底，期望 888 分（似乎多组数据还忘了换行，寄）。 DAY 1 结果呢，寄了。还是寄在T1上只得了1分，像开玩笑 1+0+25+8=341+0+25+8=34 1+0+25+8=34 几乎是被白罚坐了一早上。菜死了😭