Jessius-CSDN博客

原创 BZOJ 1034, 泡泡堂

排序后套用田忌赛马的贪心思想。 1. 当己方实力值最小的选手实力值大于对方最小时，直接比赛即可； 2. 当己方实力值最大的选手实力值大于对方最大时，直接比赛即可； 3. 用己方实力值最小的选手迎战对方实力值最大的选手（注意判断战平的情况）。

2017-03-10 21:00:20 298

原创 BZOJ 2330, 糖果

求最少需多少糖果若干约束条件。Analysis说起来这还是我的第一道差分约束题，汗颜。条件一等价于A-B≥0 , B-A≥0；条件二等价于B-A≥1；条件三等价于A-B≥0；条件四等价于A-B≥1；条件五等价于B-A≥0。具体怎么连边可以手画三角形脑补一下。同时要注意条件二和条件四如果给出了同一个人，则必定无法满足要求。

2017-03-06 20:16:30 213

原创 BZOJ 2456, Mode

给定一个数列，试求其众数。Analysis内存限制的脑洞题。感觉自己已经未老先衰了…… 主要是运用相消的思想，具体看代码吧……描述无能。

2017-03-04 09:13:57 226

原创 BZOJ 1066, 蜥蜴

参见题目描述。Analysis网络流的难点就在于构图…… 将一根石柱拆成上端和下端两个点并连边，容量为石柱高。从源点像一根有蜥蜴的石柱上端连边，容量为1。再从每一根能跳出地图的石柱下端向汇点连边，容量为INF。蒟蒻真的做题无力啊……

2017-03-04 09:06:50 184

原创 BZOJ 1024, 生日快乐

根据特定切割方法将一块蛋糕分成面积相等的若干块小蛋糕，求可行切割方案中小蛋糕长边比短边的最大值的最小值。Analysis数据范围很小，甚至不必二分直接搜索即可通过。注意到对于某一块蛋糕，可行的切割方案数是有限的（具体见代码实现），所以状态数也挺少的……

2017-02-15 20:10:31 233

原创 BZOJ 1854, 游戏

给定N个武器，每个武器拥有两个属性值（属性值在[1,10000]之间，要求选出部分武器，使得每个武器的一个属性值组成的数列为自1的连续单增序列，且长度最长。二分图匹配。每个武器向它的两个属性连边，然后从1到10000跑匈牙利算法（匹配就相当于每个武器只挑选出一个属性值）。一旦无法增广，即输出答案。匈牙利算法可以用时间戳优化。

2017-02-15 11:16:34 193

原创 BZOJ 1878, HH的项链

给定一个数列，询问某区间内不同数字的个数。Analysis在线算法不会。离线莫队代码能力又不够…… 用树状数组水了过去…… 首先对选用以左端点为关键字排序，然后用树状数组维护。先将每种数字第一个出现的位置加一，询问来到该点后将其后继加一，答案用树状数组累加前缀和相减即可。详见代码。

2017-02-11 17:33:56 211

原创 BZOJ 1004, 洗牌

等价类计数问题。根据Burnside引理，只需统计每种置换不动点的个数后除以置换数即可。其中，求不动点个数是类似于背包问题的动规，而除法在模意义下需要用扩欧求得逆元。

2017-02-11 12:42:08 224

原创 BZOJ 1029, 建筑抢修

贪心无力啊…… 首先将建筑按T2从小到大排序，然后用优先队列维护。如果当前耗时小于目前带修理的建筑的T2，便将答案加一，入队，当前耗时累加上该建筑的T1；若大于其T2，就比较优先队列的队首元素的T1与该建筑的T1，若队中元素较大即出队，并将待修理建筑入队，更新当前耗时。

2017-02-11 09:28:36 255

原创 BZOJ 1088, 扫雷

一张大小为N×2的雷图，第一列放有地雷，第二列没有。给出第二列各方格内的数字（意义如扫雷游戏），试统计第一列地雷有多少种合法的分布情况。动态规划。只要列出不同雷数之间转移的路径即可根据前后两个的数字进行转移。注意两端点情况的处理。发现动态规划其实已经把这题想复杂了……只要确定第一列前两个的地雷分布，整列的情况就确定了，再判断合不合法即可。

