16bit戦争-CSDN博客

原创 POJ 2069 Super Star 爬山

题目大意空间最小球覆盖思路临滚粗前做点水题qwqCODE#define _CRT_SECURE_NO_WARNINGS#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define INF 1e15#define EPS 1e-7#define MAX 1

2015-04-15 07:23:39 1327

原创 BZOJ 3943 Usaco2015 Feb SuperBull Prim

题目大意异或Prim。思路没开long long WA了一次你敢信？CODE#define _CRT_SECURE_NO_WARNINGS#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define MAX 2010#define INF 0x3f3f3f3fusing namespac

2015-04-09 16:19:17 1056

原创 BZOJ 1532 POI 2005 Kos-Dicing 最大流+二分

题目大意给出一些比赛，每场比赛有一个人会胜出，问胜出最多次的人最少胜出多少次。思路首先二分答案，转化成判定问题。观察题目，注意到每场比赛只有一个人胜出，那么这可以成为网络流建图流量限制的依据。具体： S->每个人 f：二分的最大胜出次数。每个人->他参与的比赛 f：1 每场比赛->T f：1 每次判断最大流和比赛是否相等。CODE#define _CRT_SECURE_NO_WARNI

2015-04-09 15:48:54 1211

原创 BZOJ 3524 POI 2014 Couriers 主席树

题目大意给出一个序列，问一段区间内有没有出现过一半以上的数字。思路用主席树取区间出来，在权值线段树上找。CODE#define _CRT_SECURE_NO_WARNINGS#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define MAX 500010#define MAXR 1000

2015-04-09 14:49:16 1025

原创 BZOJ 3932 CQOI 2015 任务查询系统可持久化线段树

题目大意给出一些任务开始的时间，结束的时间，和优先级。问在第k秒时的第k大优先级，和前k小优先级的和。思路CQOI太良心，所有题都是512M。这个题只需要按照时间轴弄一个可持久化线段树就行了，每个时间点对应着一个权值线段树，维护子节点的和和个数。注意在没有操作的时候，当前时间点的线段树要复制上一个时间点的线段树。CODE#define _CRT_SECURE_NO_WARNINGS#incl

2015-04-09 13:35:36 1871

原创 BZOJ 1602 Usaco2008 Oct 牧场行走倍增LCA

题目大意给出一个树，多次询问两点之间的距离。思路这个题存在的意义是什么？CODE#define _CRT_SECURE_NO_WARNINGS#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define MAX 1010using namespace std;int head[MAX],

2015-04-08 17:56:30 739

原创 POJ 1981 Circle and Points 计算几何

题目大意给出平面上的一些点，求一个单位圆最多能够覆盖多少点。思路数据范围300，但是没有用，多组数据就是要卡O(n3)O(n^3)，然而常数优化的比较好的话在POJ能过，但是BZ上还是过不了。我们需要寻找一种O(n2logn)O(n^2logn)的做法。做法就是枚举每个点，做一个一这个点为圆心的单位圆。之后将所有在这个圆里的点弄出来，以这些点为圆心做单位圆，与开始的单位圆会产生一段圆弧，最后求哪

2015-04-08 15:30:32 1195

原创 BZOJ 3522 POI 2014 Hotel 树形DP

题目大意给出一棵树，问选择三个点，使得这三个点相互的距离相等的方案有多少种。思路这三个点肯定不能再一条链上，那么就肯定能够确定一个中心点，使得三个点到这个中心点的距离都相等。之后我们就可以枚举这个中心点，对于每个深度统计一下就可以了。虽然看起来像是O(n3)O(n^3)的，但是跑的飞起啊。CODE#define _CRT_SECURE_NO_WARNINGS#include <cstdio>

2015-04-08 10:43:27 1122

原创 BZOJ 3931 CQOI 2015 网络吞吐量最短路+最大流

题目大意给出一个无向图，求出在这个图上1到n的所有最短路形成的图的最大流。思路想让大家叠模板也不带这么懒得吧。。记得开long long就行了。CODE#define _CRT_SECURE_NO_WARNINGS#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorith

2015-04-07 15:35:59 907

原创 BZOJ 1976 BeiJing2010组队能量魔方 Cube 最小割

