T1 相信你们都查到了的原题：CF468A 签到题，考的是出题人如何写SPJ。 1,2,31,2,31,2,3：显然无解 4,54,54,5：显然有解，手工构造就行了。 1 * 2 = 22 * 3 = 66 * 4 = 24 1 + 5 = 62 * 6 = 123 * 4 = 1212 + 12 = 24 >5>5>5：每次输出 n - (n-1) = 11 * 1 = 1 就可以使得 n,(n−1)n,(n-1)n,(n−1) 两数字凭空消失，此时只剩 111 到 (n−2)(n-2)(n−2)，可以看做 nnn 减少了 222。 不断减下去，直到 nnn 为 444 或 555，输出构造的答案就可以了。 T2 相信你们都查到了的原题：P2224 DP，设 fif_ifi​ 表示左手劳累度为 iii 时右手劳累度最小值。 最后计算 max⁡{fi,i}\max\{f_i,i\}max{fi​,i} 即可。 其实上面的思想有了，转移十分简单，实在推导不出来就看 luogu 题解吧。 T3 相信你们都查到了的近似题：P5656 傍一写了个十分正确的东西 ...

快读快写 1.0： char c=' ';ll in(void){ ll x=0;bool bl=false; while(!isdigit(c)) { bl^=c=='-'; c=getchar(); } while(isdigit(c)) { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return bl?-x:x; }template<typename t>void out(t x){ if(x<0)pc('-'),x=-x; if(x>9)out(x/10); pc(x%10+48);} 2.0（仅适用于文件读写）： char buf[1 << 23], *p1 = buf, *p2 = buf;#define getcha ...

高精度板子，会在做题时完善，目前有： 高精减高精 高精乘低精 高精除低精 struct nd{ int len,nl[maxn]; nd() { len=0; memset(nl,0,sizeof nl); } bool operator<(nd y) { if(len<y.len)return true; if(len>y.len)return false; frd(i,len-1,0) if(nl[i]<y.nl[i])return true; else if(nl[i]>y.nl[i])return false; return false; } nd operator-(nd y) { nd as; as.len=len; fru(i,0,len-1) { ...

字符串哈希 模数： 比较弱：101926081710192608171019260817 强得离谱：212370440130137957212370440130137957212370440130137957 （不要问我为啥放这）hash 表模数：194910011949100119491001 const ll mod=/*mod*/,bs=/*base*/;inline ll gths(int l,int r){return ((hs[r]-hs[l-1]*pow(bs,r-l+1))%mod+mod)%mod;}//mainl=str.size();fru(i,0,l-1)hs[i+1]=(hs[i]*bs+str[i])%mod; KMP 算法 看毛片 设字符串为 sss（下标从0开始），dcdcdc 为当前模式串 sss 判断的下标，preliprel_ipreli​ 为 s[0,i]s[0,i]s[0,i] 中最长前缀后缀相等长度，当匹配失败时正好需要会退到下标 predc−1pre_{dc-1}predc−1​。 简单来说，匹配过的总长 ...

快速幂&取余运算 O(log⁡2b)O(\log_2{b})O(log2​b) 求 abmod⁡pa^b \operatorname{mod} pabmodp。 ll qp(ll a,ll b,ll p){ ll ans=1; while(b) { if(b&1)ans=(ans*a)%p; a=(a*a)%p; b>>=1; } return ans;} 乘法逆元 快速幂 模数是质数版：qp(a,p-2,p) 模数仅满足 gcd⁡(a,p)=1\gcd(a,p)=1gcd(a,p)=1 版：qp(a,phi(p)-1,p) exGCD版 如下： ll inv(ll a,ll p){ ll tx,ty;exgcd(a,p,tx,ty); return (tx%p+p)%p;} 线性预处理 比较懒，直接贺了 oiwiki 的代码 inv[1] = 1;for (int i = 2; i <= n; ++i) &# ...

第二道黑题，想了一周终于想出来了，小激动。 main 主要思路：根据字典序定义，从小到大把每个数往小里放就一定行，于是从每个数开始搜索，找编号最小的合法终点。 补充一些细节： 只要确定了每个点的出边删除顺序，就一定有合法解。 在任何有至少一条边的状态中，设 nnn 为点数，eee 为边数，一定有 e⩽n−1e\leqslant{n-1}e⩽n−1，于是一定有两个点都把连接他们的边当做他们第一个要删的边，最终删的一边不剩。 code #include<iostream>#include<iomanip>#include<cstdlib>#include<cstdio>#include<string>#include<cstring>#include<cmath>//75760209#include<ctime>#include<climits>#include<random>#include<algorithm>#include<map> ...

板子（大体按代码长度排序） 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 ...