思路 首先所有的路径数为,也就是选出个时间点向上,其他时候向右.然后只要减去越过的路径即可.先上图:将上移,变成,也就是路径不能碰到.将路径最后一个碰到的点与以为对称轴翻折.也就是粉色点路径翻折成紫色点路径.这样的路径一定是一一对应的,因为从到的路径一定可以唯一地翻折回来,而且这样的路径肯定是碰到的,可以计算出路径数为.因此答案就是.由于没有取模,要写个高精度. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e...

思路 先不考虑数据范围,我们设表示当前构造到第位,已经匹配了位的方案数.最终答案即为我们可以写出一个递推式,是我们要求的系数.我们可以使用KMP来求系数.只要求出前位(长度为)与相同,下一位的数字为时,与最大的匹配长度.对于每一个,,很明显不能承受.但是系数每次转移都不会变,因此直接用矩阵快速幂优化即可. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define f...

思路 首先,假设图中所有路径长度都为1.走步时从到的方案数,走步时从到的方案数.那么走步的方案数.矩阵快速幂就OK了.但是这里边权不为1.由于数据范围小,我们可以将边权为的边拆成条边权为1的边,然后矩阵快速幂即可.复杂度为 代码 #include<bits/stdc++.h> using namespace std; #define mod 2009 int a[1 << 7][1 << 7], ans[1 << 7][1 << 7], N, T, tot, t, c[1 << 7][1 << 7]; void...

思路 这是一个无源无汇的最小割问题.或者说叫"无向图全局最小割".一个很暴力的思想就是枚举任意两个点作为源点和汇点.复杂度大概是,但是由于跑不到上界,还是可以过的.如果对这个复杂度不满意,可以枚举源点,其他点向汇点连边,复杂度为,优秀得多.你还可以使用二进制思想,枚举每一位,将所有点分成两部分,源点向一部分连边,剩下的向汇点连边,复杂度大概为.才50,可以忽略.(我没有试过,还不知道对不对,有错误请指出)还有一种的做法Stoer Wagner专门求无向图全局最小割.感兴趣的同学请上网查阅资料.因为我也不会 代码 最暴力的做法(*/ω＼*) #include<bits/stdc++.h&g...

思路 费用流裸题.将每个点拆成入点和出点,入点与出点之间连边,容量为1,价值为该点的数.这样该点只能经过一次且经过会得到该数的代价.实际上每个格子能经过多次,但只能得到一次的代价,因此再连一条容量为,价值为0的边.然后源点向连边,向汇点连边,跑一遍最大费用最大流即可. 代码 #include<bits/stdc++.h> using namespace std; #define MAXN 3005 #define MAXM 400555 int N, K; int hd[MAXM], nxt[MAXM], to[MAXM], val[MAXM], fee[MAXM], tot(1)...

思路 事实上,此题等价于求最小路径可重覆盖.为什么呢?我们可以考虑构造出所有的藏身点.首先,跑一遍最小路径可重覆盖后,将所有路径的终点加入集合.假设表示.表示传递闭包后的边集.如果,选取,不断沿着路径向前移,直到为止.不断重复以上过程,直到停止.容易证明,这样肯定能找到一个合法的方案.这题不需要输出方案,直接跑最小路径可重覆盖即可. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; +...

思路 因为木板可以重叠,所以如果放置木板,木板两端肯定都顶到底(障碍或者边界)是最优的.这样就可以预处理出一些横向与纵向的联通块(宽度都为1).因为每一个方格必须被覆盖,所以该方格隶属的横向联通块与纵向联通块至少有一个被木板覆盖.这样就可以构建二分图,横向联通块为左部图,纵向联通块为右部图,每一个方格都是一条边,跑二分图最小点覆盖即可. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I;...

