题目戳因为某国被某红色政权残酷的高压暴力统治。美国派出将军uim，对该国进行战略性措施，以解救涂炭的生灵。该国有n个城市，这些城市以铁路相连。任意两个城市都可以通过铁路直接或者间接到达。uim发现有些铁路被毁坏之后，某两个城市无法互相通过铁路到达。这样的铁路就被称为keyroad。uim为了尽快使该国的物流系统瘫痪，希...

题目戳题目描述有一个邮递员要送东西，邮局在节点1.他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有M条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间。输入输出格式输入格式：第一行包括两个整数N和...

图论题目练得比较少，发一道spfa的板子题目～给出一个N个顶点M条边的无向无权图，顶点编号为1～N。问从顶点1开始，到其他每个点的最短路有几条。输入格式：输入第一行包含2个正整数N，M，为图的顶点数与边数。接下来M行，每行两个正整数x,y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。输出格式：输出包括N行，...

～～考试时太弱，T1+T3一共只拿了暴力分60分，第二题看都没看一眼（其实就是一个二分答案+贪心早知道去做了）～～题目大意就是有n个点，给出每个点到前一个点的距离和每个点的值，然后有m个询问，每次询问从l到r这个区间的每个点到x点的距离*点值的总和模19260817。1、首先数据很大，直接暴力的话只能拿到30分到50分...

第一次自己写树形DP的题，发个博客纪念`～某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，...

　　有N个城市，M条双向道路组成的地图，城市标号为1到N。“西瓜炸弹”放在1号城市，保证城市1至少连接着一个其他城市。“西瓜炸弹”有P/Q的概率会爆炸，每次进入其它城市时，爆炸的概率相同。如果它没有爆炸，它会随机的选择一条道路到另一个城市去，对于当前城市所连接的每一条道路...

　　给一棵树，你可以匹配有边相连的两个点，问你这棵树的最大匹配时多少，并且计算出有多少种最大匹配。　　输入格式：　　　　第一行一个数N，表示有多少个结点。　　　　接下来N行，每行第一个数，表示要描述的那个结点。然后一个数m，表示这个结点有m个儿子，接下来m个数，表示它的m个儿子的编号。　　　【数据规模】　　　　N&le...

原文链接https://www.cnblogs.com/zhouzhendong/p/LuoguP4482.html给定一个字符串S，有q 次询问，每次给定两个数L,R，求S[L...R]的最长前后缀。$$q,|S|leq2imes10^5$$真是一道有趣的字符串题。首先我们给S建出SAM，并用线段树合并预处...

原文链接https://www.cnblogs.com/zhouzhendong/p/9265380.html　　懒了，不概括了。　　　　　　一开始写了树状数组。　　算法非常真，写完全部WA，但是漏了一步，我快写吐了，于是弃疗之后从某度*了一份代码。　　我来说说线段树的做法：　　线段树动态开点，每行一个线段树，最后一列...

原文链接https://www.cnblogs.com/zhouzhendong/p/9261079.html　　给定一个$n$个节点$m$条边的无向图。　　现在请你在这个图之上生成一个有根树。　　记$d_i$为节点$i$的深度$(d_{root}=0)$，记$fadis_i$为节点$i$到其父亲节点的连边中的最小边权...

原文链接https://www.cnblogs.com/zhouzhendong/p/9258043.html　　给定一个有向图，有$n$个节点$m$条边，边权值$in[0,1000]$。　　小明要从$1$走到$n$，要求路径长度最大为$d+k$，其中$d$为$1$到$n$最短路长度。　　问小明有多少种走法，答案对$p...

原文链接http://www.cnblogs.com/zhouzhendong/p/9031130.html推荐LOJ和洛谷，题面质量好，而且不卡常数。BZOJ题面烂，而且要卡那么一点点常数。　　有一条长度为$n$的链$forall1≤i<n$，点$i$与点$i+1$之间有一条边的无向图），每个点有一个整数...

原文链接http://www.cnblogs.com/zhouzhendong/p/8672434.html　　设$Li$表示第$i$个位置最小值，$Ri$表示最大值$vi$表示原值。　　那么如果$i$能到$j$这个位置，则满足：　　$i<j$　　$rjleqxi$　　$xileqli$　　于是CDQ分治水过。#...

原文链接http://www.cnblogs.com/zhouzhendong/p/8672131.html　　有$n$个元素，第$i$个元素有$a_i$、$b_i$、$c_i$三个属性，设$f(i)$表示满足$a_jleqa_i$且$b_jleqb_i$且$c_jleqc_i$的$j$的数量。对于$din[0,n)$...

原文链接http://www.cnblogs.com/zhouzhendong/p/8146041.html　　我们考虑到地图中x的个数很少，最多只有8个。　　所以我们可以考虑穷举。　　我们只需要把x变成a和b，这样就涵盖了选择A,B,C的三种情况。　　所以我们状压枚举每一个x可以变成什么情况。　　然后对于每一种情况，...