Scorpioch

未归档

01分数规划(1) dp(4) gcd(2) NOIP膜你赛(1) OIer的刷题记录(25) poj(3) sgu(1) 【神奇的】模板(1) 二分(1) 动态规划 - 数位DP(1) 动态规划 - 概率DP(1) 动态规划 - 背包(2) 字符串 - KMP(1) 搜索(1) 数学(2) 数据结构 - 线段树(4) 数论(2) 算法(1) 背包问题(1)

/ 注册

全部文章 / 未归档（共55篇）

【uva11732】"strcmp()" Anyone?

题目链接：https://vjudge.net/problem/UVA-11732 题解：建一棵trie树，每次经过一个点，该点的计数器+1 插入的时候顺便统计，分字符相同（*2）和不同（*1）讨论一下就好注意最后一位的比较，可以都赋值为47（’\’）考虑到串只有4000个但串比较长...

2017-07-24

0 701

【POJ2001】Shortest Prefixes

题目链接：http://poj.org/problem?id=2001 题意：给出若干字符串，求每一个字符串的最短唯一表示前缀题解：一看这种找前缀的东西肯定是trie 插入的时候每路过一个点，cnt++ 查询的时候走到第一个cnt=1即可，如果没有，就输出这个串 #include&l...

2017-07-24

0 516

【模板】AC自动机

传送门 //by sdfzchy #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namesp...

2017-07-23

0 391

【BZOJ3555】【Ctsc2014】企鹅QQ

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3555 题解：先将所有字符串哈希枚举删去哪一位上的字母，用哈希判重删去第i为的字母对应的哈希值Hash=Hash-s[i]*base^(len-i) 注意不能把所有的放到一起做...

2017-07-23

0 421

【模板】【洛谷P3370】字符串哈希

base取个131,13331……都可以 unsigned long long自然取模的话容易被卡 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> ...

2017-07-23

0 411

【洛谷2258】子矩阵

题目链接：https://www.luogu.org/problem/show?pid=2258 题解：这貌似是普及组的题诶如果行和列都爆搜的话， <nobr> O(2n+m×r×c) </nobr> 剪剪枝或许可以（hhh我都不信）枚举组合时，...

2017-07-23

0 401

【BZOJ3670】【NOI 2014】动物园(KMP)

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3670 题解：以前写过一次但不是很懂，所以重新写了一下首先构造一个cnt数组表示前缀等于后缀的子串的数目那么cnt【i】=cnt【next【i】】+1，可以在求next同时求出来...

2017-07-23

0 501

【POJ1823】Hotel

题目链接：http://poj.org/problem?id=1823 题意：有三种操作 1 A M 表示从 A 到 A+M-1 住进M个人 2 A M 表示从 A 到 A+M-1 搬到M个人 3 表示查询这个hotel 连续的空房间有多少题解：区间合并问题线段...

2017-07-22

0 397

【CDOJ1152】小panpan学图论

题目链接：http://mozhu.today/#/problem/show/1152 题解：有些点如果未被标记但在最短路上，那么就满足题意首先判断什么情况下是No 如果k==n，无法构造如果有一个未被选中的点与其他所有未被选中的点相连，剩下n-1个点构成完全图，在这个图中添加任意一...

2017-07-22

0 467

【HDU1215】七夕节

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1215 题解：水题从小到大枚举将数字加到它的倍数上 <nobr> O(nlogn) </nobr>预处理 <nobr> O(1) ...

2017-07-21

0 448