- 博客(84)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #670 (Div. 2) C. Link Cut Centroids
只能说将近一年没打建图都不会建了.......就是只有偶数个，并且当前节点的所有子节点加自身正好是n/2时，才会出现这样的情况。思路一眼就出了，但是忘了需要按照无向图建图，我给默认有向建了个图....wa的自闭手速也明显不如以前了#include<iostream>#include<cstdio>#include<vector>using namespace std;vector<int>v[200000];int ins[2000
2020-09-13 09:29:20
132
原创 Longest Common Substring II
给你多个串找到最长公共字串对第一个串建树然后维护所有串在每一个节点处最小的匹配值然后遍历所有节点找到最大需要注意的是需要从最长的后缀开始往前遍历 如果当前节点被匹配到了 那么它的父亲节点一定也被匹配到了 而且是匹配到了父亲节点的长度 （因为子节点最短的后缀也比父亲节点最长的后缀长）#include<iostream>#include<cstdio>...
2019-11-14 15:11:41
199
原创 2019南昌邀请赛I(st+单调栈）
给出数字序列，定义一个区间内的value值是这个区间所有数之和*这个区间的最小数，求对于这个数字序列，最大的value值肯定要使用前缀和快速的求区间所有数之和而求取方法为 sum[j1]-sum[j2]我们利用单调栈找到以a[i]为最小值的左右边界，以当前i为界分成左右两个区间对于a[i]>0 在右边界找到最大的sum[j1]，左边界找到最小的sum[j2]对于a[...
2019-11-11 18:17:29
209
原创 P4306 [JSOI2010]连通数(tarjan+反向建图拓扑排序)
题目大意就是给你一个有向图每个点的连通度就是它能到达的点的个数（包括自身）问你所有点的连通度之和就是tarjan缩点之后反向建图利用拓扑排序一层一层传递ans的值求解（反向建图之后入度为零的点肯定是没有出度的点）然后传递的时候我们传递的是缩点之后强连通分量的点的大小（不一定是1）而且我们计算sum时还需要先加上ans[i]乘该强连通分量的点的数量（因为看成了一个点 实际上是...
2019-11-05 16:07:03
194
原创 洛谷P2341受欢迎的牛(强连通分量模版)
强连通分量可以看作一组点 这组点中任意两个都是可到达的 然后把这一组点抽象成一个点即可#include<iostream>#include<cstdio>#include<algorithm>#include<string.h>using namespace std;const int maxn = 1e5+100;const ...
2019-11-05 14:41:07
131
原创 hdu4280(网络流模版）
验证了一下网络流的板子题发现有一个板子和kuangbin聚聚的板子效率相差不多可能还更高效kuangbin聚聚写的是非递归的 这个可能更容易敲一点题目大意就是输入n,m找到s t直接连图求最大流https://blog.csdn.net/Code92007/article/details/88581495（附链接）#include<iostream>#...
2019-11-04 21:30:51
147
原创 hdu1255(扫描线)
扫描线板子题 没啥好说的输入矩形两点 然后求覆盖两次的面积（sum为覆盖面积,sums为覆盖两次的面积）#include<iostream>#include<cstdio>#include<algorithm>#include<map>#include<string>#include<string.h>...
2019-10-24 17:26:49
165
原创 2019徐州网络赛E
给你一个序列对于每一位求这位后面最后一个大于等于该位加m的数的位置两种做法一种是线段树//// Created by xingchaoyue on 2019/10/24.//#include<iostream>#include<cstdio>using namespace std;const int maxn = 5e5+1000;int ...
2019-10-24 17:17:25
80
原创 The Stream of Corning 2（线段树）
#pragma GCC optimize(2)#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int n,m;const int maxn = 1e6+1000;int t[maxn];struct node{ int t; in...
2019-09-27 15:43:24
144
原创 Distinct Substrings & New Distinct Substrings SPOJ（后缀数组统计所有不同的子串）
一个字符串所有子串的总数是n*(n+1)/2其实要遍历所有子串 就是找每个后缀的所有前缀然后又因为所有的后缀是经过后缀排序得来的 所以每个后缀与其他后缀相同的前缀最多就是Height[i]所以n*(n+1)/2 - sum(height[i])就是答案#include<iostream>#include<cstdio>#include<strin...
2019-09-26 12:21:36
135
1
原创 life forms poj3294(写了很久才写过）
后缀数组还是不熟首先总数组的最后一个r[n]必须是0其次设置的最大值一定要比r中最大值大再其次 多个字符串拼接时 拼接的字符一定要不相同最后 题目给的n上限100莫名坑爹#include<iostream>#include<cstdio>#include<string.h>#include<algorithm>usin...
2019-09-23 19:05:23
88
原创 hdu2328(暴力kmp）
这个题我想练一下kmp就没用后缀数组做后缀数组的思路也很简单 链接所有串 然后二分答案就可以了也可以暴力枚举后缀 对每一个后缀用kmp找到最小公共前缀就可以我算着复杂度是（200*4000*400）可能3s勉强能过...但是只用了几百ms 感觉数据出水了#include<iostream>#include<cstdio>#include<al...
2019-09-22 10:32:28
218
原创 Graduation Gym - 102307G （思维+拓扑排序）
这个题我看反了树。。优先队列也写反了逻辑应该是本来优先队列就是大根堆然后我的小于号应该按照d的大小进行重定义（不知道为什么一开始跑出结果来了clion害我）就是对森林进行拓扑排序然后找拥有最大子树的节点然后删除#include<iostream>#include<cstdio>#include<vector>#include<qu...
2019-09-21 15:49:19
389
原创 poj3261(后缀数组+二分+kuangbin模版注意问题）
#include<iostream>#include<cstdio>#include<string.h>using namespace std;const int maxn = 2000000+1000;int t1[maxn],t2[maxn],c[maxn*10];bool cmp(int *r, int a, int b, int l)...
2019-09-19 17:02:10
131
原创 Relevant Phrases of Annihilation（后缀数组+二分）
#include<iostream>#include<cstdio>#include<string.h>using namespace std;const int maxn = 2000000+1000;int t1[maxn],t2[maxn],c[maxn];int n;bool cmp(int *r, int a, int b, int...
2019-09-17 20:28:10
138
原创 主席树模版（区间第K大）
//// Created by xingchaoyue on 2019/9/10.//#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int maxn = 2e5+1000;const int M = maxn*30;int t[m...
2019-09-11 13:57:34
103
原创 2019CCPC网络赛K-th occurrence（后缀数组+ST+二分+主席树）
比赛的时候思路完全正确 但是不知道为啥卡在了二分上当时没整明白这个题确实有点东西....lcp函数当两个参数相同时是查找不到的 这个需要注意其余的就是利用rank找到对应的排名然后两个二分查询1..排名..n的符合条件的区间然后利用主席树维护SA数组区间第k大即可就是代码有点长#include<iostream>#include<cstdio&...
2019-09-10 17:42:45
261
原创 2019徐州网络赛G(回文树）
比赛的时候没能静下心来看看回文树今天发现当时静下心来学学两三个小时肯定能做出来....#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 300010+100;ty...
2019-09-09 16:55:03
156
原创 SPOJ1811(后缀自动机）
一个串建DAG另一个串直接跑就可以跑的时候三种情况第一种当前的root就有c这个出边 那么 直接跑到下一位就好第二种当前的root没有c这个出边 但是当前root的别的状态的后缀有出边那么不断跳fa跳到有出边即可（因为当前length(root)必然大于其length(fa)并且kmp思想 匹配了root代表的后缀那么fa也匹配了，所以肯定是length（fa)+1)如果跳到r...
2019-09-05 17:24:11
159
原创 poj1509（后缀自动机）
其实这个题也可以用最小表示法但是还是练了练后缀自动机明白了构造函数就是构造原串（整个串）的以最后一个字符为止的所有后缀都加上一个字符产生新串的后缀这个题目就是找这个字符串循环中的最小表示直接两个原串一拼接 所有的循环都是拼接后长串的后缀找到长度为len的最小后缀即可#include<iostream>#include<cstdio>#inc...
2019-09-05 15:08:22
157
原创 后缀自动机遍历所有子串
裸板子到现在我复杂度还是不会算#include<iostream>#include<cstdio>#include<string.h>#include<cstring>typedef long long ll;using namespace std;int tot = 1;int las = 1;struct node{ ...
2019-09-04 23:42:20
192
原创 hdu3613扩展kmp求回文
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;const int maxn = 500000+100;char x[maxn];char y[maxn];int knext[maxn];int ex...
2019-09-03 17:59:56
122
原创 hdu1358(循环节）
#include<iostream>#include<cstdio>#include<string>#include<cstring>using namespace std;int knext[1000000+100];void get_kmp(string s,int len){ int i = 0; int j =...
2019-08-28 22:15:30
142
原创 poj3660(floyd求传递闭包）
#include<iostream>#include<cstdio>using namespace std;int n,m;const int inf = 0x3f3f3f3f;int mp[200][200];void init(){ for(int i = 0;i<=100;++i){ for(int j = 0;j<=...
2019-08-28 18:49:34
118
原创 poj3080(kmp+枚举）
这个题数据很小 暴力瞎搞都能过我试了试kmp我看大部分题解复杂度都不低我的复杂度大概 n*m*(n+n)就是枚举第一个串的后缀来匹配后面的串 找到最长能匹配多少 选取最小的匹配长度为ans就是这个后缀和其余串的公共部分了然后在这一堆ans里面最大的就是结果之所以写这篇题解是因为memcpy每次只会从头开始复制传递的参数个 如果你的数组里之前是AAAAA 那么复制ABC...
2019-08-15 20:05:44
127
原创 hdu3065(AC自动机）
这个题就是问你模式串在给定串中出现的次数这里又进一步了解了一下AC自动机的匹配原理其实就是每次往后移一位之后 匹配所有新后缀 最后会匹配到j==0就是根节点如果给定串中有重复的部分那么会匹配很多次（.cnt就是来判断有没有被匹配过）如果bca被匹配过 那么 ca a 肯定也被匹配过了这个题的坑就是多组样例#include<iostream>#inclu...
2019-08-15 09:25:59
209
原创 hdu2451(数学)
这个题的意思是枚举小于n的i使得i+(i+1)+(i+2)不会产生十进制下的进位思路很好想 个位只可能是0，1，2三种情况而十位往上则为0，1，2，3四种情况思路很明白然而菜的没敲出来（晖神：很简单的题）想复杂了 其实就是假设n是2183那么千位取0，1的话是所有情况首位是0，1的情况都囊括的，个位3种情况，其余位都是四种情况，然后乘起来就可以了然后再是千位取2 千位就...
2019-08-07 17:55:08
120
原创 poj2774(后缀数组）
#include<iostream>#include<cstdio>#include<string.h>#include<algorithm>#include<cmath>using namespace std;const int maxn = 2e5+100;char s[maxn];int t1[maxn],t2[...
2019-08-06 20:48:00
135
原创 扩展kmp
扩展kmp本质还是kmp有点类似马拉车就是改变next数组含义为与记录与自身最长的公共前缀的长度（这个也用扩展kmp求）#include<iostream>#include<cstdio>#include<cmath>#include<string.h>#include<cstring>using namespac...
2019-08-05 18:20:55
127
原创 poj1797最短路变形
#include<iostream>#include<cstdio>#include<queue>#include<string.h>using namespace std;int t,n,m;const int maxn = 1e3+10;int mp[maxn][maxn];const int inf = 0x3f3f3f3...
2019-08-03 14:15:10
116
原创 高斯消元（模板）
高斯消元就是求解多元一次方程组的模版具体的步骤就是每次从未知主元中选取一个作为主元找到系数最大的一个方程将方程的主元项系数化1带入其他方程使得其他方程的该主元系数变成0#include<iostream>#include<cstdio>#include<cmath>using namespace std;#define eps...
2019-08-02 14:08:20
131
原创 poj3087(hash)
//// Created by xingchaoyue on 2019/7/27.//#include<iostream>#include<cstdio>#include<map>#include<string.h>using namespace std;typedef unsigned long long ull;typede...
2019-07-28 11:52:11
108
原创 luogu k层图
k层图典型例题就是可以任意选取k条边使得他们权值变化然后问最短路//// Created by xingchaoyue on 2019/7/27.//#include<iostream>#include<cstdio>#include<queue>#include<string.h>using namespace std;...
2019-07-27 18:51:27
156
原创 2019西安邀请赛总结
打铁了上来A题我写的时候过于紧张 以至于慢了好几分钟然后开M我觉得M就是二分加判断（出赛场之后一交流确实没错，但是我判断写的dijistra也不知道哪里写错了）队友一直在开L （zc推错了规律 最后cly重新按照题目写了好几个样例最后A掉，其实就应该用哈希存储集合状态然后打个表就可以，其实规律题也是我比较拿手的，但是M不知道为什么一直wa就没来得及做）最后半个小时cly一发过了...
2019-05-21 17:25:29
258
1
原创 traffic jam(Dijkstra)
没啥好说的...//// Created by xingchaoyue on 2019/5/16.//#include<iostream>#include<cstdio>#include<queue>#include<string.h>using namespace std;int n,m;int mp[1005][100...
2019-05-17 12:55:39
317
原创 luoguP1577（二分答案）
二分答案写了一下就出来了...但是在二分那里卡住了先po上代码 日后再解惑//// Created by xingchaoyue on 2019/5/15.//#include<iostream>#include<cstdio>using namespace std;int n,m;int a[10000+100];int ri = 0;i...
2019-05-15 16:08:56
191
原创 luoguP1182（二分搜索）
好久没写二分搜索题了这个题目大体意思就是给你一串数字让你选出连续的m段数字使得和最大的数字段的和最小就是二分答案//// Created by xingchaoyue on 2019/5/15.//#include<iostream>#include<cstdio>using namespace std;int n,m;const int ...
2019-05-15 15:10:19
126
原创 洛谷P2709(简单莫队）
#include<iostream>#include<cstdio>#include<math.h>#include<algorithm>using namespace std;const int maxn = 50005;typedef long long ll;ll c[maxn];ll sum[maxn];struct no...
2019-05-15 11:41:21
120
原创 Round560div3.E
E. Two Arrays and Sum of Functionstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given two arrays aand b, both of len...
2019-05-15 10:56:12
123
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人