- 博客(293)
- 收藏
- 关注
RSS订阅
原创 |题目分类|BZOJ、Poj、Hdu题目分类
BZOJ:[数论]BZOJ 1477：裸的扩展欧几里得算法 [线段树]BZOJ 1593：经典线段树模型 [2-SAT]BZOJ 1823：2-SAT经典模型 [平衡树]BZOJ 2028：求大于x的最小值，set可以过 [树形DP]BZOJ 2060：经典树形DP模型 [2-SAT]BZOJ 2199：2-SAT经典模型 [树形DP, 缩点]BZOJ 2427：缩点后跑树上背包 [平
2017-02-07 15:27:58
2495
原创 |BZOJ 1633|字符串DP|[Usaco2007 Feb]The Cow Lexicon 牛的词典
BZOJ 1633 Luogu 2875 from: USACO 2007 Jan Sliver(USACO刷题第13题)刚开始根本没想到DP，什么kmp，AC自动机，后缀数组都想了。。看了题解才知道 解决字符串的几大武器：(字符串DP，字符串Hash，KMP，AC自动机，后缀家族……)本题设f[i]f[i]为给定串前ii个字符进行处理后最少删除的字符数。 刚开始想了个超时的方法。。然后发现
2017-06-17 17:17:11
586
原创 |BZOJ 1635|差分序列|[Usaco2007 Jan]Tallest Cow 最高的牛
BZOJ 1635 Luogu 2879 from: USACO 2007 Jan Sliver(USACO刷题第12题)之前看完题目想到差分约束，然后是个区间不知道怎么搞。。看完题解是差分序列。。 差分序列和差分约束并不是毫无关系啊。。差分约束运用于两个元素，差分序列运用于区间。。本题对于每个约束a,ba,b，如果a>ba>b，显然，交换不会影响结果 我们设f[i]f[i]为差分序列，然后
2017-06-17 11:37:37
576
原创 |BZOJ 1634|贪心|[Usaco2007 Jan]Protecting the Flowers 护花
BZOJ 1634 Luogu 2878 from: USACO 2007 Jan Sliver(USACO刷题第11题)刚开始naive的认为比较函数是第一关键字dd第二关键字tt，狂炸的我..对于两头牛a,ba, b，他们的先后顺序不影响其他牛吃花的个数 那么考虑 aa在bb前面，那么吃的花为2∗d[b]∗t[a]2*d[b]*t[a] bb在aa前面，那么吃的花为2∗d[a]∗t[b
2017-06-16 19:49:10
494
原创 |BZOJ 1649|二维背包|[Usaco2006 Dec]Cow Roller Coaster
BZOJ 1649 Luogu 2854 from: USACO 2006 Dec Sliver(USACO刷题第10题)显然是二维费用01背包。 但是直接做会超时，而且还有连接的限制。 根据题意可以知道只有在wi[i]+xi[i]=jwi[i]+xi[i]=j才需要考虑转移 那么我们设f[i][j]f[i][j]为铺到ii,成本为jj的最大有趣值 那么有下列转移方程 f[xi[i]+
2017-06-16 19:13:06
407
原创 |BZOJ 1650|二分|贪心|[Usaco2006 Dec]River Hopscotch 跳石子
BZOJ 1650 Luogu 2855 from: USACO 2006 Dec Sliver(USACO刷题第9题)最小值最大，显然二分。 二分最小值最大距离，然后贪心处理。 这里我们在头尾各增加一个石头，贪心时先从第一个石头开始记为ll，然后往后扫描，当前扫描的石头记为rr，如果st[r]−st[l]<midst[r]-st[l]<mid的话，说明l,rl, r中间的石头就算都移走都不
2017-06-15 19:28:01
533
原创 |BZOJ 1648|DFS|[Usaco2006 Dec]Cow Picnic 奶牛野餐
BZOJ 1648 Luogu 2853 from: USACO 2006 Dec Sliver(USACO刷题第8题)记录一下每个牧场的奶牛个数，之后如果一个牧场有牛就dfs遍历，把遍历到的点的tot[i]tot[i]都加上这个奶牛数，然后最后统计每个牧场如果tot[i]=ktot[i]=k那么就是一个答案。#include<cstdio>#include<cstring>#include
2017-06-15 18:35:53
372
原创 |BZOJ 1661|暴力|[Usaco2006 Nov]Big Square 巨大正方形
BZOJ 1661 Luogu 2867 from: USACO 2006 Nov Sliver(USACO刷题第7题)枚举两个点，第二个点要在第一个点的右下，那么这样我们就可以根据一个公式来求另外两个点了。之后四个点求出来后判断四个点是否都可行，然后记录这四个点中J的数量，如果>=3>=3，则这个正方形就是可行的，更新答案即可。#include<cstdio>#include<cstring
2017-06-14 19:40:27
614
原创 |BZOJ 1660|单调栈|[Usaco2006 Nov]Bad Hair Day 乱发节
BZOJ 1660 Luogu 2866 from: USACO 2006 Nov Sliver(USACO刷题第6题)单调栈，对于每个数，他后面所有比他小的数(中间不能有大于他的数)都会对答案做出贡献。 那么我们可以用单调栈来维护这个”后面所有比他小的数(中间不能有大于他的数)”#include<cstdio>#include<cstring>#include<algorithm>#
2017-06-13 19:38:52
450
原创 |BZOJ 1652|区间DP|[Usaco2006 Feb]Treats for the Cows
BZOJ 1652 Luogu 2858 from: USACO 2006 Feb Sliver(USACO刷题第5题)显然DP。 设f[i][j]f[i][j]为左取ii个，右取jj个的最大值 初值： f[x][0]=∑i=1xvi[i]∗if[x][0] = \sum_{i=1}^{x}vi[i]*i f[0][x]=∑i=nxvi[i]∗(i−n+1)f[0][x] = \sum_
2017-06-12 19:12:14
336
原创 |BZOJ 1651|差分序列|[Usaco2006 Feb]Stall Reservations 专用牛棚
BZOJ 1651 Luogu 2859 from: USACO 2006 Feb Sliver(USACO刷题第4题)首先需要发现的是，覆盖次数最多的点就是答案 然后可以用线段树求解了 但是这里要介绍一个很有用的东西，差分序列 差分序列ff记录a[i]−a[i−1]a[i]-a[i-1]的值，aa为原序列 那么根据定义可以发现差分序列的前缀和就是原序列的数 那么输入a,ba,b, 我
2017-06-11 21:16:40
425
原创 |BZOJ 1655|无限背包|高精度|[Usaco2006 Jan] Dollar Dayz 奶牛商店
BZOJ 1655 poj 3181 from: USACO 2006 Jan Sliver(USACO刷题第3题)很容易看出本题是个无限背包方案数的dp，但是本题数据大会爆long long，那就可以把dp数组拆分为两个数组，类似于高精度压位地做#include<cstdio>#include<cstring>#include<algorithm>#include<stack>#inc
2017-06-11 18:53:56
428
原创 |BZOJ 1654|强连通分量|[Usaco2006 Jan]The Cow Prom 奶牛舞会
BZOJ 1654 Luogu 2863 from: USACO 2006 Jan Sliver(USACO刷题第2题)tarjan找强连通分量，最后输出强连通分量保含节点个数>=2>=2的强连通分量个数即可，几乎是模板题#include<cstdio>#include<cstring>#include<algorithm>#include<stack>#include<vector>
2017-06-11 17:21:10
413
原创 |BZOJ 1656|BFS|[Usaco2006 Jan] The Grove 树木
bzoj 1656 luogu 2864 from: USACO 2006 Jan (USACO刷题第1题)一道BFS。之前没看题解没什么思路搜索，看了题解后发现可以随便找一棵树然后垂直于坐标轴作一条射线，该线内的方块不可到达(相当于障碍物)。BFS记录到达每个点的最短步数，之后再在这条射线上进行合并局部解，得到最后的最优解。本题咋一看就是一个BFS，但是他要求绕着树林走，那么画一条射线来分解
2017-06-11 16:13:18
433
原创 |算法讨论|RMQ 学习笔记
模板及讲解 运用st表实现区间询问区间最大/最小，初始化时间复杂度O(nlogn)O(nlogn), 查询O(1)O(1) 模板题：poj 3264#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define ms(i, j) memset(i, j, sizeof i)using namespac
2017-06-11 10:36:04
286
原创 |poj 3264|RMQ|Balanced Lineup
poj 3264RMQ模板题。#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define ms(i, j) memset(i, j, sizeof i)using namespace std;const int MAXN = 50000 + 5;int n, q;int h[MAXN], fmaxi
2017-06-11 10:27:39
299
原创 |poj 1743|后缀数组|Musical Theme
poj 1743注意用heightheight分组如果最后一组最后一个元素在序列末，那么要进行处理！最方便是直接<=n<=n，还要注意的是不能重复，而且是mini+x<maximini+x<maxi不能是mini+x<=maximini+x<=maxi本题求的是长度最少为5的重复子串，并且重复子串可以加上或者减去一个数。我们将数字处理一下取差值，然后直接做，之后再结果+1+1即可#include<c
2017-06-10 19:50:41
306
原创 |poj 2299|权值线段树|Ultra-QuickSort
poj 2299 注意开long long 权值线段树就是线段树每个节点存每个权值出现的次数，本题求逆序对应该算一个比较简单的权值线段树，注意离散化#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<queue>using namespace std;#define ms(i, j)
2017-06-10 16:10:53
408
原创 |Poj 3581|后缀数组|Sequence
poj 3581 1. 因为第一个数比后面的大，所以将原串翻转后找出排第ii位的后缀输出，符合SA[i]>=2SA[i]>=2的最小ii(后缀数组中的排列是字典序) 2. 之后将之前已经处理的数据删掉，然后题目变为将剩下的数据分为两份翻转后字典序最小，那么我们设SS为这个序列，S1,S2,...,Sk,Sk+1,...SnS_1, S_2, ..., S_k, S_{k+1},...S_n，其中
2017-06-10 14:41:24
517
原创 |Poj 3623|后缀数组|Best Cow Line, Gold
poj 3623 字符串翻转后的和原串后的数组进行求后缀数组，然后之后两个指针i，ji，j选择两端rkrk值最小的输出，注意格式#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#define ms(i, j) memset(i, j, sizeof i)#define ll long longusi
2017-06-06 19:49:57
439
原创 |BZOJ 3531|树链剖分|动态开点线段树|[Sdoi2014]旅行
BZOJ 3531树剖以后每个宗教建立一棵线段树，节点太多用传统方法开数组肯定不行，这里进行改进，使用了动态开点线段树，即需要这个点再开这个点。#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#define ms(i, j) memset(i, j, sizeof i)#define ll long l
2017-06-06 18:46:24
430
2
原创 |UVA 11729|贪心|Commando War
UVA 11729 训练指南 第一章 例2 贪心，把完成任务时间最长的优先进行#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define ms(i, j) memeset(i, j, sizeof i)const int MAXN = 1000 + 5;struct data{
2017-06-03 14:56:38
427
原创 |UVA 11292|贪心|Dragon of Loowater
UVA 11292 训练指南 第一章 例1 两个数组排序后贪心处理即可，水题一道。#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define ms(i, j) memeset(i, j, sizeof i)#define FN2 "UVA11292"const int MAXN = 20
2017-06-03 14:54:23
382
原创 |poj 3261|后缀数组|二分|Milk Patterns
poj 3261还是一样的，这题是整形数字，也可以转为字符串算法做，用后缀数组，二分以后分组判定就可以了#include<cstdio>#include<cstring>#include<algorithm>#define ms(i, j) memset(i, j, sizeof i)#define FN2 "poj3261" using namespace std;const int M
2017-05-29 21:27:42
418
原创 |spoj 694|后缀数组|Distinct Substrings
spoj 694给出一个字符串，求字符串中不相同的子串个数。我们可以知道，字符串中的每个子串都是某个后缀的前缀，于是题目转化为求不相同的后缀的前缀问题。对于每一个SA[k]SA[k]开始的后缀，将会增加n−SA[k]+1n-SA[k]+1个后缀，而其中height[k]height[k]个是和前面的字符串的前缀是相同的。所以答案就是所有n−SA[k]+1−height[i]n-SA[k]+1-hei
2017-05-29 16:14:04
344
原创 |poj 1226|后缀数组|二分|Substrings
poj 1226几本上与这题一样，只不过这里还要把读入的字符串的翻转后的字符串也要连上#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#define ms(i, j) memset(i, j, sizeof i)#define FN2 "poj1226" using namespace std;con
2017-05-29 14:01:05
447
原创 |poj 3294|后缀数组|二分|Life Forms
poj 3294和这题差不多，二分后后缀数组heightheight判断，此题要输出所有的解，用个数组存下每个解在aa中的起始位置即可。不同的是，此题判断时一定要找到一个height[i]<xheight[i]<x或者循环完毕heightheight才能更新解，这样才能防止重复解出现。 (ps: vivi数组不要开大了，否则memset时容易TLE)#include<cstdio>#includ
2017-05-29 09:36:47
379
原创 |hdu 2328|后缀数组|二分|Corporate Identity
hdu 2328给出n个字符串，输出他们的最长公共子串，无解输出”IDENTITY LOST”用不同的符号连接每个字符串，然后二分公共子串的长度，在heightheight数组中看有没有连续nn个heightheight大于公共子串的长度，如果有，那么更新答案。 (此题暴力比SA快，而且poj上用SA一直TLE，Hdu上1840ms就过了)#include<cstdio>#include<cst
2017-05-28 18:54:28
583
原创 |poj 2774|后缀数组|Long Long Message
poj 2774给出两个字符串，求这两个字符串的公共子串。我们可以连接两个字符串，中间插入$\$，然后构造后缀数组，用heightheight数组解决。以abbbc和bbc为例。 因为后缀数组是字典序排的，所以排名最近的两个后缀拥有的最大公共前缀一定比不相邻的长。所以，由图可知，只要后缀ii的位置在串1的范围，后缀i−1i-1在串2的范围(反过来亦可)，那么就可以用height[i]heigh
2017-05-27 22:34:11
377
原创 |算法讨论|后缀数组 学习笔记
模板及讲解 解决字符串的有力工具。 直接上代码，注释讲解(此题为uoj #35)#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#define ms(i, j) memset(i, j, sizeof i)#define FN2 "uoj35" using namespace std;const
2017-05-25 21:15:17
288
原创 |BZOJ 2763|最短路|[JLOI2011]飞行路线
BZOJ 2763分层图最短路注意：priority_queue默认排序序列是从大到小的，所以重载小于符号时要a>b 以后权值一律写w，不要用v或c！#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<queue>#define fo(i, j, k) for (i=(j);i<=(k)
2017-05-20 23:19:19
402
原创 |BZOJ 4196|树链剖分|线段树|[Noi2015]软件包管理器
BZOJ 4196树链剖分支持修改查找子树和到根的路径权值和即可解决，注意pushdown放前面注意lc，rc会爆的情况#include<cstdio>#include<cstring>#include<algorithm>#define fo(i, j, k) for (i=(j);i<=(k);i++)#define fd(i, k, j) for (i=(k);i>=(j);i--)
2017-05-20 20:43:48
348
原创 |poj 1144|割顶|Network
poj 1144直接割顶模板。注意此题卡前向星#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#define ms(i ,j) memset(i, j, sizeof i)#define rd(a) scanf("%d", &a)#define rd2(a, b) scanf("%d%d", &a,
2017-05-20 15:28:19
304
原创 |poj 1523|割顶|[HAOI2015]SPF
poj 1523 直接模板即可。 注意不一定是连通图。#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#define ms(i ,j) memset(i, j, sizeof i)#define rd(a) scanf("%d", &a)#define rd2(a, b) scanf("%d%d"
2017-05-20 15:22:13
315
原创 |BZOJ 4034|树链剖分|线段树|[HAOI2015]树上操作
BZOJ 4034树剖后线段树维护。 此题要修改子树的权，根据树剖性质子树是连续的一段，运用时间戳思想即可。注意开long long，第一次没开就WA了(痛不欲生)#include<cstdio>#include<cstring>#include<algorithm>#define fo(i, j, k) for (i=(j);i<=(k);i++)#define fd(i, k, j)
2017-05-19 20:28:22
383
原创 OI中的常用数据生成
一、随机生成一个小于等于nn的数int RAND(int n) { srand((int)time(0)); return rand()%n+1;}二、随机生成排列int t[MAXN];int mp(int n) { int i; srand((int)time(0)); fo (i, 1, n) t[i] = i; random_shuff
2017-05-19 17:55:59
1055
原创 |poj 3237|树链剖分|线段树|Tree
poj 3237树剖+线段树。 刚开始想用记录该区域被NEGATE了几次，结果发现不可行，翻别人博客发现了原来维护最大值maxvmaxv和最小值minvminv，NEGATE就是maxv=−minv,minv=maxvmaxv=-minv, minv=maxv, 正确性显然。 #include<cstdio>#include<cstring>#include<algorithm>#defin
2017-05-18 21:00:19
348
原创 |hdu 3966|树链剖分|线段树|Aragorn's Story
hdu 3966裸树剖+线段树维护，while写成if， 数组开小搞得我调试了好久。。静态查错真的不能快了#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio>#include<cstring>#include<algorithm>#define fo(i, j, k) for (i=(j);i<=(
2017-05-18 18:44:24
340
原创 |poj 2186|强连通分量|Popular Cows
poj 2186这题求所有满足被所有点能够到达的节点，那么我们可以进行缩点，缩点之后得到一个有向DAG图，统计新图的出度，如果有一个强连通分量的出度是=0的，那么输出这个强连通分量的大小，如果有多个，输出0#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<stack>#define ms
2017-05-16 19:09:12
318
原创 |算法讨论|树链剖分 学习笔记
模板及讲解 树链剖分解决树上的修改问题。 将树剖成一条条链，再用线段树、树状数组等维护#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#define fo(i, j, k) for (i=(j);i<=(k);i++)#define fd(i, k, j) for (i=(k);i>=(j);i--
2017-05-15 21:03:55
327
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人