JZYshuraK

分类

未归档(392)

/ 注册

全部文章（共392篇）

Sticks Problem

Sticks Problem poj-2452 　　　　题目大意：给你一串n个数的数列a，上面的数为a1到an。我们求最大的y-x，其中，y和x满足1.x<y 2.任意的x<i<y，都有ai>ax&&ai<ay。　　　　注释：n<=50000...

2018-01-15

0 369

Sliding Window

poj2823 Sliding Window 　　　　题目大意：给你一个n个数的序列，有一个长度固定的窗口，求出两个数列，分别是窗口从左滑到右，窗口内的最小值和最大值，分两行输出。　　　　注释：n<=$10^6$，内存<=64. 　　　　　　想法：这内存是真恶心啊，正常的ST算法...

2018-01-14

0 283

Frequent Value

Frequent Value poj-3368 　　　　题目大意：给你n个数的数列，保证它是单调递增的。给你m个询问，每个询问是询问两个节点之间最长的连续的相等的数的长度。　　　　注释：n,m<=100000。　　　　　　想法：这道题是我做的第一道有点儿意思的RMQ(RMQ?猛戳)的...

2018-01-13

0 300

浅谈-RMQ

浅谈RMQ Today，我get到了一个新算法，开心....RMQ。今天主要说一下RMQ里的ST算法(Sparse Table)。 RMQ(Range Minimum/Maximum Query)，意思是对于一段区间，查询最大值或最小值的一种数据结构。首先，我们很容易想到线段树，时空复杂度均...

2018-01-13

0 332

古韵之鹊桥相会

jdoj1497-vijos1406古韵之鹊桥相会　　　　题目大意：给你一个m行n列的字母矩阵，有一个人，每一次可以将几个联通块打没。联通块的定义是两个挨着的字母，如果他们两个相同，那么就说他们两个是联通的。求：从上面到下面，最少打几次才可以到达。　　　　注释：n,m<21。　　　...

2018-01-11

0 387

宿命的PSS

jdoj1574-vijos1579 宿命的PSS 　　　　题目大意：给你一棵n个点的最小生成树。求：由这个最小生成树所构成的完全图的边权和的最小值且保证这个完全图的最小生成树是题目给定的且唯一的。　　　　注释：n<20000，边权<=int。　　　　　　想法：这时博主迄今做的...

2018-01-11

0 258

Tram

Tram 　　　　题目大意：给你一个图，这个图上有n点和边。点上有开关，开关开始指向一条道路，拨动开关可以使开关指向由开关出发的任意一条路径，读入，a,b，求，至少要拨动几次才能从a点走到b点。　　　　　注释：n<=100. 　　　　　　想法：最短路的题，由于n的范围，想采用floyd...

2018-01-10

0 275

The Beginning of the Graph Theory

The Beginning of the Graph Theory 　　　　是的，这不是一道题。最近数论刷的实在是太多了，我要开始我的图论与树的假期生活了。　　　　祝愿我吧？？！ShuraK...... 　　　　poj1847 　　　　poj1125 　　　　neooj1339 　　　...

2018-01-10

0 346

poj 3696 The Luckiest Number

The Luckiest Number 　　　　题目大意：给你一个int范围内的正整数n，求这样的最小的x，使得：连续的x个8可以被n整除。　　　　注释：如果无解输出0。poj多组数据，第i组数据前面加上Case i: 即可。　　　　　　想法：这题还是挺好的。我最开始的想法是一定有超级多的...

2018-01-03

0 440

求逆序对[树状数组] jdoj

求逆序对　　题目大意：给你一个序列，求逆序对个数。　　注释：n<=$10^5$。　　　　此题显然可以跑暴力。想枚举1到n，再求在i的后缀中有多少比i小的，统计答案即可。这显然是$n^2$的。这...显然过不去，我们思考如何优化？显然，这里的有些过程是重复的。我们将这个序列设为a序列...

2017-12-14

0 222