前序遍历:根左右

中序遍历:左根右

后序遍历:左右根

P3916图的遍历

题意:求每个节点能到达最大节点的编号;

SOL:反向建边,倒序枚举最大节点能到达的点。

如果枚举每个点的出边,会发现出边的出边的出边……才是最终的结果,考虑反向建图,倒序枚举最大的点,dfs,这个点能到达的所有的点都更新一遍,第一遍更新的时候一定是最大值,所以如果已经算过一遍就直接return。

P1229遍历问题(已知前序后序遍历,求中序遍历有几种)

tip:只有一个儿子 的节点 才会在知道 前序后序 的情况下有不同的中序遍历,
所以将题目转化成找 只有一个儿子的节点个数。

分析:在先序遍历中某一元素A的后继元素B(**B可能是A的左节点或A无左节点,B为A的右节点**),如果在后序遍历中A的前驱元素是B
**B可能是A的右节点或A无右节点,B为A的左节点** ,

综上,**那么A只有一个子树,** 问题即得解,

SOL:求出有x个节点的子树只有一个(那么中序遍历就可能是左子树或右子树两种),答案即为2^x;

代码

P1443 马的遍历

printf("%-5lld",f[i][j]);

代码

P5407 [THUPC2019]历史行程

蔡勒公式的运用

int week=(c/4)-2 * c +(y+y/4)+(13 * (month+1))/5+day-1;

代码

P1346 电车

对于默认状态的边,边权赋值为0,其他边赋值为1(意为要改变一次),用Floyd跑一边最短路即可求出最少改变多少次开关。

P2863 [USACO06JAN]牛的舞会The Cow Prom

tarjan缩点,如果强连通分量的size>1则舞会成功

P1807 最长路_NOI导刊2010提高(07)

与最短路的不同:

mem(dis,-0x3f);

if(dis[v]<dis[u]+w)

P2746 [USACO5.3]校园网Network of Schools(复习tarjan)

子任务a:求出指派几个学校即可将消息传遍

SOL:tarjan缩点后,答案为入度为0的点的个数

子任务b: 求再加几条边能使所有学校连成一个强连通分量

SOL:max(出度为0的个数,入度为0的个数);显然,出度为0连一条入度为0的点即可,但是如果出度为0的个数!=入度为0的个数,则多的那个随便连就好了。

record:1nd 90pts:Bcnt == 1 的时候 子任务b的答案不能取max(出度为0的个数,入度为0的个数);要特判,输出0;

UVA1665 岛屿 Islands

P1197 [JSOI2008]星球大战

如果动态维护连通块个数且连通块内元素不断减少,则离线处理询问,倒着加点求并查集。

P1162 填涂颜色

首先对外围的0,dfs并标记
a[i][j]填2的时候当且仅当:
1.未被标记
2.不是1

这里的重点是dfs,显然不可能对每个点都dfs,如果这样的话被围着的点也会被标记,只能搜外面的点,如果dfs(1,1)的话,下面这组数据就出了问题:

10
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 1 0 1 0 0 0 0 1
1 0 1 0 1 0 0 0 0 1
1 0 1 0 1 0 0 0 0 1
1 0 1 0 1 0 1 1 1 1
1 0 1 0 1 0 1 0 0 0
1 0 1 1 1 0 1 1 1 1
1 0 0 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

正解是

1 1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2 1
1 2 1 2 1 2 2 2 2 1
1 2 1 2 1 2 2 2 2 1
1 2 1 2 1 2 2 2 2 1
1 2 1 2 1 2 1 1 1 1
1 2 1 2 1 2 1 0 0 0
1 2 1 1 1 2 1 1 1 1
1 2 2 1 1 2 2 2 2 1
1 1 1 1 1 1 1 1 1 1

而dfs(1,1)的结果是

1 1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2 1
1 2 1 2 1 2 2 2 2 1
1 2 1 2 1 2 2 2 2 1
1 2 1 2 1 2 2 2 2 1
1 2 1 2 1 2 1 1 1 1
1 2 1 2 1 2 1 2 2 2
1 2 1 1 1 2 1 1 1 1
1 2 2 1 1 2 2 2 2 1
1 1 1 1 1 1 1 1 1 1

我们可以从dfs(0,0)开始搜!!!! 这样就很好的解决了边界问题。

代码

01-26 21:21