题目大意给出一个N×N×NN \times N \times N的矩阵，矩阵上的每一个方块可以涂上两种颜色，相邻的两个方块如果涂上了不同的颜色，就会产生一点能量。现在已知了一些方块的颜色，问最多可以产生多少点能量。思路假设所有相邻的方块之间全部都产生能量，且不考虑已经上好色的方块，之后减去不合法的就行了。一般来说这种相邻的方块之间会产生一些什么的一般都是把所有点染色，一种颜色的与S相连，另一种

2015-04-07 15:27:12 1143

原创 BZOJ 2251 2010Beijing WC 外星联络后缀数组/Trie树

题目大意给出一个字符串，问这个字符串中出现过1次以上的子串的个数，按照子串的字典序输出。思路由于数据范围过小，这个题有两个解法。基本的想法就是用后缀数组来进行后缀的排序，之后按照height数组扫就可以了。应该是挺快的。但是注意到数据范围只有3000，因此我们只需要弄出所有的后缀拿出来建立一颗后缀Trie树就行了。最后DFS一次树种的所有节点。CODESuffixArraySuffixArr

2015-04-07 09:42:12 1528

原创 POJ 3974 Palindrome Manacher

题目大意给出一个字符串，求出这个字符串的最长回文子串。思路前来学习著名的Manacher算法。这是一个线性时间求出回文子串的算法。具体来说，对于我们弄出的一个回文串，它对于后面的串并不是，没有用的，因为它的左右两侧是相同的，那么自然可以用左边的信息去更新右边。设p[i]p[i]为第ii个字符的回文半径，_max\_max为max{p[i]+i}max\{p[i] + i\}，也就是最远可以更

2015-04-07 08:30:42 829

原创 BZOJ 3916 Baltic 2014 friends Hash

题目大意给出一个字符串，这个字符串是由两个相同的字符串连接之后再加一个字母的到的，求原串。思路枚举加的字母是哪一个，之后分情况讨论，根据hash值来判定是否符合题目要求。注意判重。CODE#define _CRT_SECURE_NO_WARNINGS#include <cstdio>#include <cstring>#include <iostream>#include <algorithm

2015-04-01 20:04:48 1115

原创 BZOJ 3922 Karin的弹幕线段树

题目大意给出一个序列，支持单点修改，每次查询一个位置成等差数列中所有数的最大值。思路等差数列如果公差很大的话，那么整个数列中的数并不会很多；但是如果公差很小，我们就可以用线段树来乱搞。具体方法是对于每个公差维护一个线段树，按照对这个公差取模的值来进行划分。这样询问的时候就在一块了。具体看代码。CODE#define _CRT_SECURE_NO_WARNINGS#include <cstdio>

2015-03-31 19:31:33 1069

原创 BZOJ 3897 Power 分治

题目大意一个人打工，每一天有一个收益，使用一点体力可以获得一份收益，每天回复固定的体力，体力有一个上限，超出之后就不回复了。问最多可以获得多少收益。思路分治策略：Solve(l, r, st, ed)表示第l天到第r天，初始体力为st，结束体力为ed的最大收益。显然，我们想让这个区间中的收益最大的那天干的越多越好，于是分情况讨论：如果从一开始就休息，一直休息到收益最大的那天，没有达到体力的上限，

2015-03-28 14:45:19 1318

原创 BZOJ 3910 火车 LCA+并查集

题目大意给出一棵树，起点，和要经过的点的序列，已经经过的点就不用去了，剩下的点按照顺序依次去，问要经过多少条边。思路链剖大概应该是可以，不过没试，用了听大爷说的一种神奇的方法。因为树上经过的点肯定是一段一段的，就想到用并查集将一段合成一个点，每个点最多只能被合一次，这样的话就能保证时间复杂度。查询的时候像链剖一样一段一段往上跳就行了，还要顺便把路径上的所有点缩起来。CODE#define _CR

2015-03-28 10:00:25 1314

原创 BZOJ 2440 中山市选 2011 完全平方数莫比乌斯函数+二分

