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) 未归档(72) 算法(1) 背包问题(1)

/ 注册

全部文章（共109篇）

【POJ2001】Shortest Prefixes

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

2017-07-24

0 515

【模板】AC自动机

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

2017-07-23

0 389

【POJ2752】seek the name,seek the fame

题目链接：http://poj.org/problem?id=2752 题解：一直跳next就好 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm>...

2017-07-23

0 458

【BZOJ3555】【Ctsc2014】企鹅QQ

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

2017-07-23

0 420

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

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

2017-07-23

0 407

【洛谷2258】子矩阵

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

2017-07-23

0 400

【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 498

【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 396

【CDOJ1152】小panpan学图论

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

2017-07-22

0 463

【CDOJ1059】秋实大哥与小朋友

题目链接：http://mozhu.today/#/problem/show/1059 题解：区间更新单点查询，裸裸的树状数组/线段树考虑到m范围太大，所以要离散化因为是单点修改，所以没有涉及到的点是不需要管的将所有修改和询问记录下来离线处理，离散化之后正常做就好了 #inclu...

2017-07-22

0 466