JZYshuraK

分类

未归档(392)

/ 注册

全部文章（共392篇）

[bzoj4010][HNOI2015]菜肴制作_贪心_拓扑排序

菜肴制作 bzoj-4010 HNOI-2015 题目大意：给定一张n个点m条边的有向图，求一个toposort，使得：（1）满足编号为1的点尽量在前；（2）满足（1）的情况下编号为2的点尽量在前，以此类推。注释：$1\le n,m\le 10^5$，$1\le cases \le 3$。 ...

2018-07-31

0 313

[bzoj1855][Scoi2010]股票交易_动态规划_单调队列

股票交易 bzoj-1855 Scoi-2010 题目大意：说不明白题意系列++...题目链接注释：略。想法：这个题还是挺难的。动态规划没跑了状态：dp[i][j]表示第i天手里有j个股票的最大获利。转移：第i天可以选择搞事情或者什么都不干。如果不买不卖的话，有dp[i...

2018-07-31

0 339

[bzoj1342][Baltic2007]Sound静音问题_单调队列

Sound静音问题 bzoj-1342 Baltic-2007 题目大意：给定一个n个数的序列，求所有的长度为m的区间，使得区间内最大值减去最小值不超过阈值c。注释：$1\le n \le 10^6$，$1\le m\le 10^4$。想法：单调队列裸题。定长区间最值问题显然可以用...

2018-07-31

0 274

[bzoj4385][POI2015]Wilcze doły_单调队列

Wilcze doły bzoj-4385 POI-2015 题目大意：给定一个n个数的序列，可以将连续的长度不超过d的区间内所有数变成0，求最长的一段区间，使得区间和不超过p。注释：$1\le n,m\le 10^6$，$1\le a_i$。想法：感觉自己就没会过单调队列... .....

2018-07-31

0 286

[bzoj1901][Zju2112]Dynamic Rankings_主席树

Dynamic Rankings bzoj-1901 Zju-2112 题目大意：给定一个n个数的序列，m个操作，支持：单点修改；查询区间k小值。注释：$1\le n,m\le 10^4$。想法：如果这个教树套树的话，我也没办法。其实就是借用了树状数组的思想，我们在这里叫它...*...

2018-07-30

0 253

[bzoj4530][Bjoi2014]大融合_LCT

大融合 bzoj-4530 Bjoi-2014 题目大意：n个点，m个操作，支持：两点连边；查询两点负载：负载。边(x,y)的负载就是将(x,y)这条边断掉后能和x联通的点的数量乘以能和y联通的点的数量。数据保证任意时刻，点和边构成的都是森林或者树。注释：$1\le n,m\le 10^5$。...

2018-07-30

0 321

[bzoj2850]巧克力王国_KD-Tree

巧克力王国 bzoj-2850 题目大意：给出n块巧克力，每块巧克力都有自己的两个参数x和y和本身的价值val，询问：m个人，每个人有两个系数和一个限度a,b,和c。求所有ax+by<=c的巧克力价值和。注释：$1\le n,n\le 5\cdot 10^4$。想法：我们将巧克力...

2018-07-30

0 286

[bzoj4154][Ipsc2015]Generating Synergy_KD-Tree_dfs序

Generating Synergy bzoj-4154 Ipsc-2015 题目大意：给定一棵n个节点树，m个操作，支持：将一个点周围所有距该点距离不超过l的子结点的颜色改成另一种颜色；查询单点颜色。每个点的颜色开始都是1。注释：$1\le n,m\le 10^5$ 想法：这就是一个典...

2018-07-30

0 286

[bzoj1941][Sdoi2010]Hide and Seek_KD-Tree

Hide and Seek bzoj-1941 Sdoi-2010 题目大意：给出平面上n个点，选出一个点，使得距离这个点的最远点曼哈顿距离减去距离这个点的最近非己点的曼哈顿距离最小。输出最小曼哈顿距离差。注释：$1\le n \le 5\cdot 10^5$。想法：这个题的话处理方法...

2018-07-30

0 286

[bzoj2648/2716]SJY摆棋子_KD-Tree

SJY摆旗子 bzoj-2648 题目大意：平面上有n个黑子。有m个操作，可以下一颗白子，查询与曼哈顿距离下最近黑子之间的曼哈顿距离，或者下一颗黑子。注释：$1\le n,m\le 5\cdot 10^5$ 想法：KD-Tree维护近邻点对问题。这类问题和那个定区域查询问题不一样，那...

2018-07-30

0 486