JZYshuraK

未归档

/ 注册

全部文章 / 未归档（共392篇）

[bzoj2086][Poi2010]Blocks_单调栈_双指针

Blocks bzoj-2086 Poi-2010 题目大意：题目链接。注释：略。想法：首先，不难发现，如果连续的一段数的平均值不小于输入的k的话，这段数是满足题意的。所以，我们再次简化一下：将每个数都减去k，即求极大区间，使得区间和为正。将所有数的前缀和自尾至头压进单调栈，然...

2018-08-05

0 326

[bzoj1131][POI2008]Sta_树形dp

Sta bzoj-1131 POI-2008 题目大意：给定一棵n个点的树，求一个根，使得深度和最大。注释：$1\le n \le 10^6$。想法：扭一扭即可。扭的时候看看这个点当没当过根。最后，附上丑陋的代码... ... #include <iostream...

2018-07-31

0 245

[bzoj2060][Usaco2010 Nov]Visiting Cows 拜访奶牛_树形dp

Visiting Cows 拜访奶牛 bzoj-2060 Usaco-2010 Nov 题目大意：题目链接。注释：略。想法：看起来像支配集。只是看起来像而已。状态：dp[pos][flag]表示以pos为根的子树中，i选（不选）的最大收益。转移：dp[pos][0]+=ma...

2018-07-31

0 325

[bzoj3295][Cqoi2011]动态逆序对_主席树

动态逆序对 bzoj-3295 Cqoi-2011 题目大意：题目链接。注释：略。想法：直接建立主席树。由于是一个一个删除，所以我们先拿建立好的root[n]的权值线段树先把总逆序对求出来，接着没删一个数，我们就删掉这个点作为右端点的逆序对和作为左端点的逆序对。这个过程我们直接...

2018-07-31

0 358

[bzoj2989]数列_KD-Tree_旋转坐标系

数列 bzoj-2989 题目大意：题目链接。注释：略。想法：显然，我们用x和a[x]两个值建立笛卡尔坐标系。两个点之间的距离为曼哈顿距离。修改操作就是插入... 查询操作就是查询一个点周围的斜正方形的点数。而斜正方形的复杂度是没有办法保证的。所以，我们旋转坐标系。 ...

2018-07-31

0 409

[bzoj4025]二分图_LCT

二分图 bzoj-4025 题目大意：给定一个n个节点的图，m条边，每条边有一个产生时间和一个删除时间，询问所有时间点是否是连通图。注释：$1\le n\le 10^5$，$1\le m\le 2\cdot 10^5$ 想法：好难... 又是一道结论题。开始不知道结论，在那里LCT不知...

2018-07-31

0 377

[bzoj1704][Usaco2007 Mar]Face The Right Way 自动转身机_贪心

Face The Right Way 自动转身机 bzoj-1704 Usaco-2007 Mar 题目大意：不想描述题意系列++... ...题目链接注释：略。想法：我们直接枚举k，然后从左往右扫。碰见的第一个亮的就把它后面的都变了即可。最后，附上丑陋的代码... .. ...

2018-07-31

0 295

[bzoj2802][Poi2012]Warehouse Store_贪心_堆

Warehouse Store bzoj-2802 Poi-2012 题目大意：一家商店的连续n天内，每一天会进货$a_i$个，有且只有一个客人回来买$b_i$个，问至多满足多少人。注释：$1\le n \le 2.5\cdot 10^5$。想法：又往dp上想了..... 然后一顿推...

2018-07-31

0 448

[bzoj1634][Usaco2007 Jan]Protecting the Flowers 护花_贪心

Protecting the Flowers 护花 bzoj-1634 Usaco-2007 Jan 题目大意：n头牛，每头牛有两个参数t和atk。表示弄走这头牛需要2*t秒，这头牛每秒会啃食atk朵花。求一个弄走牛的顺序，使得这些牛破坏最少的花。注释：$1\le n \le 10^5$。 ...

2018-07-31

0 298

[bzoj3669][Noi2014]魔法森林_LCT_并查集

魔法森林 bzoj-3669 Noi-2014 题目大意：说不明白题意系列++……题目链接注释：略。想法：如果只有1个参量的话spfa、dij什么的都上来了。两个参量的话我们考虑，想将所有的边按照a排序。如果两个点：它们之间有两条路径，有一条比另一条劣。那么我们完全可以将另...

2018-07-31

0 318