2017-02-10 14:19:43 168

原创 BZOJ 1087, 互不侵犯

给定一张大小为N×N的棋盘，要求放置K个棋子，其中，棋子上下左右以及左上、左下、右上和右下八个位置不得有其它棋子存在。求合法方案数。动态规划。状态数很多，可以先预处理出一行的合法放置方案，再处理出上一行放置的情况下，下一行哪些方案是可行的，于是一行一行转移即可。运用位运算优化预处理，后来四重循环也能跑得飞快~~~

2017-02-10 13:06:30 241

原创 BZOJ 1059, 矩阵游戏

给定一个大小为N×N的黑白染色矩阵，试判断能否通过交换行与列使矩阵左上角至右下角这一对角线上所有点均为黑色。Analysis易知若几个黑点原本同行或同列，不管如何变换，它们始终同行或同列。因此我们只需判断是否存在N个点互不同行，也互不同列。由此转化为二分图模型。对于一个坐标为(i,j)的黑点，由第i行向第j列连边。若此二分图存在完美匹配，则可满足题目要求。

2017-02-10 08:32:21 191

原创 BZOJ 1798, 维护序列

维护一个数列，要求支持区间加、区间乘以及查询操作。很裸的线段树，难点在于加法和乘法的操作顺序。标记下传时应先打乘法标记，再打加法标记，同时更新时还要用乘法标记维护加法标记。

2017-02-09 10:53:44 286

原创 BZOJ 1014, 火星人

给定一仅有小写字母组成的字符串，要求支持单字符修改、插入和查询不同起始位置的最长公共前缀长度。用Splay维护字符串，二分+Hash查询。反反复复WA了很多次，就因为Hash的操作顺序不太对……也算是买了个教训。

2017-02-08 21:17:20 423

原创 BZOJ 1016, 最小生成树计数

给定一张简单无向加权图，求其最小生成树方案数。貌似有一个Matrix Tree定理……但是感觉目前不是很学得进东西，所以还是打了dfs。先跑一遍Kruskal，统计不同权值的边各出现几次。然后dfs判断某一种权值的边的方案数，累乘即可。需要注意的是并查集不可以路径压缩，那样会导致连通块合并后无法分开。

2017-02-08 09:40:30 369

原创 BZOJ 1070, 修车

某汽车维修中心有m位技术人员，有n辆汽车待修理。不同的技术人员修理不同车辆耗时不同。最小化平均等待时间。经典的最小费用最大流。设第j位技术人员修理第i辆汽车耗时为w[i,j] 。将技术人员拆成n个点，每个点向汽车连容量为1的边，第k个点所连边费用为k×w[i,j]，表示倒数第k个修理该车则对总等待时间贡献k×w[i,j]。

2017-02-08 07:26:10 166

原创 BZOJ 3110, K大数查询

要求维护一个数列，支持在某部分的每个位置填上一个数以及查询某部分第K大的数字。终于学习了一下树套树的姿势……其实和自己想的也差不多……但是不学还是打不出代码来…… 外层是权值线段树，内层是区间线段树。要注意的细节比较多。二分查询过程中结果可能超过 Maxlongint ，需要用 unsigned int 类型传递；权值可以翻转后整体右移等等。

2017-02-07 20:05:40 182

原创 BZOJ 1497, 最大获利

选择合理方案新建基站，满足部分用户群需要，求最大获利（净获利 = 获益之和 - 投入成本之和）。注意到类似于有向无环图的性质，套用最小割模型中的最大权闭合图即可。参考资料：胡伯涛2007年集训队论文《最小割模型在信息学竞赛中的应用》

2017-02-07 10:22:14 194

原创 BZOJ 3223, 文艺平衡树

编写一个支持对数列进行翻转子串操作的数据结构。Splay裸题。只需要支持翻转操作即可。输出数列时一个一个查询就是了……

2017-02-06 20:21:00 262

原创 BZOJ 1192, 鬼谷子的钱袋

将一个数字m分为几个互不相同的数字，使得由这些数字可以组成1至m的任意数字。求最少划分为几个数字可满足要求。水题。求得满足2^k＞m的最小k值即可。

2017-02-06 16:28:29 219

原创 BZOJ 1007, 水平可见直线

