JZYshuraK

分类

未归档(392)

/ 注册

全部文章（共392篇）

[bzoj3192][JLOI2013]删除物品_树状数组_栈

删除物品 bzoj-3192 JLOI-2013 题目大意：给你n个物品，分成2堆。所有的物品有不同的优先级。我只可以将一堆中的堆顶移动到另一个堆的堆顶。而如果当前物品是全局所有物品中优先级最高的，我可以直接将其删除。询问最小移动多少次，删除不计入总次数。注释：$1\le n\le 10^5$...

2018-05-25

0 424

[bzoj3694]最短路_树链剖分_线段树

最短路 bzoj-3694 题目大意：给你一个n个点m条边的无向图，源点为1，并且以点1为根给出最短路树。求对于2到n的每个点i，求最短路，要求不经过给出的最短路树上的1到i的路径上的最后一条边。注释：$1\le n \le 4000$，$1\le m\le 10^5$。想法：对于任意两个...

2018-05-25

0 366

[bzoj3747][POI2015]Kinoman_线段树

Kinoman bzoj-3747 POI-2015 题目大意：有m部电影，第i部电影的好看值为w[i]。现在放了n天电影，请你选择一段区间l~r使得l到r之间的好看值总和最大。特别地，如果同一种电影放了两遍及以上，那么这种电影的好看值将不会被获得。注释：$1\le m \le n \le 1...

2018-05-24

0 333

[bzoj1598][Usaco08Mar]牛跑步_A*_Dijkstra

牛跑步 bzoj-1598 题目大意：给你n个点，m条边的有向图。求从1到n的严格的第k短路。注释：$1\le n\le 1000$，$1\le m \le 10,000$，$1\le k \le 100$。想法：　　A*：俗称机器人走路算法。就是说从一个点走到另一个点的最短路径，显然...

2018-05-24

0 330

[bzoj1592][Usaco09Feb]Making the Grade 路面修整_动态规划

Making the Grade 路面修整 bzoj-1592 题目大意：给你n段路，每段路有一个高度h[i]，将h[i]修改成h[i]$\pm\delta$的代价为$\delta$，求将这n段路修成非严格单调的最小代价。注释：1$\le$n$\le$2000，$1\le A_i\le 10^...

2018-05-24

0 274

[bzoj3339]Rmq Problem||[bzoj3585]mex_线段树

Rmq Problem bzoj-3339||mex bzoj-3585 题目大意：给定一个长度为n的数列a，多次讯问区间l,r中最小的不属于集合{$A_l,A_{l+1}...A_r$}的非负整数。注释：n,q$\le$200,000 ; 0$\le A_i \le$200,000 ; $A...

2018-05-24

0 302

[bzoj1925][Sdoi2010]地精部落_递推_动态规划

地精部落 bzoj-1925 Sdoi-2010 题目大意：给你一个数n和模数p，求1~n的排列中满足每一个数的旁边两个数，要么一个是边界，要么都比它大，要么都比它小(波浪排列个数) 注释：$1\le n\le 4200$ , $1\le p\le 10^9$。想法：神题！这题标签给的是dp...

2018-05-13

0 305

[bzoj1047][HAOI2007]理想的正方形_动态规划_单调队列

理想的正方形 bzoj-1047 HAOI-2007 题目大意：有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。注释：$2\le a,b,n\le 10^3$，$n\le min(a,b)$。想法：我的思路简直要死。通常的，我...

2018-05-13

0 298

[bzoj3126][USACO2013]Photo_动态规划_单调队列

Photo bzoj-3126 题目大意：给你一个n长度的数轴和m个区间，每个区间里有且仅有一个点，问最多能有多少个点。注释：$1\le n \le 2\cdot 10^5$，$1\le m\le10^5$。想法：开始和GXZlegend在那里贪心。贪了挺久发现几乎所有的贪心策略都会被卡，...

2018-05-11

0 245

[bzoj2654]tree_二分_kruskal

tree bzoj-2654 　　　　题目大意：给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。　　　　注释：$1\le V\le 5\cdot 10^4$，$1\le E \le 10^5$，$1\le val_i\le 100$。...

2018-05-11

0 314