accepoc-CSDN博客

原创 Codeforces Round #368 (Div. 2)

A. Brain’s Photos给你一张照片每个像素的颜色，问这是黑白照片还是彩色。。 ‘C’ (cyan) ‘M’ (magenta) ‘Y’ (yellow) ‘W’ (white) ‘G’ (grey) ‘B’ (black) 注意G是灰色！！#include <cstdio>#include <cstring>#include <algorithm>#include

2016-09-22 22:16:28 479

原创 1818: [Cqoi2010]内部白点

题目链接Description无限大正方形网格里有n个黑色的顶点，所有其他顶点都是白色的（网格的顶点即坐标为整数的点，又称整点）。每秒钟，所有内部白点同时变黑，直到不存在内部白点为止。你的任务是统计最后网格中的黑点个数。内部白点的定义：一个白色的整点P(x,y)是内部白点当且仅当P在水平线的左边和右边各至少有一个黑点（即存在x1 < x < x2使得(x1,y)和(x2,y)都是黑点），且在竖直线

2016-09-21 22:47:21 412

原创 Educational Codeforces Round 15

题目链接在这里A. Maximum Increase最长上升子串#include <bits/stdc++.h>using namespace std;int n;int arr[100005];int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> arr[i]; int ans = 0;

2016-09-12 21:56:23 364

原创 bzoj 1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

Description了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的： 1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi - xil+IYi -

2016-09-10 20:13:16 412

原创 Codeforces Round #367 (Div. 2)

A. Beru-taxi给定n个出租车的位置和速度，问哪个最快到你家。。扫一遍即可。#include <bits/stdc++.h>using namespace std;int n;double a, b, c;double x, y;double dist(int a, int b, int c, int d) { return sqrt((a - c) * (a - c) + (b

2016-09-10 11:44:26 312

原创 BestCoder Round #45

继续宣传：新博客：http://shijieyywd.com/?p=120呃。。虽然发挥不咋样但是状态似乎回转了一点。。1001.Dylans loves numbers问一个整数n的二进制中有多少组1。如果两个1之间有若干个（至少一个）0挡住，他们就不是一组的，否则他们就是一组的。嗯。。直接模拟吧。#include <cstdio>#include <cstring>#include <alg

2015-06-21 05:09:15 822

原创 Codeforces Round #307 (Div. 2)

我知道你们会来的：新博客：http://shijieyywd.com/?p=108唉最近状态越来越差。。。A. GukiZ and Contest给你n个人的分数然后输出排名。一遍排序搞定。#include <bits/stdc++.h>using namespace std;struct Node{ int val, pos; bool operator < (const No

2015-06-20 18:58:09 568

原创 Codeforces Round #308 (Div. 2)

再次厚颜无耻地宣传一发：新博客http://shijieyywd.com/?p=99这次cf真是发挥的有点醉，下次有div1我都不敢做了。A. Vanya and Table给你n个矩形，问你面积之和。是面积之和不是面积并，直接算。然而我这个傻逼交错文件了WA了一发233333。#include <bits/stdc++.h>using namespace std;int n;int main()

2015-06-19 04:46:37 1368 3

原创 bzoj1367 [Baltic2004]sequence [左偏树]

Description给定一个序列t1,t2,...,tnt_1, t_2, ..., t_n，求一个递增序列z1<z2<...<znz_1<z_2<...<z_n，使得R=|t1−z1|+|t2−z2|+...+|tn−zn|R = |t_1 - z_1| + |t_2 - z_2| + ... + |t_n - z_n|的值最小。本题中，我们只需要求出这个最小的R值。Input第1行为一个整数

2015-06-17 12:31:02 2542

原创 hdu2825 Wireless Password [AC自动机+状压dp]

Problem DescriptionLiyuan lives in a old apartment. One day, he suddenly found that there was a wireless network in the building. Liyuan did not know the password of the network, but he got some import

2015-06-04 11:14:50 639

原创 bzoj 2437 [Noi2011]兔兔与蛋蛋 [二分图匹配]