将直线按斜率排序，然后从小到大依次入栈，入栈时计算该直线与栈顶元素交点。若该交点在栈顶元素与栈顶下一个元素交点的左侧（或重合），则栈顶元素被完整遮挡，出栈。反复比较，全部操作完毕后栈中元素即为可见水平直线。

2017-02-06 16:06:52 267

原创 BZOJ 1061, 志愿者招募

最小化招聘给定不同类型志愿者，以满足每日不同人数要求的费用总和。由线性规划转化为最小费用最大流来处理。一般按如下步骤进行操作： ①添加松弛变量，将不等号都变为等号。分别用下一个式子减去上一个式子，如果每个变量只出现了两次且符号一正一负，那么可以转化为费用流。 ②对于每个式子建立一个点，那么每个变量对应一条边，从一个点流出，向另一个点流入。

2017-02-06 14:04:53 364

原创 BZOJ 2243, 染色

要求编写一个数据结构，维护一颗无根树各节点的颜色以支持查询两点间的路径上颜色段的数量。树链剖分+线段树。线段树各节点保存区间左端点、右端点的颜色，区间内颜色段数量，以及线段树set操作标记。合并区间时要注意处理两段点颜色相同的情况。

2017-01-20 13:43:55 260

原创 BZOJ 3668, 起床困难综合症

在0到m间选取一个数，使其经过若干次关于某个值的OR, XOR或AND运算后所得结果最大。Analysis二进制下从高位到低位贪心即可。运算结果相同的情况下当前位取0优于取1。

2016-12-17 19:04:59 239

原创 BZOJ 1013, 球形空间产生器

求给定的n+1个点所确定的n维球面的球心。高斯消元裸题。（第一次打没有1A很失望）可以先设球心坐标，用距离公式表示出其与某点的距离。用该表达式与其他n个表达式相减即可得到关于球心坐标的n个方程。接着套用高斯消元即可。需要注意输出末尾不能有空格。

2016-11-01 20:51:52 188

原创 BZOJ 1051, 受欢迎的牛

求可以被除自己以外所有点遍历到的点的个数。首先强连通分量跑一遍，缩点之后统计每个强连通分量（可以视为一个点）的出度。如果有多个出度大于0，则无解；否则输出唯一出度为0的强连通分量内点的个数。

2016-10-30 15:59:04 184

原创 BZOJ 1015, 星球大战

编写一个支持删点并查询当前图中连通块个数的数据结构。离线倒序处理+并查集。于是删点就变成了加点，因此不必考虑正序处理时删边后两点是否仍连通的问题。先将所有未删除的点加入到图中，再倒序依次加入被删除的点，用并查集来维护图的连通块个数。

2016-10-27 21:36:00 168

原创 BZOJ 1031, 字符加密

将一个长度为n的字符串首尾相连，以不同的下标为串的头，有n种读法，将这些读法排序后取各种读法的最后一位组成新串。后缀数组裸题。将字符串倍长后用后缀数组排序即可。注意若传入下标为0~n-1的字符串（下标n处为’\0’），传入SA函数中的串长应为n+1，排序后结果亦存在于sa[0…n]中。

2016-10-27 06:47:12 258

原创 BZOJ 1082, 栅栏

二分+搜索。二分可能得到的符合条件的木板数，再搜索验证。爆搜的姿势很要紧，写一个美观一点的搜索不仅复杂度小而且方便剪枝…… 搜索时优先匹配较小的木板，显然若较小木板都无法满足则较大木板也无法满足。剪枝一：排序并删除小于最小木板的木材和大于最大木材的木板。剪枝二：搜索时记录当前已浪费的木材量，当浪费值加需求量已大于木材总量时退出。

2016-10-23 21:04:22 212

原创 BZOJ 1003, 物流运输

动态规划+最短路。状态转移方程为f[i]=min(f[j-1]+d[m]*(i-j+1)+k),1≤j≤i≤n。d[m]为每次状态转移计算所得当前可行的最短路花费。

2016-10-12 07:48:28 550

原创 BZOJ 1026, Windy数

求区间[A,B]中相邻位数字之差均大于1的元素个数。数位DP。第一次写这中类型的DP题，细节处理上还是有很多盲点，花了不少时间来调试。 solve(b+1)-solve(a)相较于solve(b)-solve(a-1)好处在于可以不必单独处理匹配至最后一位的情形。

