JZYshuraK

分类

未归档(392)

/ 注册

全部文章（共392篇）

[bzoj2743][HEOI2012]采花_树状数组

采花 bzoj-2743 HEOI-2012 题目大意：给定n朵花，每朵花有一个种类，m次询问：一段区间中至少出现两朵花的种类的个数。注释：$1\le n,m\le10^6$。想法：这个题超级像HH的项链就是把那个题的$nxt$往后再延迟一个更新即可。最后，附上丑陋的代码......

2018-08-29

0 321

[bzoj3378][Usaco2004 Open]MooFest 狂欢节_树状数组

MooFest 狂欢节 bzoj-3378 Usaco-2004 Open 题目大意：给定一个n个数的a序列，每两个数之间有一个距离，两个点之间的权值为$max(a[i],a[j])*dis(i,j)$。注释：$1\le n\le 2\cdot 10^4$。想法：裙子说了，这种$max...

2018-08-28

0 353

[bzoj1878][SDOI2009]HH的项链_树状数组

HH的项链 bzoj-1878 SDOI-2009 题目大意：给定一个n个数的序列，m次查询。查询区间数的种类个数。注释：$1\le n \le 5\cdot 10^4$，$1\le m\le 2\cdot 10^5$。想法：在线的我不会啊qwq。我们考虑离线做法，将所有的询问以左...

2018-08-28

0 342

[bzoj1103][POI2007]大都市meg_dfs序_树状数组

大都市meg bzoj-1103 POI-2007 题目大意：给定一颗n个点的树，m次操作。将一条路的边权更改成0；查询一个点到根节点的点权和。开始的时候所有边的边权都是1。注释：$1\le n,m\le 2.5\cdot 10^5$。想法：我们先拉出dfs序。其实严格来讲是出栈入栈序...

2018-08-28

0 321

[bzoj1935][Shoi2007]Tree 园丁的烦恼 _树状数组

Tree 园丁的烦恼 bzoj-1935 Shoi-2007 题目大意：给定平面上的$n$个点，$m$次查询矩形点个数。注释：$1\le n,m\le 5\cdot 10^5$。想法：静态二维数点。 $Orz Winniechen$，真tm敢写$KD-Tree$，虽然$T$了.. ...

2018-08-28

0 284

[bzoj2226][Spoj5971]LCMSum_欧拉函数_线性筛

LCMSum bzoj-2226 Spoj-5971 题目大意：求$\sum\limits_{i=1}^nlcm(i,n)$ 注释：$1\le n\le 10^6$，$1\le cases \le 3\cdot 10^5$。想法：$\sum\limits_{i=1}^nlcm(i,n)$...

2018-08-26

0 293

[bzoj4282]慎二的随机数列_动态规划_贪心

慎二的随机数列 bzoj-4282 题目大意：一个序列，序列上有一些数是给定的，而有一些位置上的数可以任意选择。问最长上升子序列。注释：$1\le n\le 10^5$。想法：结论：逢N必选。N是可以任意选择的位置。具体的，我们将所有N踢出序列，将给定的权值-=前面N的个数。再在当...

2018-08-26

0 346

[bzoj2467][中山市选2010]生成树_快速幂

生成树 bzoj-2467 中山市选2010 题目大意：题目链接注释：略。想法：首先，考虑生成树的性质。每两个点之间有且只有一条路径。我们将每个五边形的5条边分为外面的4条边和内部的一条边，在此简称为外边和内边。那么显然，每个五边形的4条外边至少需要选3条。如果选了3条外边而且内边...

2018-08-26

0 326

[bzoj2783][JLOI2012]树_树的遍历

树 bzoj2783 JLOI2012 题目大意：给定一棵n个点的树。求满足条件的路径条数。说一个路径是满足条件的，当且仅当这条路径上每个节点深度依次递增且点权和为S。注释：$1\le n\le 10^5$，$1\le S,val_i\le 10^3$。想法：翻lijinnn的blog...

2018-08-26

0 278

[bzoj2213][Poi2011]Difference_动态规划

Difference bzoj-2213 Poi-2011 题目大意：已知一个长度为n的由小写字母组成的字符串，求其中连续的一段，满足该段中出现最多的字母出现的个数减去该段中出现最少的字母出现的个数最大。求这个个数。注释：$1\le n\le 10^6$。想法：“在线”的dp题。状...

2018-08-26

0 286