描述这些天，兔兔和蛋蛋喜欢上了一种新的棋类游戏。这个游戏是在一个 n 行 m 列的棋盘上进行的。游戏开始之前，棋盘上有一个格子是空的，其它的格子中都放置了一枚棋子，棋子或者是黑色，或者是白色。每一局游戏总是兔兔先操作，之后双方轮流操作，具体操作为：兔兔每次操作时，选择一枚与空格相邻的白色棋子，将它移进空格。蛋蛋每次操作时，选择一枚与空格相邻的黑色棋子，将它移进空格。第一个不能按照规则操作

2015-06-03 11:31:58 1688

原创 bzoj 2434 [Noi2011]阿狸的打字机 [AC自动机+树状数组]

Description 阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现，这个打字机是这样工作的：| 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。| 按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。| 按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有

2015-06-02 17:10:25 443

原创 bzoj 2432 [Noi2011]兔农 [矩阵]

Description 农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第n个月有多少只兔子？聪明的你可能已经发现，第n个月的兔子数正好是第n个Fibonacci(斐波那契)数。栋栋不懂什么是F

2015-06-02 16:15:01 1839

原创 bzoj 2433 [Noi2011]智能车比赛 [计算几何+spfa]

Description 新一届智能车大赛在JL大学开始啦！比赛赛道可以看作是由n个矩形区域拼接而成（如下图所示），每个矩形的边都平行于坐标轴，第i个矩形区域的左下角和右上角坐标分别为(xi,1,yi,1)和(xi,2,yi,2)。题目保证：xi,1<xi,2=xi+1,1，且yi,1< yi,2，相邻两个矩形一定有重叠在一起的边（如图中虚线所示），智能车可以通过这部分穿梭于矩形区域之间。选手们需要

2015-06-02 15:51:26 1001

原创 bzoj2878 [Noi2012]迷失游乐园 [树形dp]

Description放假了，小Z觉得呆在家里特别无聊，于是决定一个人去游乐园玩。进入游乐园后，小Z看了看游乐园的地图，发现可以将游乐园抽象成有n个景点、m条道路的无向连通图，且该图中至多有一个环（即m只可能等于n或者n-1）。小Z现在所在的大门也正好是一个景点。小Z不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，并且同一个景点不去两次（包括起始景点）。贪玩的小

2015-06-02 14:36:26 2320

原创 bzoj2879 [Noi2012]美食节 [费用流动态加边]

DescriptionCZ市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。作为一个喜欢尝鲜的美食客，小M自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小M仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小M开始研究起了做菜顺序的问题，即安排一个做菜的顺序使得同学们的等待时间最短。小M发现

2015-06-02 14:12:36 880

原创 bzoj2877 [Noi2012]魔幻棋盘 [二维线段树]

http://www.lydsy.com/JudgeOnline/problem.php?id=2877题解人生苦短。#include #define p(i, j) (((i) - 1) * m + (j))#define g(i, j) (((i) - 1) * ((m << 2) + 100) + (j))#define MAXN 555555#define lch

2015-06-02 13:57:07 1223

原创 bzoj2875 [Noi2012]随机数生成器 [矩阵+快乘]

http://www.lydsy.com/JudgeOnline/problem.php?id=2875Description 给出a,c,g,mod,x0,n,xn=(a∗xn−1+c)a,c,g,mod,x0,n,x_n=(a*x_{n-1}+c)%mod,求xn%gx_n\%g

2015-06-02 13:46:42 498

原创 bzoj2535 [Noi2010]Plane 航空管制2 [贪心+堆]

Description世博期间，上海的航空客运量大大超过了平时，随之而来的航空管制也频频发生。最近，小X就因为航空管制，连续两次在机场被延误超过了两小时。对此，小X表示很不满意。在这次来烟台的路上，小 X不幸又一次碰上了航空管制。于是小 X开始思考关于航空管制的问题。假设目前被延误航班共有 n个，编号为 1至n。机场只有一条起飞跑道，所有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。定义一

2015-05-22 13:31:04 1165

原创 bzoj2876 [Noi2012]骑行川藏 [二分+拉格朗日乘数法]

Description蛋蛋非常热衷于挑战自我，今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。川藏线的沿途有着非常美丽的风景，但在这一路上也有着很多的艰难险阻，路况变化多端，而蛋蛋的体力十分有限，因此在每天的骑行前设定好目的地、同时合理分配好自己的体力是一件非常重要的事情。由于蛋蛋装备了一辆非常好的自行车，因此在骑行过程中可以认为他仅在克服风阻做功（不受自行车本身摩擦力以及自行车与地面的摩擦力影响