2016-10-11 19:58:08 180

原创 BZOJ 1208, 宠物收养所

编写一个支持插入、删除元素，查询数列中最接近某值的元素的数据结构。保证没有重复元素存在出现在树中。Treap和Splay都可做。 Splay苦手选择Treap，然而写得奇丑无比。查询最接近某值的元素可以将该值插入树中查询前驱与后继，后比较。查询完以后再删掉。

2016-09-27 20:46:38 210

原创 BZOJ 2049, 洞穴勘测

要求编写一个数据结构，支持动态连边、删边和查询两点连通性。保证两点间最多只有一条路径。LCT模板题。（其实并查集更好些？）借这题大致了解了一下LCT，顺便回顾了一下Splay。 LCT里的Splay略有不同于普通的Splay，也是需要特别注意的。参考资料：Yang Zhe《SPOJ375 QTREE 解法的一些研究》

2016-09-27 06:43:45 228

原创 BZOJ 1012, 最大数

编写一个支持查询末尾L个数中最大数和在数列末尾插入的数据结构。乍一看觉得得写Splay，其实只是利用单调性就可以解决了。当然这题做法很多，线段树什么的都可搞。开两个数组，一个作为栈，一个记录栈中元素在数列中的位置。每新加一个数字，就将栈顶小于它的元素弹出后加入栈（因为若栈顶元素小于新数，那么栈顶元素一定不是最大值）。

2016-09-11 19:20:09 226

原创 BZOJ 1500, 维修数列

编写一个支持插入、删除、修改、翻转、求和以及求和最大子序列的数据结构。Splay无疑。但是写太丑也是会TLE的，比方说插入的时候应该以建树的形式插入，而不是一个点一个点的形式。实现起来要注意的细节很多，对练习打Splay挺有好处。（陆陆续续调试了好多天，总算在崩溃之前AC了……）

2016-09-11 15:51:46 190

原创 BZOJ 3224, 普通平衡树

编写一个支持插入、删除元素，查询元素排名，查询相应排名的元素，查询元素前驱与后继的数据结构。有重复元素存在，且查询前驱后继的元素可能未出现在树中。Treap和Splay都可做。 Splay随便搞一搞就可以了，然而没打过的我只会口胡…… 于是打了Treap。重复元素可以选择在保存在同一节点中，在Struct里新加一个cnt来保存当前节点元素个数。

2016-08-18 19:34:27 225

原创 BZOJ 2002, 弹飞绵羊

输入链上各弹力装置的弹力系数，要求支持修改弹力系数以及查询绵羊被弹几次后弹飞。LCT可做，而且时间复杂度优。分块虽然慢一些但是编程复杂度比较低。两个数组cnt和nxt分别记录处于当前装置时被弹几次后弹出当前块以及弹到后面的什么位置。分块对细节处理要求比较高，题目中也特别强调了装置编号为0到n-1，需要注意。

2016-08-14 11:18:26 280

原创 BZOJ 1001, 狼抓兔子

求平面图最小割。数据范围太大导致直接跑最大流会TLE。正确做法是平面图转对偶图，就可以把最小割问题转化成求最短路。注意要特判n=1与m=1的情况。参考资料：周冬2008年集训队论文《两极相通——浅析最大—最小定理在信息学竞赛中的应用》

2016-08-14 09:40:31 204

原创 BZOJ 1002, 轮状病毒

在一个n轮状基中删去若干条边，使得各点之间有且仅有一条通路。递推公式 f[i]=f[i-1]*3-f[i-2]+2 正解是基尔霍夫矩阵，然而我并不知道这是什么东西……

2016-08-13 15:33:36 264

原创 BZOJ 1213, 高精度开根

输入一个正整数m（1≤m≤50）和一个整数n（0≤n≤10^10000），求开根后取整的结果。二分+高精度+NTT 倍增地确定二分边界L，R；由于n过大，高精度乘法不够快，所以需要用NTT来加速乘法（FFT比较慢，而且精度不够）。

2016-08-13 10:41:49 1625

NOIP2013初赛提高组C++试题及答案

空空如也