6 16bit戦争

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 1w+

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

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

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

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

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

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

2015-04-09 13:35:36

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

POJ 1981 Circle and Points 计算几何

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

2015-04-08 15:30:32

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

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

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

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

2015-04-07 15:27:12

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

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

2015-04-07 09:42:12

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

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

BZOJ 3922 Karin的弹幕 线段树

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

2015-03-31 19:31:33

BZOJ 3897 Power 分治

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

2015-03-28 14:45:19

BZOJ 3910 火车 LCA+并查集

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

2015-03-28 10:00:25

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

BZOJ 2654 tree 二分+最小生成树

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

2015-03-27 17:24:13

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

BZOJ 3707 圈地

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

2015-03-26 11:07:49

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!