2015-05-21 09:19:19 816

原创 bzoj1857 [Scoi2010]传送带 [三分套三分]

Description 在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在lxhgww想从A点走到D点，他想知道最少需要走多长时间Input 输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By 第二行是4个整数，表示C和D的坐标，分别为

2015-05-14 15:13:00 583 1

原创 poj3301Texas Trip [三分]

Description 给出n个点的坐标，求一个最小的正方形可以覆盖所有点。Input 第一行一个正整数T，表示数据的组数。每组数据第一行一个整数n，表示点的个数。接下来n行，每行两个整数表示坐标。 T <= 30, n <= 30, 坐标的绝对值<=500Output 每组数据一行一个两位小数表示正方形面积。Sample Input 2 4

2015-05-14 14:39:37 395

原创 poj3737 UmBasketella [三分]

Description 告诉你一个圆锥的表面积（包括底面积），问最大的体积是多少。Input 多组数据。每组数据一行一个实数S，表示圆锥的表面积。 1≤S≤10000.Output 每组数据输出3行：第一行一个实数表示最大的体积。第二行一个实数表示圆锥的高。第三行一个实数表示圆锥的底面半径。所有实数精确到0.01。Sample Input 30

2015-05-14 11:58:53 492

原创 bzoj3890 [Usaco2015 Jan]Meeting Time [spfa + A*]

Description Bessie and her sister Elsie want to travel from the barn to their favorite field, such that they leave at exactly the same time from the barn, and also arrive at exactly the same time at

2015-04-21 15:34:09 507

原创 hdu5114 Collision [模拟]

Description给定一个x*y的矩形，矩形里有两个小球，它们初始的速度都是(1, 1)，即向右上方。碰壁后会反弹（墙壁为x=0,x=n,y=0,y=m这4条直线），问这两个小球能否相遇，输出相遇的坐标或"Collision will not happen."Input第一行一个整数T，表示数据的组数。每组数据第一行两个整数x,y，表示矩形的长和宽。第二行4个整数x1, y1, x2, y

2015-04-11 09:51:42 598

原创 bzoj1663 [Usaco2006 Open]赶集 (最短路)

Description 每一年，约翰都会带着他的奶牛们去赶集．集会中一共有N(1≤N≤400)个商店，第i个商店会在特定的时间Pi(0≤Pi≤1090≤P_i≤10^9)对当时在店里的顾客送出一份精美的礼物．约翰当然得到了这个消息，于是他希望能拿到尽量多的礼物送给他的奶牛们．也就是说，他想尽可能多地在某商店发放礼物的时候，正好呆在店里．经过一定的调查，约翰弄清楚了从i号商店走到J

2015-04-06 21:38:32 918

原创 bzoj1698 [Usaco2007 Feb]Lilypad Pond 荷叶池塘 [BFS]

Description为了便于牛们欣赏和锻炼，农夫JOHN在他的农场上新添加了一个美丽的池塘。 JOHN的池塘是一个长方形，他已经把它划分成了M行N列的小正方行 (1 <= M <= 30; 1 <= N <= 30). 某些正方行里是石头，另外一些则是特别结实的荷叶，其余则只有清水。为了锻炼，Bessie想从一片荷叶跳到另外一片。她的每一次跳跃都是一个象棋中的马步：两行一列或一行两列。 JOHN

2015-04-02 12:59:44 881

原创 bzoj1616 [Usaco2008 Mar]Cow Travelling游荡的奶牛 [BFS]

Description奶牛们在被划分成N行M列(2 <= N <= 100; 2 <= M <= 100)的草地上游走，试图找到整块草地中最美味的牧草。Farmer John在某个时刻看见贝茜在位置 (R1, C1)，恰好T (0 < T <= 15)秒后，FJ又在位置(R2, C2)与贝茜撞了正着。 FJ并不知道在这T秒内贝茜是否曾经到过(R2, C2)，他能确定的只是，现在贝茜在那里。设S为奶

2015-04-01 14:52:03 749

原创 bzoj2006 [NOI2010]超级钢琴 [优先队列|RMQ]

