- 博客(76)
- 收藏
- 关注
RSS订阅
原创 BZOJ3833[Poi2014] Solar lamps
Task：有很多盏灯，第ii盏灯在第ii个时刻点亮。如果有至少kik_i盏灯照亮了第ii盏灯，那么这盏灯就将被点亮。每盏灯照亮的范围都是一样角度的一个区域且无限延伸，给定(x1,y1),(x2,y2)(x1,y1),(x2,y2)表示如果这盏灯的坐标在(x,y)(x,y)，那么它的照亮范围为射线(x,y)→(x+x1,y+y1)(x,y)\to (x+x1,y+y1)与射线(x,y)→(x+x2,y
2016-11-09 19:49:56
703
原创 BZOJ3832[Poi2014] Rally
Task：给定一个有向无环图，边的长度都为1。找到一个点使得删掉这个点后图中剩余的最长路径最短。(N<=500 000,M<=1 000 000)Solution：神一样的题…将原图划分为两个集合S,TS,T。一开始所有点都属于TT，然后按照拓扑序逐步将TT中的点移到SS中，同时统计答案。当然这样讲并不能懂，来看一看实际的做法：拓扑dp处理出，表示到点的最长路，点出发的最长路。首先把所有的都加入
2016-11-08 18:59:05
437
原创 NOIP2014 解方程
NOIP2014 解方程 Description Input 输入文件名为equation.in。 输入共n+2行。 第一行包含2个整数n、m，每两个整数之间用一个空格隔开。 接下来的n+1行每行包含一个整数，依次为a0,a1,a2,……,an。 Output
2016-11-08 15:16:11
533
原创 NOIP2014 飞扬的小鸟
NOIP2014 飞扬的小鸟 Description Input Output 输出文件名为 bird.out。 共两行。 第一行，包含一个整数，如果可以成功完成游戏，则输出 1，否则输出 0。 第二行，包含一个整数，如果第一行为 1，则输出
2016-11-07 15:49:54
388
原创 NOIP2013 华容道
NOIP2013 华容道 Description 小 B 最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面，华容道是否根本就无法完成，如果能完成，最少需要多少时间。 小 B 玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的： 在一个 n*m 棋盘上有 n*m 个格子，
2016-11-04 21:54:37
957
原创 NOIP2012 开车旅行
NOIP 2012开车旅行 Description 小A 和小B决定利用假期外出旅行，他们将想去的城市从1到N 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 i的海拔高度为Hi，城市 i 和城市 j 之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d[i, j] = |Hi − Hj|。 旅行过程
2016-11-01 16:48:13
598
原创 Topcoder SRM 701 Div2 900 ThueMorseGame
Topcoder SRM 701 Div2 900 ThueMorseGame Problem Statement Alice and Bob play a game with a pile of stones. Initially, there are n stones in the pile. The players take alternating turns,
2016-10-31 21:48:38
508
原创 NOI2013 快餐店
NOI2013 快餐店 Description 小T打算在城市C开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，小T希望快餐店的地址选在离最远的顾客距离最近的地方。 快餐店的顾客分布在城市C的N 个建筑中，这N 个建筑通过恰好N 条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存
2016-10-30 22:16:25
562
原创 BZOJ3831[Poi2014] Little Bird
BZOJ3831[Poi2014] Little Bird Description 有一排n棵树，第i棵树的高度是Di。 MHY要从第一棵树到第n棵树去找他的妹子玩。 如果MHY在第i棵树，那么他可以跳到第i+1,i+2,…,i+k棵树。 如果MHY跳到一棵不矮于当前树的树，那么他的劳累值会+1，否则不会。
2016-10-28 15:49:05
432
原创 BZOJ3830[Poi2014] Freight
BZOJ3830[Poi2014] Freight Description Upper Bytown和Lower Bytown的火车站被一条铁路连接着。火车从一侧到另一侧需要S分钟。然而，每两列车发车时间至少需要间隔一分钟。并且，在每一个时刻，在铁路上的所有列车的行驶方向都必须相同。 按照时间表的顺序，N辆列车将从Upper Bytown出发前往Low
2016-10-28 09:38:03
805
原创 BZOJ3526[Poi2014] Card
BZOJ3526[Poi2014] Card Description 有n张卡片在桌上一字排开，每张卡片上有两个数，第i张卡片上，正面的数为a[i]，反面的数为b[i]。现在，有m个熊孩子来破坏你的卡片了！ 第i个熊孩子会交换c[i]和d[i]两个位置上的卡片。 每个熊孩子捣乱后，你都需要判断，通过任意翻转卡片（把正面变为反面或把反面
2016-10-26 22:08:48
804
原创 Codeforces 2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror)
人生的第一次ACM啊（虽然是镜像）…先来一张临时组建队伍GZC的合影：开始的时候Chongkan迷之手气直接抽H，敲掉了最水的一道题（各种WA），于是从一脸懵逼的蒟蒻我手中接过了A题，说些什么我听不懂的东西，然后就去敲了…[Kanosword在敲B题]一看G题A的人挺多的，我就去看G题了。一看貌似挺水的，随便搞了个multiset维护了一下区间。原本还想用什么lower_bound之类的，然后小C出
2016-10-24 10:18:52
990
原创 BZOJ3827[Poi2014] Around the world
BZOJ3827[Poi2014] Around the world Description 通过几年的努力，Byteasar最终拿到了飞行员驾驶证。为了庆祝这一事实，他打算买一架飞机并且绕Byteotia星球赤道飞行一圈。但不幸的是赤道非常长所以需要中途加几次油。现在已知赤道上面所有飞机场，所有飞机从飞机场起飞降落也可以加油。因为买飞机是个十分重大的决定，Byteas
2016-10-24 09:57:57
898
原创 BZOJ3524[Poi2014] Couriers
BZOJ3524[Poi2014] Couriers Description 给一个长度为n的序列a。1≤a[i]≤n。 m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。 Input 第一行两个数n，m。 第二行n
2016-10-22 19:56:52
424
原创 NOIP2016初赛记
10.22 初赛日早晨，站在机房的门外，照例眺望远方的那座山。雾气好重，云雾缭绕，远山躺在一片白茫茫之中，看不清楚。中午，雾气散了些，山峰棱角分明了些，我们也坐上了大巴，开往温州。一路开着各种退役的玩笑，就开进了十二中。然而来得太早了？早到了一个半小时，保安不让我们下车233，于是一群人各种找厕所…等待的时候看到了好多认识的人。说实话，等待发试卷的时候反而比考的时候更要紧张，也不知道在想些什么东西。
2016-10-22 19:22:31
899
2
原创 BZOJ3521[Poi2014] Salad Bar
BZOJ3521[Poi2014] Salad Bar Description 有一个长度为n的字符串，每一位只会是p或j。你需要取出一个子串S（从左到右或从右到左一个一个取出），使得不管是从左往右还是从右往左取，都保证每时每刻已取出的p的个数不小于j的个数。你需要最大化|S|。 Input 第一行一个数n，第二行一个长度n的字符串。
2016-10-21 21:42:34
1231
原创 排序算法一览
总述：排序，初赛知识点之一，都敲了一遍，供初赛复习。此处收录了10 9种常见排序算法。只给出部分程序代码，读入一律使用Rd函数，输出为Pf。计数排序。稳定，复杂度O(n+m)O(n+m)Rd(n);while(n--){ Rd(x); cnt[x]++;}for(int i=1;i<=10;i++) for(int j=1;j<=cnt[i];j++)
2016-10-21 11:27:27
355
原创 BZOJ4383[POI2015] Pustynia
BZOJ4383[POI2015] Pustynia Description 给定一个长度为n的正整数序列a，每个数都在1到10^9范围内，告诉你其中s个数，并给出m条信息，每条信息包含三个数l,r,k以及接下来k个正整数，表示a[l],a[l+1],…,a[r-1],a[r]里这k个数中的任意一个都比任意一个剩下的r-l+1-k个数大（严格大于，即没有等号）。
2016-10-19 18:02:20
579
原创 BZOJ4382[POI2015] Podział naszyjnika
BZOJ4382[POI2015] Podział naszyjnika Description 长度为n的一串项链，每颗珠子是k种颜色之一。 第i颗与第i-1,i+1颗珠子相邻，第n颗与第1颗也相邻。 切两刀，把项链断成两条链。要求每种颜色的珠子只能出现在其中一条链中。 求方案数量（保证至少存在一种），以及切成的两段长度之差绝对值的
2016-10-18 18:28:43
657
原创 BZOJ4384[POI2015] Trzy wieże
BZOJ4384[POI2015] Trzy wieże Description 给定一个长度为n的仅包含’B’、’C’、’S’三种字符的字符串，请找到最长的一段连续子串，使得这一段要么只有一种字符，要么有多种字符，但是没有任意两种字符出现次数相同。 Input 第一行包含一个正整数n(1<=n<=1000000)，表示字符串的长度。
2016-10-18 13:53:17
732
原创 BZOJ4377[POI2015] Kurs szybkiego czytania
BZOJ4377[POI2015] Kurs szybkiego czytania Description 给定n,a,b,p，其中n,a互质。定义一个长度为n的01串c[0..n-1]，其中c[i]==0当且仅当(ai+b) mod n < p。 给定一个长为m的小01串，求出小串在大串中出现了几次。 Input
2016-10-18 10:58:24
428
原创 BZOJ4386[POI2015] Wycieczki
BZOJ4386[POI2015] Wycieczki Description 给定一张n个点m条边的带权有向图，每条边的边权只可能是1，2，3中的一种。 将所有可能的路径按路径长度排序，请输出第k小的路径的长度，注意路径不一定是简单路径，即可以重复走同一个点。 Input 第一行包含三个整数n,m,k(1<=n<=
2016-10-17 09:12:57
753
原创 矩阵
定义矩阵乘法：C=ABC=AB如果AA是m∗nm*n矩阵，BB是n∗pn*p矩阵，那么CC是一个m∗pm*p矩阵。其中Cik=∑nk=1AijBjkC_{ik}=\sum_{k=1}^{n}A_{ij}B_{jk}，如： [142536]⎡⎣⎢135246⎤⎦⎥=[1+6+154+15+302+8+188+20+36]=[22492864]\begin{bmatrix}1 & 2 & 3\\
2016-10-17 08:14:45
365
原创 BZOJ4380[POI2015] Myjnie
BZOJ4380[POI2015] Myjnie Description 有n家洗车店从左往右排成一排，每家店都有一个正整数价格p[i]。 有m个人要来消费，第i个人会驶过第a[i]个开始一直到第b[i]个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于c[i]，那么这个人就不洗车了。 请给每家店指定一个
2016-10-14 20:52:04
836
原创 BZOJ4379[POI2015] Modernizacja autostrady
BZOJ4379[POI2015] Modernizacja autostrady Description 给定一棵无根树，边权都是1，请去掉一条边并加上一条新边，定义直径为最远的两个点的ju距离，请输出所有可能的新树的直径的最小值和最大值。 Input 第一行包含一个正整数n(3<=n<=500000)，表示这棵树的点数。
2016-10-14 19:07:12
517
原创 HDU5293 Tree chain problem
HDU5293 Tree chain problem Problem Description Coco has a tree, whose vertices are conveniently labeled by 1,2,…,n. There are m chain on the tree, Each chain has a certain weigh
2016-10-12 13:51:09
396
原创 BZOJ3749[POI2015] Łasuchy
BZOJ3749[POI2015] Łasuchy Description 圆桌上摆放着n份食物，围成一圈，第i份食物所含热量为c[i]。 相邻两份食物之间坐着一个人，共有n个人。每个人有两种选择，吃自己左边或者右边的食物。如果两个人选择了同一份食物，这两个人会平分这份食物，每人获得一半的热量。 假如某个人改变自己的选择后（其他n-1
2016-10-12 12:41:09
617
原创 BZOJ4385[POI2015] Wilcze doły
BZOJ4385[POI2015] Wilcze doły Description 给定一个长度为n的序列，你有一次机会选中一段连续的长度不超过d的区间，将里面所有数字全部修改为0。 请找到最长的一段连续区间，使得该区间内所有数字之和不超过p。 Input 第一行包含三个整数n,p,d(1<=d<=n<=200000
2016-10-12 11:13:30
380
原创 BZOJ4381[POI2015] Odwiedziny
BZOJ4381[POI2015] Odwiedziny Description 给定一棵n个点的树，树上每条边的长度都为1，第i个点的权值为a[i]。 Byteasar想要走遍这整棵树，他会按照某个1到n的全排列b走n-1次，第i次他会从b[i]点走到b[i+1]点，并且这一次的步伐大小为c[i]。 对于一次行走，假设起点为x，终点
2016-10-12 10:41:46
485
原创 BZOJ4378[POI2015] Logistyka
BZOJ4378[POI2015] Logistyka Description 维护一个长度为n的序列，一开始都是0，支持以下两种操作： 1.U k a 将序列中第k个数修改为a。 2.Z c s 在这个序列上，每次选出c个正数，并将它们都减去1，询问能否进行s次操作。 每次询问独立，即每次询问不会对序列进行修改。
2016-10-12 10:22:34
470
原创 树上的分治算法
附论文：《分治算法在树的路径问题中的应用》点分治 POJ1741 Tree Description Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node
2016-10-09 12:59:57
619
原创 BZOJ3747[POI2015] Kinoman
BZOJ[POI2015] Kinoman Description 共有mm部电影，编号为11~mm，第ii部电影的好看值为w[i]w[i]。 在nn天之中（从11~nn编号）每天会放映一部电影，第ii天放映的是第f[i]f[i]部。 你可以选择l,r(1<=l<=r<=n)l,r(1<=l<=r<=n)，并观看第l,l+1,…,rl,l+1
2016-10-05 22:08:47
366
原创 2016.10.5常规赛总结
哈哈忍不住先自嘲一下不过其实今天做的还是很不错的，比前几次花式倒数强多了。特别是第三题的树链剖分200行能够写出来还是感觉很棒的。（虽然AK大犇直接暴力修改就过了）第一题有一个地方，细节做得不是很好，只有90分，当然如果想法比较好的话就不会有这些问题了，代码也会比较短。第二题没什么问题，直接dp稍微优化一下就A了。第三题这个就比较尴尬了，结构体里习惯性的初始化了一下值。CE. 其实今天还特意留
2016-10-05 16:02:53
322
原创 BZOJ2087[Poi2010] Sheep
BZOJ2087[Poi2010] Sheep Description Lyx的QQ牧场养了很多偶数个的羊，他是Vip，所以牧场是凸多边形（畸形）。现在因为他开挂，受到了惩罚，系统要求他把牧场全部分为三角形（划分线不能在牧场中相交，只能在顶点相交），羊也是有个性的，如果他们在三角形中是单数就会有羊自杀（Lyx的样就是畸形），这让Lyx很难办，于是他向你求助了。
2016-10-04 15:37:01
581
原创 BZOJ2095[Poi2010] Bridges
BZOJ2095[Poi2010] Bridges Description YYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海上，风变得十分大，
2016-10-03 15:28:11
374
原创 欧拉回路
欧拉回路以下部分引用于《欧拉回路性质与应用探究》相关概念：欧拉回路：图GG中经过每条边一次并且仅一次的回路称为欧拉回路。欧拉路径：图GG中经过每条边一次并且仅一次的路径称为欧拉路径。欧拉图：存在欧拉回路的图称为欧拉图。半欧拉图：存在欧拉路径但不存在欧拉回路的图称为半欧拉图。关于欧拉图的判定： 无向图：无向图GG为欧拉图，当且仅当GG为连通图且所有顶点度为偶数。（已排除孤立点）
2016-10-03 15:24:53
661
1
原创 BZOJ2093[Poi2010] Frog
BZOJ2093[Poi2010] Frog Description 一个条河无限宽，上面有n块石头，石头离左边的河岸（无限宽，右边河岸不晓得在哪）距离严格递增，现在Zxl想锻炼自己的跳跃能力（谁叫他在班里外号是鸟怪。。畸形），他在某一块石头上，想跳到离他这块石头第k远的石头上去，假如离他第k远的石头不是唯一的，他就选离岸最近的那一个（不然回不去了），他想你让他知道，从
2016-10-03 11:12:27
655
原创 网络流学习记录
网络流学习记录总述： 目前已学习的内容： Ford-Fulkerson O(FE)O(FE) Edmonds-Karp O(E2V)O(E^2V) Dinic O(EV2)O(EV^2) 持续学习中…Ford-Fulkerson最大流的一种最基础的算法，想要搞清楚首先需要弄清楚反向边的作用。假设我们已经获得了一条按如图所示流向的最大流（黑色路径），此时我
2016-10-02 19:42:16
280
原创 BZOJ2091[Poi2010] The Minima Game
BZOJ2091[Poi2010] The Minima Game Description 给出N个正整数，AB两个人轮流取数，A先取。每次可以取任意多个数，直到N个数都被取走。 每次获得的得分为取的数中的最小值，A和B的策略都是尽可能使得自己的得分减去对手的得分更大。 在这样的情况下，最终A的得分减去B的得分为多少。
2016-09-29 11:00:32
361
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人