- 博客(64)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #292 D.Drazil and Morning Exercise
题意：有一棵带边权的树，共有nn个节点。有一些蚯蚓需要安置在此树上，每个节点只能安放11只蚯蚓，且所有蚯蚓在树上所占据的节点必须组成一个联通块。在确定位置之后，蚯蚓会同时开始朝离自己最远的节点前进，所有蚯蚓速度均为11。 给出qq次询问，每次输入一个数ll，要求输出可能安放的最多蚯蚓数，使得最先抵达终点的蚯蚓与最后的蚯蚓抵达时间之差不超过ll。数据范围：2 ≤ n ≤ 105,边权 ≤ 106,q
2017-10-21 20:36:20
455
原创 Codeforces模拟赛，题解及体会
从某种角度来说，在一个稳定举办赛事的OJ上写题的效率是比自己找题更高的。这一类的OJ包括且不限于CodeForces,Atcoder,Topcoder,Codechef,等等。此处放置部分模拟赛题解，不是给神看的，给人看吧。Contest #402 Div.1A. String Game:Little Nastya has a hobby, she likes to remove some lett
2017-10-18 17:56:38
1047
原创 CodeForces 762F. Tree nesting
You are given two trees (connected undirected acyclic graphs) S and T.Count the number of subtrees (connected subgraphs) of S that are isomorphic to tree T. Since this number can get quite large
2017-01-30 21:51:09
792
原创 CodeForces 750E. New Year and Old Subsequence
A string t is called nice if a string "2017" occurs in t as a subsequence but a string "2016" doesn't occur in t as a subsequence. For example, strings "203434107" and "9220617" are nice, while
2017-01-02 16:10:41
778
原创 BZOJ 4750: 密码安全
Description有些人在社交网络中使用过许多的密码，我们通过将各种形式的信息转化为 01 信号，再转化为整数，可以将这个人在一段时间内使用过的密码视为一个长度为 n 的非负整数序列 A_1,A_2,...,A_n 。一个人相邻几次在社交网络中使用的密码很有可能是类似的，这使得密码并不是足够安全。为了检验某些人在某些时间段内是否可能受到不安全的影响，我们需要计算上述序列的复
2017-01-01 23:00:02
731
原创 CodeForces 750F. New Year and Finding Roots
This is an interactive problem. In the interaction section below you will find the information about flushing the output.The New Year tree of height h is a perfect binary tree with vertices number
2017-01-01 20:34:43
455
原创 BZOJ1097: [POI2007]旅游景点atr
Description FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景，品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的，比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山，而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的，他可以在某些旅行方案之间进行选择。由于FGD非常讨厌乘车的颠簸，他希望在满足他的要求的情况下，旅
2017-01-01 10:58:11
575
原创 BZOJ1924: [Sdoi2010]所驼门王的宝藏
DescriptionInput第一行给出三个正整数 N, R, C。 以下 N 行，每行给出一扇传送门的信息，包含三个正整数xi, yi, Ti，表示该传送门设在位于第 xi行第yi列的藏宝宫室，类型为 Ti。Ti是一个1~3间的整数， 1表示可以传送到第 xi行任意一列的“横天门”，2表示可以传送到任意一行第 yi列的“纵寰门”，3表示可以传送到周围 8格宫
2016-12-30 19:52:08
383
原创 BZOJ 2958&3269: 序列染色
Description给出一个长度为N由B、W、X三种字符组成的字符串S，你需要把每一个X染成B或W中的一个。对于给出的K，问有多少种染色方式使得存在整数a,b,c,d使得: 1 Sa,Sa+1,...,Sb均为B Sc,Sc+1,...,Sd均为W 其中b=a+K-1,d=c+K-1由于方法可能很多，因此只需要输出最后的答案对109+7取模的结果。
2016-12-26 15:20:27
884
原创 BZOJ 1492
1492: [NOI2007]货币兑换CashTime Limit: 5 Sec Memory Limit: 64 MBSubmit: 4048 Solved: 1696[Submit][Status][Discuss]Description小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A纪念券（以下简称A券）和 B纪念券（以下简称B券）。每个持有金
2016-12-23 20:16:28
522
原创 网络流一般建模方式——最小割篇
前言：如果说网络流的难点在于建模，则最小割的难点还有一个——想到利用最小割，以及建出适用的最小割模型。一旦这两点搞定，就可以使用最小割=最大流定理解题了。1， 直接使用定理最小割释义：一个图中的一些边，使得删去这些边后整个图不连通，且这些边的总权值最小。 典型例题：太空飞行计划问题/方格取数问题/骑士共存问题 例题：【tyvj1338】QQ农场这个
2016-12-23 08:53:30
2976
原创 BZOJ4700
4700: 适者Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 43 Solved: 21[Submit][Status][Discuss]Description【题目背景】“虽然不知道那两台是谁干掉的，不过任务完成了。”一一次祖伽密．【题意描述】敌方有n台人形兵器，每台的攻击力为Ai，护甲值为Di。我方只有
2016-12-22 21:56:26
673
原创 BZOJ4539
4539: [Hnoi2016]树Time Limit: 40 Sec Memory Limit: 256 MBSubmit: 510 Solved: 194[Submit][Status][Discuss]Description 小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为N的树，结点的编号为1,2,…,N，其中结点1
2016-12-16 18:53:49
529
原创 BZOJ4008: [HNOI2015]亚瑟王
Description小 K 不慎被 LL 邪教洗脑了，洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。他决定，在脱坑之前，最后再来打一盘亚瑟王。既然是最后一战，就一定要打得漂亮。众所周知，亚瑟王是一个看脸的游戏，技能的发动都是看概率的。作为一个非洲人，同时作为一个前 OIer，小 K 自然是希望最大化造成伤害的期望值。但他已经多年没写过代码，连 Spaly都
2016-12-16 17:06:40
653
原创 网络流一般化建模方式/最大流篇
最大流模板分配类型问题：将物资均匀分配到多个点上。典型例子：网络流24题圆桌问题/试题库问题/分配问题一般化建模方式：将每个可分配的点连上源点，容量为可分配流量数；将每个待分配的点连上汇点，容量为待分配流量数；点之间按题目关系连边，容量按题目而定（1或者inf），最大流即可。例题：【tyvj1431】分配任务随着tyvj发展越来越大，管理员的任务越来越重，如何合理的
2016-12-11 21:12:38
2044
原创 1017: [JSOI2008]魔兽地图DotR
Description DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图，他的规则简单与同样流行的地图DotA (Defense of the Ancients) Allstars。DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等
2016-12-07 13:53:24
554
原创 4016: [FJOI2014]最短路径树问题
Description给一个包含n个点，m条边的无向连通图。从顶点1出发，往其余所有点分别走一次并返回。往某一个点走时，选择总长度最短的路径走。若有多条长度最短的路径，则选择经过的顶点序列字典序最小的那条路径(如路径A为1,32,11，路径B为1,3,2,11，路径B字典序较小。注意是序列的字典序的最小，而非路径中节点编号相连的字符串字典序最小)。到达该点后按原路返回，然后往其他点走，
2016-12-07 13:52:16
477
原创 BZOJ2310
2310: ParkIITime Limit: 20 Sec Memory Limit: 128 MBSubmit: 86 Solved: 34[Submit][Status][Discuss]DescriptionHnoi2007-Day1有一道题目 Park：给你一个 m * n 的矩阵，每个矩阵内有个权值V(i,j) (可能为负数)，要求找一条回路，使得每个点
2016-12-06 20:30:29
554
原创 BZOJ3697
3697: 采药人的路径Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 773 Solved: 271[Submit][Status][Discuss]Description采药人的药田是一个树状结构，每条路径上都种植着同种药材。采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的
2016-12-05 19:43:02
426
原创 BZOJ3763
3763: 最小环Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 71 Solved: 22[Submit][Status][Discuss]Description给定一个无向图，某些点之间连有一条可以双向通过的边，假设结点a,b之间有边，则从a到b会得到c[a][b]个糖果，从b到a会得到c[b][a]个糖果。问在图中
2016-12-04 12:26:40
411
原创 BZOJ 2335
2335: [SCOI2011]飞镖Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 457 Solved: 140[Submit][Status][Discuss]Description飞镖是在欧洲颇为流行的一项运动。它的镖盘上分为20个扇形区域，分别标有1到20的分值，每个区域中有单倍、双倍和三倍的区域，打中对应的
2016-12-04 12:15:02
463
1
原创 BZOJ4424
Description给定 n 个点，m 条边的无向图，可以从图中删除一条边，问删除哪些边可以使图变成一个二分图。Input第 1 行包含两个整数 n，m。分别表示点数和边数。第 2 到 m+1 行每行两个数 x，y 表示有一条（x,y）的边。Output输出第一行一个整数，表示能删除的边的个数。接下来一行按照从小到大的顺序输
2016-12-03 13:32:47
574
原创 BZOJ3165
3165: [Heoi2013]SegmentTime Limit: 40 Sec Memory Limit: 256 MBSubmit: 432 Solved: 172[Submit][Status][Discuss]Description要求在平面直角坐标系下维护两个操作： 1.在平面上加入一条线段。记第i条被插入的线段的标号为i。 2.给定一个数k,询
2016-12-01 20:59:45
657
1
原创 BZOJ 3113: Toy
Description外面有一圈N个结点，中心有一个结点与N个结点都相连，总共就是2*N条边，删除N条边，使N+1个点连通，旋转相同视为等价，问有多少种情况。Input输入N，M3Output输出方案数 Mod M的结果Sample Input3 100004 100004 10Sample Output
2016-11-29 23:32:18
458
原创 网络流24题 前9题 一段话题解
网络流24题题解（无代码）：实际上网络流的题考的主要是建模能力，而非算法。只要记住Dinic和最小费用流算法，接下来需要训练的就是抽象思维和转化。（或说刷题，也一样。）网络流24题中虽然有一些dp题目，但总的来说仍然是极好的网络流新手训练题集，在此给出思路与题解。1，飞行员配对方案问题Description 第二次世界大战时期，英国皇家空军从沦陷国征募了大量
2016-11-28 22:54:29
848
原创 Bzoj 4726
Description某个公司有n个人, 上下级关系构成了一个有根树。其中有个人是叛徒(这个人不知道是谁)。对于一个人, 如果他下属(直接或者间接, 不包括他自己)中叛徒占的比例超过x，那么这个人也会变成叛徒，并且他的所有下属都会变成叛徒。你要求出一个最小的x，使得最坏情况下，叛徒的个数不会超过k。Input第一行包含两个正整数n,k(1接下来n-1行，
2016-11-26 18:09:59
603
原创 bzoj1061
Description 申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，
2016-11-26 15:34:52
398
原创 BZOJ 3196: Tyvj 1730 二逼平衡树
Description您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：1.查询k在区间内的排名2.查询区间内排名为k的值3.修改某一位值上的数值4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)5.查询k在区间内的后继(后继定义为大于x，且最小的数)Input第一行两个数 n,m 表示长度为n的有序序列和m个操作
2016-11-17 00:36:56
479
原创 BZOJ1087
1087: [SCOI2005]互不侵犯KingTime Limit: 10 Sec Memory Limit: 162 MBSubmit: 3235 Solved: 1878[Submit][Status][Discuss]Description 在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方
2016-11-16 19:58:06
389
原创 BZOJ 3343: 教主的魔法
Description教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。 每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个
2016-11-15 21:26:18
432
原创 BZOJ1044
1044: [HAOI2008]木棍分割Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3291 Solved: 1238[Submit][Status][Discuss]Description 有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连接处, 砍完
2016-11-15 19:03:28
474
原创 BZOJ4131
4131: 并行博弈Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 24 Solved: 15[Submit][Status][Discuss]Descriptionlyp和ld在一个n*m的棋盘上玩翻转棋，游戏棋盘坐标假设为(x, y)，1 ≤ x ≤ n，1 ≤ y ≤ m，这个游戏的游戏的的游戏规则如下：每次可以操
2016-11-14 19:08:28
525
原创 BZOJ 1057
1057: [ZJOI2007]棋盘制作Time Limit: 20 Sec Memory Limit: 162 MBSubmit: 2481 Solved: 1230[Submit][Status][Discuss]Description 国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个
2016-11-13 15:18:15
265
原创 BZOJ 1064
Description一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一 个自己喜欢的面具。每个面具都有一个编号，主办方会把此编号告诉拿该面具的人。为了使舞会更有神秘感，主办方把面具分为k (k≥3)类，并使用特殊的技术将每个面具的编号标在了面具上，只有戴第i 类面具的人才能看到戴第i+1 类面具的人的编号
2016-11-08 20:37:21
324
原创 bzoj2242
2242: [SDOI2011]计算器Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 3179 Solved: 1248[Submit][Status][Discuss]Description你被要求设计一个计算器完成以下三项任务：1、给定y,z,p,计算Y^Z Mod P 的值；2、给定y,z,p，计算满足xy≡
2016-11-08 14:04:13
411
原创 BZOJ 3037(water problem)
This is a water problem.3037: 创世纪Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 324 Solved: 134[Submit][Status][Discuss]Descriptionapplepi手里有一本书《创世纪》，里面记录了这样一个故事……上帝手中有着N 种被称作“世界元
2016-11-07 21:30:48
534
原创 BZOJ3630
3630: [JLOI2014]镜面通道Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 478 Solved: 166[Submit][Status][Discuss]Description在一个二维平面上，有一个镜面通道，由镜面AC，BD组成，AC，BD长度相等，且都平行于x轴，B位于（0，0）。通道中有n个外表面为镜面的
2016-11-03 16:43:39
480
原创 BZOJ1007
先吹一波司机强1007: [HNOI2008]水平可见直线Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 6177 Solved: 2342[Submit][Status][Discuss]Description 在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往下看,能见到Li的某个
2016-11-02 21:07:48
378
原创 BZOJ 1047
二维单调队列#include#include#include#include#define maxn 1010using namespace std;int n,m,r,mx[maxn][maxn],mn[maxn][maxn],ma[maxn][maxn];struct queue{ int ql,qr,q[maxn][2],lim,f; queue(){ql=qr=0;}
2016-10-31 17:43:34
417
原创 hihocoder #24 Rikka with Subsequence
题目2 : Rikka with Subsequence时间限制:10000ms单点时限:1000ms内存限制:256MB描述众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：勇太有一个长度为n的字符串s，现在他对这个字符串进行了一些操作，在操作之后第i个字符有Ai%的概率被删除。现在他想要知道
2016-10-31 11:57:43
550
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人