Description小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个

2015-03-30 19:33:17 647

原创 bzoj1036 [ZJOI2008]树的统计Count （树链剖分|Link Cut Tree）

Description一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和注意：从点u到点v的路径上的节点包括u和v本身Input

2015-03-25 10:18:25 605

原创 [Noi2014]魔法森林（Link Cut Tree）

Description为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵：A型守护

2015-03-24 21:38:16 770

原创 bzoj2049 [Sdoi2008]Cave 洞穴勘测（Link Cut Tree）

Description辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏，然而通道不太稳定，时常因

2015-03-24 21:33:33 565

原创 bzoj2002 [Hnoi2010]Bounce 弹飞绵羊（Link Cut Tree）

Description某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，L

2015-03-24 21:18:47 538

原创图论专题整理

主要是将各种算法简单整理了一下，对于算法的具体原理没有过于深入的讲解。模板：最小生成树（MST）：给定一个n个节点的连通图，它的生成树就是原图的一个子图，它包含了原图的n个点和n-1条边。最小生成树就是权值和最小的生成树。kruskal算法求最小生成树：将原图的边按权值由小到大排序。依次考虑所有的边i，如果i的两端点u，v还没有连通，则将i加入最小生成树并将u，v标记为连通，否则抛弃i。节点的

2015-03-24 18:32:18 892

原创 poj2187 Beauty Contest 平面最远点对（凸包）

题意：给你n个点，问距离最远的两个点的距离的平方是多少。思路：最远点对一定在凸包上，所以枚举凸包上的点即可。代码：#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#define MAXN 50005using namespace std;struct Point{ long long x

2015-03-20 21:59:55 430

原创 hdu1007 Quoit Design 平面最近点对（分治）

题意：就是平面最近点对←_←思路：先把点按x坐标排好序，利用分治的思想，比如要求区间[l, r]的最近点对，先求区间[l, mid]的最近点对，再求[mid + 1, r]的最近点对，设此时的最近距离为best。但是best没有考虑一个点在左边，一个点在右边的情况。此时我们再枚举区间[mid - best, mid + best]中的所有点更新答案。

2015-03-20 21:54:14 506

原创 poj3580 SuperMemo (splay)

思路：其他的操作很简单，要说的只有关于REVOLVE操作：比如将区间[l, mid]接到区间[mid + 1, r]之后，可以先翻转区间[l, mid]，再翻转区间[mid + 1, r]，再翻转区间[l, r]。代码：#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#define MA

2015-03-20 21:36:16 355

原创 bzoj1500 [NOI2005]维修数列 splay

思路：INSERT：将pos+1旋转到根，pos+2旋转到根的右子树，然后把要插入的序列建成一颗树，接到根的右子树的左子树即可。 DELETE：将要删除的区间旋转到根的右子树的左子树，直接删去即可。 MAKE-SAME：将要修改的区间旋转到根的右子树的左子树，打上标记。 REVERSE：翻转操作类似修改操作，给区间打上标记。 GET-SUM：splay维护一个区间和，把所求区间旋转到根的右子

2015-03-15 10:58:08 399

原创 hdu3487 Play with Chain splay

题意：给你一个长度为n的1~n序列，要求实现以下两个操作： CUT i j c：将ai,ai+1,...aja_i, a_{i + 1},...a_j切下，接到新数列的第c个数之前。 FLIP i j：将ai,ai+1,...aja_i, a_{i + 1},...a_j这段序列翻转。思路：用splay维护这段序列。假设要对区间[l, r]进行操作，则将l-1旋转到根，r＋1旋转到根的右子树

2015-03-15 10:22:58 403

原创 poj1191 棋盘分割 dp

本题黑书P116有详细讲解。思路：先把方差公式化简： σ2=1n∑i=1nx2i−(x¯)2\sigma^2 = \frac 1 n \sum_{i=1}^n x_i^2 - (\bar x)^2 其中平均数是一定的，就是方格里所有的数的和除以n，所以问题转化为将棋盘分成n个矩形，使每个矩形的总分的平方和最小。考虑左上角为（x1，y1），右下角为（x2，y2）的矩形：设它的总分为s[x1,

2015-03-15 10:04:12 365

空空如也

空空如也