BZOJ2115 [Wc2011] Xor 线性基+DFS 图论 数学

BZOJ2115 [Wc2011] Xor 线性基+DFS

题目   给出一个无向图,求一条1-n的路径,使路径边权xor和最大。 首先,可以把一条简单路径和任意多个环拼在一起,形成一条题目所求的路径。接着,对于任意一条简单路径,都可以和一些环的权值异或在一起,达到其他简单路径的效果。所以,我们只需找出任意一条简单路径,找到所有的环,再把环上的xo···
BZOJ1093 最大半连通子图 tarjan+最长链 图论

BZOJ1093 最大半连通子图 tarjan+最长链

画画图,可以看出来强连通分量里面的肯定都是,所以缩点去环,建新图。观察一下,可以发现一个半联通子图没法跨越两条链,就是说最大的联通子图在新图上一定是一条最长链,DFS一下就可以求出来。就是统计最长链数的时候一开始只想出了再DFS一次的做法,但因为无形中又加了一维所以光荣TLE。后来才发现,最长链数只···
NOIP2011 玛雅游戏 DFS 搜索

NOIP2011 玛雅游戏 DFS

昨天考试第一题,一眼看出做法,但是就是不会打。DFS、回溯移动过程,移动后一直调用消块、掉落函数,直到不可调用为止。注意剪枝,限制向左走时,左边必须没块。因为搜索是按照(x,y,d)三元组排序进行的,如果当前块和其左边的块都不为0,那么左边的块右移等效于当前块左移,而前者已经被考虑到(坐标优先),所···