Spy97

分类

2018 Multi-University Training(7) 2019牛客多校(1) AC自动机(1) BFS(2) CCPC(7) Codeforces(16) DFS序(1) Hash(4) ICPC(6) pb_ds(2) 主席树(2) 分块(2) 分治(2) 动态规划(2) 博弈(4) 后缀数组(6) 回文树(2) 图论(15) 差分约束系统(1) 思维(8) 数学(2) 未归档(5) 树(5) 树链剖分(3) 模拟(1) 模拟退火(1) 矩阵快速幂(2) 线性基(1) 线段树(7) 莫队(1) 计算几何(30) 贪心(2)

/ 注册

全部文章（共151篇）

HDU 6194

string string string Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2270 Acce...

2018-03-17

0 418

POJ 3693

题目描述：给出一个字符串，求重复次数最多的子串。若多个，输出字典序最小的。题解：先穷举长度 L，然后求长度为 L 的子串最多能连续出现几次。首先连续出现1 次是肯定可以的，所以这里只考虑至少 2 次的情况。假设在原字符串中连续出现 2 次，记这个子字符串为 S，那么 S 肯定包括了字符 r[0]...

后缀数组 POJ

2018-03-04

0 616

URAL 1297 最长回文子串

题目描述：给一个字符串，求最长回文子串，若有多个，输出最先出现的。注意：题目给的字符串要删去除字母外的其他字符，再进行求解。题解：设原串为s，在s尾部加一个特殊字符，然后再将s逆序添加在特殊字符的后面。一开始我的思路是直接求最长公共子串，然后出现了反例。abefba，求解是ab，但正确答案是a...

2018-03-03

0 478

POJ 1743

题目描述：给一组数字串，求不可重叠的最长公共子串，如果长度大于5，输出长度，否则输出0。注意：“公共子串”的定义为，两子串的对应位置的元素的差值相同即可。如：1 2 3 和 6 7 8 即满足条件，他们对应位置的差值是2。题解：我们如果有两个满足条件的子序列a[i],a[i+1],…a[i+...

2018-03-01

0 445

HDU 4691

题解：后缀数组求两个子串的LCP。用ST表求height数组中两个子串rank之间的最小值，即为子串的LCP。代码： #include<bits/stdc++.h> #define N 200010 #define LL long long using namespace std; ...

2018-02-28

0 549

HDU 1403

题目描述：给出两个字符串，求最长公共子串的长度。题解：后缀数组。将两个字符串合并成一个，中间加一个字符'0'，然后求出height数组。因为以最长公共子串为前缀的子串，他们的rank肯定相差为一，然后遍历sa数组，判断sa[i]和sa[i-1]的位置是否位于字符'0'的两侧，符合条件的最大的he...

2018-02-27

0 558

HDU 3394

题目描述：n个地点，m条路，要规划旅游路线（经过多个地点），必须是个环形。如果一条路属于多条旅游路线，就可能发生相撞，如果一条路不属于任何旅游路线，就统计一下。要求输出不属于任何旅游路线的路的数目以及会相撞的路的数目。题解：点双联通分量问题。第一问：桥的数量；第二问：如果一个联通分量中边的数...

2018-01-29

0 401

HDU 4738

题目描述：曹操在长江上修了n个岛，m座桥，桥上有一定士兵把守。刘备派人去炸一座桥，使得避免所有岛屿连成一起。要求派出的人不少与桥上把守的士兵，问最少派多少人。这是裸的割顶（割点）、割桥问题，找出所有的割桥，求最小值即可。坑点： 1、重边问题，判断如果“割桥”有重边，那么其实不是割桥，不能考...

2018-01-27

0 330

ICPC 2015 北京 Today Is a Rainy Day

题目链接：https://vjudge.net/problem/UVALive-7263 或者：http://hihocoder.com/problemset/problem/1251 题目大意：给你两个字符串，问你从一个变成另一个的最少变化次数。变化规则有二，一是将某一字符变成另一...

2017-12-10

0 456

ICPC 2017 北京 Liaoning Ship’s Voyage

题目地址：http://hihocoder.com/problemset/problem/1633?sid=1234017 题目大意：在二维平面内，船从(0,0)出发到(n-1,n-1)结束，求最短路，要求：一个点可以向周围8个方向走，距离都为1，并告诉哪些点不可以走，同时要求路线不可以穿过...

2017-11-19

0 508