题目大意给出一个数k，求第k个不是完全平方数个数的数字（这里的完全平方数并不包括1）。思路首先介绍一下莫比乌斯函数(Möbius): μ(x)=⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ 1(−1) k 0 x=1能分解成k个不同的质因数的乘积其他情况 \mu(x)=\left\{\begin{aligned}&1&x = 1 \\&(-1)^k&能分解成k个不同的质因数的乘积\\&0&其他情况\

2015-03-27 20:42:57 982 1

原创 BZOJ 2654 tree 二分+最小生成树

题目大意给出一些边，每个边有一个边权和颜色。现在要求出最小边权有need个白边的生成树。输出这个边权。思路在白边上加一个权值，这样就可以人为的改变白边出现在最小生成树。这个东西显然可以二分。之后取一下最小值就可以了。CODE#define _CRT_SECURE_NO_WARNINGS#include <cstdio>#include <cstring>#include <iostream>#

2015-03-27 17:24:13 1118

原创 BZOJ 3550 ONTAK2010 Vacation 线性规划转费用流

题目大意给出一个长度为3×N 3 \times N的序列，规定N N个数字中不能选择超过k k 个，问最多能取出的数的权值和是多少。思路非常神的建图，本来想朴素费用流不过去学zkw费用流，结果朴素费用流跑的飞起。利用一些辅助变量我们可以列出一些式子：设k k是N N个数种最多能够取出的数的数量，a[i] a[i]表示第i i天选不选，y y数组一定是自然数。 ∑ N i=1 a[i]+

2015-03-26 19:55:16 1264

原创 BZOJ 3707 圈地

题目大意给出平面上n个点，求最小面积三角形。思路暴力能过。。。于是我只写了暴力。。。后来看hzwer学长的博客发现了一个有趣的骗分。将整个序列分块，块内暴力，这样就避免了太远的点之间的计算。然后旋转几次坐标轴争取枚举到所有的情况。。CODE(暴力)：#define _CRT_SECURE_NO_WARNINGS#include <cmath>#include <cstdio>#i

2015-03-26 11:07:49 948

原创 BZOJ 2668 CQOI 2012 交换棋子费用流

题目大意给出一个网格图，每个格子上有移动次数限制。每次可以交换相邻的两个棋子（有公共点就算相邻）。给出一个初始状态，问最少需要多少步达到目标状态。思路这个题主要是限制是每个格子，而不是棋子。我们对每个格子拆点，相邻的格子之间连边，经过一个格子的时候的费用是2，流量是（正常的流量+这个点是入点+这个点是出点）/2，在连S和T的时候要将费用设成-1。这样跑出来的最小费用的一半就是答案。注意要特判一下

2015-03-25 20:25:10 727

原创 BZOJ 1028 JSOI 2007 麻将贪心

题目大意给出一种简化的麻将游戏规则，给出一副牌，问是否听牌，如果听，听那些张。思路一开始图样，写搜索，果断T了。其实就是一个显然的贪心。枚举听哪张牌，加进来，然后枚举最后剩下的雀头，对剩下的牌尽量组成m个顺子或者对子就行了。这时候我们从左往右扫，能够组成对子的就形成对子，不能的就和后面组成顺子。遇到小于0的就退出就好了。CODE#define _CRT_SECURE_NO_WARNINGS#in

2015-03-24 17:04:49 928

原创 BZOJ 1027 JSOI 2007 合金计算几何+最小环

题目大意给出一个CPU处理事件的规则，给出一些事件，问处理这些事件的顺序和结束时间。思路我们只需要维护一个堆来模拟他说的规则，之后按顺序输出就行了。CODE#define _CRT_SECURE_NO_WARNINGS#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorith

2015-03-23 20:08:48 1169

原创 BZOJ 1216 HNOI 2003 操作系统堆

题目大意给出一个CPU处理事件的规则，给出一些事件，问处理这些事件的顺序和结束时间。思路我们只需要维护一个堆来模拟他说的规则，之后按顺序输出就行了。CODE#define _CRT_SECURE_NO_WARNINGS#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorith

2015-03-19 18:42:40 664

原创 BZOJ 2741【FOTILE模拟赛】L 分块+可持久化Trie树

题目大意给出一个序列，求[l, r]中的最大连续xor xor和。强制在线思路先把整个序列分成n √ \sqrt{n}块，预处理每一块的开头到每个数字的最大连续xor xor和。这个我们只需处理出前缀xor xor和，之后用可持久化Trie树就可以搞定。这样询问的右边就是整块的了。剩下左边的随便暴力一下就能过了。。CODE#define _CRT_SECURE_NO_WARNINGS#inc

2015-03-17 20:30:16 1286

原创 BZOJ 1570 JSOI 2008 Blue Mary的旅行网络流

题目大意给出一个有向图，每天每人只能做一次飞机。现在给出起点，终点，和需要走的人数，还有每条航线的限制人数，问最少多少天最慢的人到达终点。思路很明显是网络流的模型，至于如何去验证，其实连二分都不用，枚举最少天数，然后每次加一层边进行验证就行了。CODE#define _CRT_SECURE_NO_WARNINGS#include <queue>#include <cstdio>#include

2015-03-07 07:57:42 1066

原创 BZOJ 3678 wangxz与OJ 缩点Splay

题目大意维护一个序列，支持 1. 插入一段序列，这个序列以1递增 2. 删除连续的一段序列 3. 查询位置p的数是多少。思路简单Splay维护就可以。但是后来好像被卡了，还有rope什么乱搞的都被卡了。于是观察这个插入的序列，他是一个很有规律的数列，但是插入之后我们却不一定查找这个序列中的数字，我们可以将这个数列当成一个节点插入Splay中去，这样每个节点可以记录ll和rr来表示这个点所代表的

2015-03-06 14:17:20 1101

原创 BZOJ 3888 Usaco 2015 Jan Stampede 模拟

题目大意给出一些奶牛，一个人在原点观察，牛和牛之间又互相遮挡的关系，给出每头牛的运行方式和位置，问这个人最终会看到多少头牛。思路知道了运行方式，我们就知道这头牛在什么时间段会遮挡住人的视线，然后从高到低弄个东西维护一下覆盖什么的，这个题就变成了POJ的Mayor’s posters。注意下时间点和时间段的区别就行了。CODE#define _CRT_SECURE_NO_WARNINGS#incl

2015-03-06 08:59:56 970

原创 BZOJ 3613 HEOI 2014 南园满地堆轻絮二分+贪心

题目大意给出一个数字序列，要求将这个数字序列变成单调不降的序列。若原来的数字是A[i],变化之后的数字是B[i],那么花费是|A[i]−B[i]||A[i] - B[i]| 。求出一种方案，使得最大的花费最小。思路一眼就能看出是二分，然后贪心什么的随便yy一下就行了。CODE#define _CRT_SECURE_NO_WARNINGS#include <cstdio>#include <cstr

2015-03-05 20:00:31 948

原创 POJ 2079 Triangle 旋转卡壳

题目大意给出平面上的一些点，求这些点能够组成的最大面积三角形。思路虽然数据范围有50W，但是POJ上的数据一向很弱，discuss中居然有人这样说：手动二分发现极限数据凸包上有2596个点 RT 好水的数据好吧，留给我们的就剩下O(n2)O(n^2)的时间内解决这个题了。首先先求出凸包，之后可以枚举这个大三角形的一条边，然后枚举另一个顶点。很显然这个过程是O(n3)O(n^3

2015-03-05 14:29:27 749

原创 BZOJ 2333 SCOI 2011 棘手的操作可并堆

做此题的原因题号美题目大意给出一个序列，支持一堆操作（具体看下面）。让你维护它。思路U x y：我们需要可并堆来将两个堆合并。 A1 x v：将这个点从堆中拽出来，改了之后再合并回去。 A2 x v：在堆顶打标记。 A3：记录一个全局变量记录。 F1 x：将这个点到堆顶的链上的所有标记下传，之后返回自己的大小。 F2 x：返回堆顶。 F3：用一个堆（set也行）维护所有堆顶的元素。需

2015-03-05 13:34:27 773

原创 BZOJ 1455 罗马游戏可并堆

题目大意给出n个人的权值，每次要求将两队人合成一堆，或者杀掉一堆人中的权值最小的那个人。问每次删除的人的权值是多少。思路就是可并堆，没了。我挑最简单的随机堆写的。CODE#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define MAX 1000010using namespace st

2015-03-05 07:43:25 800

原创 BZOJ 2815 ZJOI 2012 灾难动态倍增LCA

题目背景阿米巴是小强的好朋友。题目大意给出一个食物链（拓扑图），定义一个生物所有的食物都灭绝了之后他自己也灭绝了。定义每种生物灭绝之后跟随着它灭绝的生物个数为这个生物的灾难值。求所有生物的灾难值。思路看题帽知出题人系列。 fhq的题大家也知道，一般都是不可做的。于是我就去看了他的题解，发现这个题还是可做的。定义一种灭绝树，对于任意一个子树，若这个子树的根节点灭绝，那么子树中的所有点都

2015-03-04 16:22:23 1249

原创 BZOJ 1898 ZJOI 2004 Swamp 沼泽鳄鱼矩阵乘法

题目大意给出一张无向图，这个图中有一些鱼，他们不同的时间会出现在固定的位置，呈周期性循环，一个人要在这个图上走，他不能和鱼同时在一个点上。问从s到t走k步有多少种方案。思路注意到鱼的循环只可能是2/3/4，也就是说最多经过12个时间点之后，状态又会和一开始相同。所以预处理12个矩阵用来转移。分为k/12和k%12来处理。当鱼在一个位置上的时候，当前时间从这个位置出发的一行和上一个时间到达这个点的

2015-03-04 14:13:45 1195

原创 BZOJ 3527 ZJOI 2014 力 FFT

题目大意定义求E[i] = F[i] / q[i]思路经过推导发现最后形成了卷积的形式，之后直接套用FFT就行了。注意卷积卷起来之后占用的是2倍的空间。。CODE#define _CRT_SECURE_NO_WARNINGS#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include

2015-03-04 08:18:18 1262

原创 BZOJ 2326 HNOI 2011 数学作业矩阵乘法

题目大意求一个这样的数：“12345678910111213……”对m取模的值。思路观察这个数字的特点，每次向后面添加一个数。也就是原来的数乘10^k之后在加上一个数。而且处理每个数量级的时候是相似的。所以就可以用矩阵乘法来加速。我构造的矩阵是这样的。 [当前数字累加数字1]×⎡⎣⎢数量级10011001⎤⎦⎥=[新的数字累加数字+11] \begin{bmatrix} 当前数字 & 累加数字

2015-03-03 09:36:03 797

原创 BZOJ 3890 Usaco2015 Jan Meeting Time 拓扑图DP

题目大意题上的中文题意太不明确了。。。给出一个拓扑图，每条有向边有两个权值，有两个人从1出发到n，分别走这两种权值。问有没有权值使得这两个人都能走过这些权值到达n。思路看懂了题之后就水了。维护两个数组表示从1号节点是否能够通过i的权值到达j。然后做拓扑图DP。CODE#define _CRT_SECURE_NO_WARNINGS#include <queue>#include <cstdio>

2015-03-02 16:14:16 1116

原创 BZOJ 1199 HNOI 2005 汤姆的游戏计算几何

题目大意给出若干个图形，这些图形中有些是矩形，剩下的是圆形。还有一些点，问每个点在多少个图形里面。思路题目没写数据范围，其实是25w。敢O(n^2)暴力么？没错这个题就是暴力。只需用二分处理一维坐标然后第二维暴力就行了。CODE#define _CRT_SECURE_NO_WARNINGS#include <cmath>#include <cstdio>#include <cstring>#i

2015-03-02 14:12:08 947

原创 BZOJ 3246 IOI 2013 Dreaming 树形DP

题目大意给出一个缺若干条边的树，现在让你填一些长度为定值的边，使得整个树的直径最小。思路给一个详细的网址，讲的非常明白。 http://www.ccf.org.cn/resources/1190201776262/fujian/xuhaoran2013-07-25-03_33_55.pdf还有数据范围是50w。CODE#define _CRT_SECURE_NO_WARNINGS#includ

2015-03-02 12:52:17 1153

原创 BZOJ 3531 SDOI 2014 旅行

题目大意给出一个树，树上每个节点有两个权值，分别是这个节点的宗教评级和这个节点信仰的宗教。多次修改这两个权值，每次询问树上路径上的点的同一个宗教的最大评级和评级和。思路不要想太多，每个宗教建立一颗线段树，空间开不下考虑一下动态节点线段树。之后在每个线段树上维护一下树链剖分就行了。你们想知道c的取值范围么？ [0,10^5]CODE#define _CRT_SECURE_

2015-03-02 09:42:26 857

空空如也

空空如也