JZYshuraK

分类

未归档(392)

/ 注册

全部文章（共392篇）

[poj3321]Apple Tree_dfs序_树状数组

Apple Tree poj-3321 　　　　题目大意：给你一个根固定的树，每一个点的点权是0或1，查询子树点权和。　　　　注释：$1\le n \le 10^5$。　　　　　　想法：刚刚学习dfs序，刷到水题偶哈哈。　　　　　　　　什么是dfs序？就是在遍历树的时候记录的每个点的出...

2018-04-03

0 420

[poj3974]Palindrome_Manacher

Palindrome poj-3974 　　　　题目大意：求字符串的最长回文子串。　　　　注释：$1\le strlen(s) \le 10^6$. 　　　　　　想法：介绍一种字符串算法——Manacher。求以每一个字符和字符间隔为回文中心的回文半径长度。什么是Manacher？　　　...

2018-03-30

0 370

[poj1062]昂贵的聘礼_最短路_离散化

昂贵的聘礼 poj-1062 　　　　题目大意：原文链接？不是英文题，自己看　　　　注释：$1\le N \le 100$。　　　　　　想法：开始的想法有些过于简单，因为落下了一个条件：就是等级限制是一条路径上的任意两点而不是相邻两点。所以我们考虑枚举当前可接受等级的区间。显然最多只有10...

2018-03-29

0 384

[poj1068]Parencodings_模拟

Parencodings 　　　　题目大意：给你一个P序列，表示从左到右的右括号左边有多少左括号，求M序列。　　　　注释：M序列定义为每一个右括号左边最近的没有被之前的右括号匹配的括号之间，有多少已经匹配的括号队对。$1\le number for P\le 20$。　　　　　　想法：暴力...

2018-03-28

0 346

[poj1012]Joseph_Joseph

Joseph 　　　　题目大意：给你2*k个人，前k个是好人，后k个是坏人，编号从1到2*k。每次从上一个死掉的人的下一个开始查m个人并将第m个人杀死。问最后剩下的全是好人的m是多少。　　　　注释：$1\le k \le 14$。　　　　　　想法：开始觉得自己想的有些简单，然后发现其实就是...

2018-03-28

0 339

[poj3984]迷宫问题_bfs

迷宫问题　　　　题目大意：给你一个5*5的矩阵，求左上角到左下角的最短路径。　　　　注释：0或1的矩阵，1表示不能走，0表示能走，保证有唯一最短路径。　　　　　　想法：bfs爆搜练习题。通过其实点，定义方向数组，然后进行bfs遍历即可。　　　　最后，附上丑陋的代码... ... ...

2018-03-28

0 271

[luogu1168]中位数_优先队列

中位数　　　　题目大意：输出读入的前2*k+1个数的中位数。一共有n个数，按照读入顺序。　　　　注释：$1\le n \le 10^9$。　　　　　　想法：这是优先队列的一个应用qwq。我们弄两个堆。小根堆和大根堆，保证：大根堆中的任意一个数都小于小根堆，而且大根堆中的元素个数始终比小根...

2018-03-26

0 307

[poj3468]A Simple Problem with Integers_线段树

A Simple Problem with Integers 　　　　题目大意：给出n个数，区间加、查询区间和。　　　　注释：1<=n,q<=100,000.(q为操作次数)。　　　　　　想法：嗯...学了这么长时间线段树，发现我tm竟然不会lazy标记？？！好吧，看来线段树又...

2018-03-26

0 422

[poj2185]Milking Grid_KMP

Milking Grid poj-2185 　　　　题目大意：给出一个字符矩阵，求最小覆盖矩阵(可以残余). 　　　　注释：$1\le R\le 10^5$，$1\le C \le 75$ 　　　　　　想法：和bzoj1355不同的是，bz那题求的是最小覆盖子串。这题其实异曲同工。Discus...

2018-03-23

0 307

[bzoj1355][Baltic2009]Radio Transmission_KMP

Radio Transmissio bzoj-1355 Description 　　　　给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少. Input 　　　　第一行给出字符串的长度,1 < L ≤ 1,000,0...

2018-03-22

0 381