height数组 我们可以把两个字符串中间用分隔符连在一块。然后，求解id<n1与id>n1的后缀的最长的公共前缀就可以了。 但是这好像稍微有一点困难。很轻易地我们像枚举后面的id然后去在height数组中找id小于n1的后缀的最大公共前缀。就算利用了rmq，我们仍然无可避免地需要O(n^2)的时间。 其实，不用这样。我们想，在我们枚举一个n1后的后缀i去找n1前的后缀j时。在height数组上从i所处的位置向前向后遍历去找。知道找到第一个n1前的后缀。然后，取这一路的最小height值。 既然如此，我们直接找相邻的两个id在n1前后的不就好了吗？反正要取一路的最小值的啊。 代码如...

水题 #include<iostream> #include<algorithm> #include<cstdio> #include<queue> using namespace std; const int inf = 2e9; const int max_n = 200; const int max_m = 1e5; struct edge{ int to, cap, rev, next; }E[max_m * 2]; int head[max_n]; int cnt = 1; void add(int from, int to, ...

单纯的HK算法。匈牙利会超时 代码如下 #include<iostream> #include<algorithm> #include<cstdio> #include<queue> using namespace std; const int max_n = 3100; const int max_m = 1e7; const int inf = 2e9; struct edge{ int to, next; }E[max_m]; int head[max_n]; int cnt = 1; void add(int from, int ...

反向建图 单纯的反向建图，求dij就可以了。我刚开始认为，可以两个人一起乘车花一人的钱。求成最小生成树了。 代码 #include<iostream> #include<algorithm> #include<functional> #include<cstdio> #include<queue> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; const ll inf = 2e9 + 10; const int max_m = 1e...

版子题，练手。只不过这里要统计数量，所以还是有一点变化 #include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cstring> using namespace std; const int maxn = 50004; using namespace std; const int max_n = 5e4 + 100; const int max_m = 2e6 + 100; struct AC_Automation { i...

版子题，练手 #include<iostream> #include<algorithm> #include<queue> #include<set> #include<cstring> using namespace std; const int max_n = 1e5 + 100; set<int> ans; queue<int> que; struct AC_Automation { int teir[max_n][130]; int cnt = 1;int tot = 0; in...

水题，nim博弈 #include<iostream> #include<algorithm> #include<cstdio> using namespace std; int main() { int T;scanf("%d", &T); for (int tcase = 1;tcase <= T;++tcase) { int ans = 0;int N;scanf("%d", &N); for (int i = 1, a, b;i <= N;++i) { ...

如何添加边使一个无向图变为边双连通分量。双连通分量分为便双连通和点双连通。分别对应着桥和割点这里我们解决的是便双连通分量。正确的做法是，缩点。用桥连接。这样最后会变成一棵树。那么最小的代价将这棵树变成一个便双连通分量就是连接其叶子节点成为一个环及(leaves+1)/2 注意根也可能是叶子，所以还是统计度数为好 比较坑的是，这里面会有重边。故我们在判断桥时，要稍微改改。具体见代码，就是记录边的编号。 代码如下 #include<iostream> #include<algorithm> #include<cstdio> using namespace st...

模板题 点亮技能树！！AC自动机！！！！ #include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std; const int max_n = 1e6 + 100; struct AC_Automation { int teir[max_n][27]; int fail[max_n]; int is[max_n]; int cnt = 1; void init() { f...

可算过了 这是道论文题。有相应的论文的。主要想法是枚举长度，然后跳着遍历。我这里维护了两个rmq，并且在后面又接了一个倒序的字符串网上有人说不用这样，只要在往前遍历就好了。但我觉得这是错的，很可能会将复杂度提升到O(n^2)所以，我维护了两个rmq累死了，也没快多少 代码如下： #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int max_n = ...

求闭包 如果一个cow 我们知道的大于他的人数+知道的小于他的人数 == n-1那么就可以断定他的排名。 那么，如果A>B,我们就连一条A到B的边。A能到的节点数+能到A的节点数为n-1就可以了。 也就是求闭包。我们用佛洛依德算法。 代码： #include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int max_m = 5000; const int max_n = 110; bool G[max_n][max_n]; int pre[max...

nim 我们可以看出来，这是一个典型的nim游戏整个大博弈是有许多相同的小博弈组成的。那么，我们关注的重点就在如何求解出，每个小博弈的sg函数值。我们注意到，对于当前手来说，如果过此刻两棋子向邻，那么他是必输的。而反之当前手可以通过移动使下一次的局面濒危两棋子相邻。即，反之必胜。必输，即棋子间隔为0时sg==0，那么棋子间隔为1时呢？我们可以通过移动使其间隔为0，那么sg==1同理间隔为i sg==i可能会有些疑惑：棋子也可以向后走啊！这里我也不是很懂。向后走的话是不会改变局面的，无论向后走多少次，对手都可以进行相同长度的向前移动。 代码如下： #include<iostream&gt...

KMP!!!!骗子！！！！！骗子！！！！骗子！！！！！！ 这道题被放进后缀数组题单里面。但是用后缀数组的方***超时。t到死。。。。。。。。。骗子！后缀数组思路：我们要求最小的循环子串。利用后缀数组：如果 a1 a2 a3 a4 a5 a6 a7 a8 a9 的最小循环子串长为3即以a1 a2 a3为循环的话。我们就可以发现 a4为起始的后缀应该和a1为起始的后缀的最大公共前缀和为6.即为a4的长度！！！！这里是必须使a4的长度的。那么我们就可以求出高度数组，利用st表。枚举s长度的因数，利用st表枚举长度。但这会t！！！ 正确的思路为KMP。我们再回到上面的例子：a1 a2 a3 a4 a...

思维题 我们仔细想想对于行列交换如果是这种情况：1 0 0 01 0 0 01 0 0 01 0 0 0 我们是必死的。因为行列交换无法是我们将第一列中那聚在一块的4个1分散到其他的列中。 也就是说，行列交换无法使原本没有1的行/列有1 那么一个充分条件就是，对于每一行每一列，我们至少要有一个1.这也是充要条件因为：1 0 0 00 1 0 00 0 1 00 0 0 1我可以行列变化任何形状 那么直接二分图匹配吧。另外观察上面的那个矩阵。我们可以发现任何一个行交换其实都可以被列交换替代。那么其实，我们只需要进行行交换或者列交换就够了。 对每个行哥他们匹配所对应的列。然后记录他们的所处的行位，...