8段第一课
A我们可以设 $f_{i,0/1}$ 为第 $i$ 个点选不选，那么一个点选了自然就是加上所有儿子节点不选的状态，不选就是加上所有儿子选和不选的较大值。
12345678910111213141516171819202122232425262728293031323334353637#include <bits/stdc++.h>using namespace std;const int N = 100010;int h[N],e[N],ne[N],idx;int a[N],f[N][2];int n;void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++;}void dfs(int u,int fa){ f[u][1]=a[u]; for(int i=h[u];i!=-1;i=ne[i]) { if(e[i]!=fa) { dfs(e[i],u); f[u][0 ...
8段基环树笔记
基环树学习笔记https://517coding.com/contests/2395/problem/A
这道题可以分为几个步骤来做
1.找环我们可以直接用一个 dfs，搜到以前标记过的就说明是一个环并且不断回溯并记录环。
而通过样例，我们可以发现我们不能通过父节点判重，应该以是否是从原来的边经过来判定，而我们链式前向星中的 $idx$ 编号是连续的，所以可以以此来判定是否是原来的边。
然后如果能搜到以前搜过的就记录环并返回 $1$，接收到这个标记的点就记录环并不断回溯，一边回溯一边更新环的距离，$dis$ 数组表示环间距离。
2.处理环因为只有一个环，所以环上的每个点肯定都是一棵树的根，可以找到以根节点为出发点在树上的最长路。
而我们发现，其实一棵基环树的最长路径其实就是某两个点在环上的距离加上这两个点分别在自己的树上的最长路。
于是，我们可以断环成链把环复制一份，把环的边权做一个前缀和，这样就能清楚地知道两点间的最长距离。
而算出最大的距离的式子应是 $dis_j-dis_i+mx_i+mx_j$，其中 $mx$ 表示树上最长路。我们发现这个式子可以分成 $dis_j+mx_j$ ...
随笔
难得有时间，我带足球下楼玩。
我喜欢自己一个人踢球，草坪是不让踢的，空旷的地方踢了滚得很远，要费些力气才能捡回来，所以我喜欢在架空层踢球。每次来到这里，我便会先大力射一脚，球飞出去，撞上架空层的墙壁又弹回来。然后我便停住球，琢磨着怎样踢才踢得好。大概是脚内侧吧。我后退几步，喜欢先低着头仔细观察球一番，然后慢步向前，抬脚起射。但结果总是不如意，有时球打到脚尖，径直飞向旁边的草丛，总是得爬上爬下，经历好一番艰苦卓绝的斗争才能救出我的皮球，而有时候又打着脚背，球径直往上飞，把天花板上几块木板装饰物打下来是常有的事，经常被吓得抱住头，踉跄着后退几步。几脚射门下来，技术是没多好，植物和天花板倒是被糟蹋不少。
几脚大力且胡乱的射门后，我便开始琢磨着弧线球的踢法。我总是期望着能打出像球星一样如圆月弯刀般的射门。几般努力下来，球还是没有多少弧线，可天花板和植物就不这么想了。试了几次，玩腻了又准备练练盘球，或者是一些空中技术。就这么，一直玩，一直玩，感觉差不多该回家了，便走出架空层。
天已经蒙上了一层灰云，但还是漏了几缕刺眼的光。我有些好奇，便站在那里看着。
那几缕光像几根手指，一点 ...
笛卡尔树学习笔记
笛卡尔树学习笔记1.介绍笛卡尔树是一种树，每个节点都有两个关键字 $(k,w)$，其中如果按 $k$ 看，这棵树是满足二叉搜索树的，而按 $w$ 看，满足堆性质。
一半以数组下标为 $k$，数组元素为 $w$ 来建树。
2.流程我们可以用栈来实现这一过程。
首先，由于是以下标作为 $k$ 的，所以我们在添加节点的时候一定是添加最右边节点的右子树的。
我们用栈来维护最右边这一条链，那么每次新加进来一个数都分几种情况。
栈顶元素大于当前值，那么我为了满足堆的性质，我们应该退栈，并往他的祖先继续看。
知道栈为空或者找到了比他小的节点，就让当前点的右儿子设为新加入的点，然后为了让下标满足堆的性质，就把这一轮最后一个退栈的子树设为新节点的右儿子。
然后就完成算法流程了。
代码12345678910for(int i=1;i<=n;i++) { scanf("%d",&a[i]); int k=top; while(k>0 && a[stk[k]]>a[i]) k--; if(k) r[stk[k]]=i; if( ...
暑假模拟赛总结
7.16A解法设 $f_{i,j}$ 为当前在 $i$ 节点，用了 $j$ 条线段。
然后我们可以枚举新的不相交线段的右端点，假设为 $k$，则我们的左端点可以是 $i+1,i+2…k$，然后此时对答案的贡献就是 $2^{k-i}-1$（不选的情况舍去），这些线段可以选与不选，都会让总的选数增加 $1$。
而其他线段，其右端点需要大于 $k$（不然和贪心策略矛盾），左端点需要大于 $i$ （避免重复）。那么选与不选就有 $2^{(n-k)\times (k-i)}$ 个方案
综上所述，由 $f_{i,j}$ 转移到 $f_{k,j+1}$ 可得到 $f_{k,j+1} = f_{i,j} \times (2^{k-i} - 1) \times 2^{(k-i)\times({n-k})}$
代码1234567891011121314151617181920212223#include <bits/stdc++.h>using namespace std;const long long inf = 1e9 + 7;long long f[123123][123 ...
八段第二课tarjan算法总结
八段第二课tarjan算法总结D 构造可达性解法首先我们缩点，因为里面都是可达的。
然后我们可以发现，缩完点之后，如果一个点入度为 $0$，那么就说明没有点能到这个点，我们就得答案++。
最后，注意判断 $s$ 所在的点是否有被算入答案。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include <bits/stdc++.h>using namespace std;const int N = 2000010;int h[N],e[N],ne[N],idx;int n,m,s;int times=1;int color[N];int dfn[N],low[N];bool vis[N];int cc=0;void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++;}int ...
八段第八课字符串算法总结
八段第八课字符串算法总结A T恤分配解法这道题好像是到二分图。
直接连每个人能选的码数，然后二分图模板即可。
代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include <bits/stdc++.h>using namespace std;const int N = 2000;int h[N],e[N],ne[N],idx;void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++;}string s;int x,a[22];string sz[22];int k[6][22];map<char,int> mp;int pi[N];bool m[N];bool find(int u){ for(int i=h[u];i!=-1;i=ne[i]) ...
八段第七课轮廓线dp总结
第七课轮廓线dpB 铺砖问题解法这道题我们可以使用 $dp$。
我们可以在每一行枚举轮廓，逐格转移。
我们看上图，我们现在考虑的是红星位置的三种情况：横，竖和不放。
因为后面无论怎么放都不可能填满红色部分，所以红色部分都必须满。
那么，如果红星的上面没有填，那么必须填。
相反，如果红星的上方没填，那么就可以横放或者不放。
那么使用二进制压缩这条轮廓，然后滚动数组转移就好了。
具体详见代码。
代码123456789101112131415161718192021222324252627282930313233#include <bits/stdc++.h>using namespace std;#define int long longint dp[2][4096];int n,m;signed main(){ scanf("%d%d",&n,&m); dp[0][(1<<m)-1]=1; int cur=1; for(int i=0;i<n;i++) { for(int j=0;j<m;j+ ...
八段第四课数位dp
八段第四课：数位DPA包含49的数字解法我们可以使用记忆化搜索从高到低一位一位放，每位都从 $0-9$ 枚举，使用数组优化。
设 $f_{i,0/1/2}$ 表示从高到低第 $i$ 为的三种情况：
$0$ ，表示前面出现过 $49$.
$1$，表示前面没出现过 $49$。
$2$，表示前面没出现过 $49$，但是以 $4$ 结尾。
那么我们就可以直接转移。
代码123456789101112131415161718192021222324252627282930313233343536373839404142#include <bits/stdc++.h>using namespace std;#define int long long//0: 有49 1：没49 2：以4开头 long long n;long long dp[123][123];int w[123];long long dfs(int pos,int mask,int limt)//当前位数，状态，能选到的极限（0表示能选到0~9，1则表示能选0~a[pos]）{ if( ...
八段第一课树结构升级总结
八段第一课树结构升级总结A 间隔选点-树上版本解法设 $f_{i,0/1}$ 表示当前是编号为为 $i$ 的点，是否有选。
然后当前节点选的状态就可以加上所有儿子不选的状态，而当前节点不选的状态则可以加上儿子选与不选的状态。
所以dfs即可。
代码12345678910111213141516171819202122232425262728293031323334#include <bits/stdc++.h>using namespace std;const int N = 20000;int a[N],h[N],e[N],ne[N],idx;int f[N][2];int n;void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}void dfs(int u,int fa){ f[u][0]=0,f[u][1]=a[u]; for(int i=h[u];i!=-1;i=ne[i]) { if(e[i]!=fa) dfs(e[ ...