思路 很裸的二分图最小点覆盖题.首先,因为最开始都处于0模式,那么或的边都可以删去.然后因为最优情况下每种模式最多只转换一次,可以把转换过这种模式看作选择这种模式所代表的的点,而可以看作一条边.的模式是左部图,的模式是右部图.很明显,题目转换成这样一个问题:选择最少的点,使所有边都能覆盖到.这就是经典的二分图最小点覆盖模型.直接跑匈牙利或网络流即可.(最近比较懒,所以就写了虽然复杂度高但是代码短的匈牙利) 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e...

思路 很明显,一对相斥的位置,横纵坐标之和的奇偶性肯定不同.所以可以构成一个二分图.源点向所有横纵坐标之和为奇数的点连边,为偶数的向汇点连边,边权都为1.一对相斥的点之间连边,跑一遍最小割即可.或者如果你懒得写网络流,你可以套用最大独立点集的模型,跑匈牙利即可.虽然效率比网络流低得多. 代码 #include<bits/stdc++.h> using namespace std; #define MAXN 60555 #define MAXM 520555 int N, M, TT; int hd[MAXN], val[MAXM], nxt[MAXM], to[MAXM], tot...

思路 先预处理出,表示从开始,小A小B各走了步时,小A走的路程,小B走的路程,以及所到达的地方.这些东西可以预处理出来.2^1,然后对于第一问,我们可以枚举每一个出发点,从枚举到,能继续走就继续走,否则就停止,别忘了最后小A还可以走一步.然后就可以得到小A小B分别走的路程,取比值最小的即可.对于第二问,也从枚举到,总路程不超过就继续走,否则就停止,也别忘了小A还能继续走一步.虽然想法不难,但是细节还是比较多的.复杂度为稳稳的. 代码 #include<bits/stdc++.h> #define u32 unsigned #define i64 long long #define ...

思路 按照题意建边,若亮度大于等于的,连有向边,大于则为,相等则为.然后缩点,如果出现一个强连通子图内有大于0的边,说明存在正环,无解.然后拓扑排序,若有边,,直接DAG上DP即可.当然你想跑差分约束我也没办法qwq. 代码 话说那时候脑子抽了还是怎么样,本地运行爆栈了,我还以为一定要手工栈什么的qwq.... 没救了没救了 #include<bits/stdc++.h> using namespace std; #define MAXN 200005 #define MAXM 300005 #define LL long long int N, K; int hd[MAXN], ...

思路  I.设在搜索树T中以x为根的树包含的点集为SubTree(x)。 II.这里去除割点可以理解为删除与该点相连的所有边。 III.这里提到的连通块是指当某一割点去除时：1.其中任何两个点都能相互到达 2.没有更大的连通块包含该块 当然，根据II，我们把单独的X也看做一个连通块 IV.为了方便，我们直接将(x,y)(满足x不能到y)成为“点对” V. ~S：S的补集，A^B：在A中不包括点B的所有点构成的集合  利用Tarjan查找割点的同时，我们可以找出该割点X去除后剩余的连通块（有两种情况，一种是在SubTree(X)^X中，另一种是~SubTree(X)）。 只要能够理解割点的求解过...

思路 放置多米诺骨牌可以看作与或或或匹配的过程.因为与,奇偶性不同,可以分成一个二分图.这样就变成一个二分图匹配问题,能匹配且都不是障碍的两个点之间连边,直接跑匈牙利即可. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i ) #define go( i, ...

思路 这题可以用并查集或二分+二分图染色解决.首先二分答案,然后只要判断是否能将罪犯分成两个图,图的内部边权都不超过答案. 并查集 这样子可以直接使用并查集的边带权或者扩展域解决.对边从小到大排序.边带权的话,边权可以是两点是否相同,合并时如果有冲突判断就输出答案.扩展域的话也就是每个罪犯拆成两个点,每次合并与,如果最终与在同一个联通块,判断即为失败. 二分图染色 取出有效边(边权大于),因为要构成二分图,边的两端节点颜色必须不同.直接跑即可.如果遇到冲突判断就失败. 代码 这里仅给出二分图染色的代码 #include<bits/stdc++.h> using namespace ...