- 博客(458)
- 收藏
- 关注
RSS订阅原创 [Luogu P4649] [BZOJ 1808] [IOI2007] training 训练路径
洛谷传送门BZOJ传送门题目描述马克(Mirko)和斯拉夫克(Slavko)正在为克罗地亚举办的每年一次的双人骑车马拉松赛而紧张训练。他们需要选择一条训练路径。他们国家有NNN个城市和MMM条道路。每条道路连接两个城市。这些道路中恰好有N−1N-1N−1条是铺设好的道路，其余道路是未经铺设的土路。幸运的是，每两个城市之间都存在一条由铺设好的道路组成的通路。换句话说，这NNN个城市和N−1N...
2019-03-31 22:55:11
371
原创 [Luogu P4244] [BZOJ 1023] [SHOI2008]仙人掌图 II
洛谷传送门BZOJ传送门题目描述如果某个无向连通图的任意一条边至多只出现在一条简单回路（simple cycle）里，我们就称这张图为仙人掌图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，...
2019-03-29 11:52:11
322
原创 [Luogu P4630] [BZOJ 5463] [APIO2018] Duathlon 铁人两项
洛谷传送门BZOJ传送门题目描述比特镇的路网由 mmm 条双向道路连接的 nnn 个交叉路口组成。最近，比特镇获得了一场铁人两项锦标赛的主办权。这场比赛共有两段赛程：选手先完成一段长跑赛程，然后骑自行车完成第二段赛程。比赛的路线要按照如下方法规划：先选择三个两两互不相同的路口 s,cs, cs,c和 fff，分别作为比赛的起点、切换点（运动员在长跑到达这个点后，骑自行车前往终点）、终...
2019-03-29 11:46:43
301
原创 [Luogu P5236] [BZOJ 2125] (仙人掌)最短路
洛谷传送门BZOJ传送门题目描述给你一个有nnn个点和mmm条边的仙人掌图，和qqq组询问每次询问两个点u,vu,vu,v，求两点之间的最短路。输入输出格式输入格式：第一行三个正整数n,m,qn,m,qn,m,q，意义如题目描述。接下来mmm行，每行三个正整数u,v,wu,v,wu,v,w，表示u,vu,vu,v之间有一条权值为www的无向边。然后qqq行，每行两个正整数u,vu...
2019-03-29 11:22:56
386
原创 [Luogu P3286] [BZOJ 3598] [SCOI2014]方伯伯的商场之旅
洛谷传送门BZOJ传送门题目描述方伯伯有一天去参加一个商场举办的游戏。商场派了一些工作人员排成一行。每个人面前有几堆石子。说来也巧，位置在 iii 的人面前的第 jjj 堆的石子的数量，刚好是 iii 写成 KKK 进制后的第 jjj 位。现在方伯伯要玩一个游戏，商场会给方伯两个整数 L,RL,RL,R。方伯伯要把位置在 [L,R][L, R][L,R] 中的每个人的石子都合并成一堆石子...
2019-03-29 11:15:19
245
原创 [Luogu P3287] [BZOJ 3594] [SCOI2014]方伯伯的玉米田
洛谷传送门BZOJ传送门题目描述方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。这排玉米一共有NNN株，它们的高度参差不齐。方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。方伯伯可以选择一个区间，把这个区间的玉米全部拔高111单位高度，他可以进行最多KKK次这样的操作。拔玉米则可以随意选择一个集合的...
2019-03-26 23:06:49
220
原创 [Luogu P4250] [BZOJ 4445] [SCOI2015]小凸想跑步
洛谷传送门BZOJ传送门题目描述小凸晚上喜欢到操场跑步，今天他跑完两圈之后，他玩起了这样一个游戏。操场是个凸 nnn 边形， nnn 个顶点按照逆时针从 0∼n−10 \sim n - 10∼n−1 编号。现在小凸随机站在操场中的某个位置，标记为 ppp点。将 ppp 点与 nnn 个顶点各连一条边，形成 nnn 个三角形。如果这时 ppp 点， 000 号点， 111 号点形成的三角形的...
2019-03-26 22:54:42
259
原创 [Luogu P4253] [BZOJ 4446] [SCOI2015]小凸玩密室
洛谷传送门BZOJ传送门题目描述小凸和小方相约玩密室逃脱，这个密室是一棵有 nnn 个节点的完全二叉树，每个节点有一个灯泡。点亮所有灯泡即可逃出密室。每个灯泡有个权值 aia_iai，每条边也有个权值 bib_ibi。点亮第一个灯泡不需要花费，之后每点亮一个新的灯泡 vvv 的花费，等于上一个被点亮的灯泡 uuu 到这个点 vvv 的距离 Du,vD_{u,v}Du,v，乘以这个点的权...
2019-03-26 22:41:17
261
原创 [Luogu P4469] [BZOJ 1075] [SCOI2007]最优驾车
洛谷传送门BZOJ传送门题目描述有nnn条南北方向的双向街道和nnn条东西方向的双向街道纵横交错。相邻街道（不管是哪个走向）的距离均为LLL英里。西南角交叉口的坐标为(1,1)(1,1)(1,1)，东北角为(n,n)(n,n)(n,n)。在所有交叉口均可任意改变行驶方向。每条街道有它自己的最高速度限制，该限制对整条街道有效（不管行驶方向如何）。你的任务是从交叉口(xs,ys)(x_s,y_...
2019-03-25 18:37:41
213
原创 [Luogu P2569] [BZOJ 1855] [SCOI2010]股票交易
洛谷传送门BZOJ传送门题目描述最近 lxhgww\text{lxhgww}lxhgww 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。通过一段时间的观察，lxhgww\text{lxhgww}lxhgww 预测到了未来 TTT 天内某只股票的走势，第 iii 天的股票买入价为每股 APiAP_iAPi，第 iii天的股票卖出价为每股 BPiBP_iBPi（...
2019-03-25 18:15:02
210
原创 [Luogu P5045] [BZOJ 1092] [SCOI2003]蜘蛛难题
洛谷传送门BZOJ传送门题目描述有一堆管道，还有一个蜘蛛Willy\text{Willy}Willy，如下图所示。所有管道的是上端开口，下端封底，直径都是1cm1cm1cm，连接两个管道的连接容量无限，但体积可以忽略不计。在第一个管道上方有一个水源，从中有水不断往下流，速度为每秒0.25cm30.25cm^30.25cm3。由于管道横截面积为0.25cm20.25cm^20.25cm2，...
2019-03-23 22:31:54
200
原创 [Luogu P2566] [BZOJ 1294] [SCOI2009]围豆豆
洛谷传送门BZOJ传送门题目描述是不是平时在手机里玩吃豆豆游戏玩腻了呢？最近MOKIA手机上推出了一种新的围豆豆游戏，大家一起来试一试吧。游戏的规则非常简单，在一个N×MN×MN×M的矩阵方格内分布着DDD颗豆子，每颗豆有不同的分值ViV_iVi。游戏者可以选择任意一个方格作为起始格，每次移动可以随意的走到相邻的四个格子，直到最终又回到起始格。最终游戏者的得分为所有被路径围住的豆豆的分值...
2019-03-23 22:00:24
160
原创 [Luogu P3214] [BZOJ 4339] [HNOI2011]卡农
洛谷传送门BZOJ传送门题目描述众所周知卡农是一种复调音乐的写作技法，小余在听卡农音乐时灵感大发，发明了一种新的音乐谱写规则。他将声音分成 nnn 个音阶，并将音乐分成若干个片段。音乐的每个片段都是由 111 到 nnn 个音阶构成的和声，即从 nnn 个音阶中挑选若干个音阶同时演奏出来。为了强调与卡农的不同，他规定任意两个片段所包含的音阶集合都不同。同时为了保持音乐的规律性，他还规定在一段...
2019-03-23 21:36:14
170
原创 [Luogu P3277] [BZOJ 2335] [SCOI2011]飞镖
洛谷传送门BZOJ传送门题目描述飞镖是在欧洲颇为流行的一项运动。它的镖盘上分为202020个扇形区域，分别标有111到202020的分值，每个区域中有单倍、双倍和三倍的区域，打中对应的区域会得到分值乘以倍数所对应的分数。例如打中181818分里面的三倍区域，就会得到545454分。另外，在镖盘的中央，还有”小红心“和”大红心“，分别是252525分和505050分。通常的飞镖规则还有一...
2019-03-21 21:53:01
180
原创 [Luogu P3291] [BZOJ 3570] [SCOI2016]妖怪
洛谷传送门BZOJ传送门题目描述邱老师是妖怪爱好者，他有nnn只妖怪，每只妖怪有攻击力atk和防御力dnf两种属性。邱老师立志成为妖怪大师，于是他从真新镇出发，踏上未知的旅途，见识不同的风景。环境对妖怪的战斗力有很大影响，在某种环境中，妖怪可以降低自己k∗ak*ak∗a点攻击力，提升k∗bk*bk∗b点防御力或者，提升自己k∗ak*ak∗a点攻击力，降低k∗bk*bk∗b点防御力，aaa，...
2019-03-21 18:16:54
203
原创 [Luogu P2470] [BZOJ 1068] [SCOI2007]压缩
洛谷传送门BZOJ传送门题目描述给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母RRR与MMM，其中MMM标记重复串的开始，RRR重复从上一个MMM（如果当前位置左边没有MMM，则从串的开始算起）开始的解压结果（称为缓冲串）。bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程：已经解压的...
2019-03-21 16:47:45
178
原创 [Luogu P2329] [BZOJ 1082] [SCOI2005]栅栏
洛谷传送门BZOJ传送门题目描述农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为101010的木板可以切成长度为888和222的两个木板。你的任务：给你约翰所需要...
2019-03-21 16:17:12
185
原创 [Luogu P4165] [BZOJ 1071] [SCOI2007]组队
洛谷传送门BZOJ传送门题目描述NBA每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为minVminVminV，身高最矮的球员高度为minHminHminH，那么这支球队的所有队员都应该满足:$ A × ( height – minH ) + B × ( speed – minV ) \le C$ 其中AAA和BBB，CCC为...
2019-03-20 21:30:51
156
原创 [Educational Codeforces Round 32] - G Xor-MST
洛谷传送门Codeforces传送门题意翻译已知一个nnn个节点的无向完全图，第iii个节点的权值为aia_iai,iii与jjj的边的权值是KaTeX parse error: Expected '}', got '^' at position 10: a_i\text{^̲}a_j,求该图的MST的权值解题分析贪心地想， 从高位往低位考虑， 我们一定是先考虑在这一位都为111或都为...
2019-03-20 16:48:15
145
原创 [Educational Codeforces Round 7] - F The Sum of the k-th Powers
洛谷传送门Codeforces传送门题目大意求∑i=1nikmod  (109+7)\sum_{i=1}^ni^k\mod (10^9+7)∑i=1nikmod(109+7)， n≤109,k≤106n\le 10^9,k\le 10^6n≤109,k≤106解题分析首先可以知道的是， 答案是一个k+1k+1k+1次， 关于...
2019-03-18 18:56:44
137
原创 [Luogu P4022] [BZOJ 2806] [CTSC2012]熟悉的文章
洛谷传送门BZOJ传送门题目描述阿米巴是小强的好朋友。在小强眼中，阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的真谛，小强向阿米巴求教。阿米巴给小强展示了几篇作文，小强觉得这些文章怎么看怎么觉得熟悉，仿佛是某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了疑惑的眼光，却发现阿米巴露出了一个狡黠的微笑。为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”，小强想出了一个评定作文...
2019-03-18 18:44:13
171
原创 [VK Cup 2016 - Round 3] - D Bearish Fanpages
洛谷传送门Codeforces传送门题目描述There is a social website with nnn fanpages, numbered 111 through nnn . There are also nnn companies, and the iii-th company owns the iii -th fanpage.Recently, the website cr...
2019-03-18 18:26:53
247
原创 [BZOJ 3786] 星系探索
BZOJ传送门题目描述物理学家小C的研究正遇到某个瓶颈。他正在研究的是一个星系，这个星系中有nnn个星球，其中有一个主星球(方便起见我们默认其为111号星球)，其余的所有星球均有且仅有一个依赖星球。主星球没有依赖星球。我们定义依赖关系如下：若星球aaa的依赖星球是bbb,则有星球aaa依赖星球bbb.此外，依赖关系具有传递性，即若星球aaa依赖星球bbb,星球bbb依赖星球ccc,则有星球...
2019-03-18 08:22:33
283
原创 [BZOJ 4241] 历史研究
BZOJ传送门题目描述IOI国历史研究的第一人——JOI教授，最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活，开始着手调查日记中记载的事件。日记中记录了连续NNN天发生的时间，大约每天发生一件。事件有种类之分。第iii天(1≤i≤N)(1\le i\le N)(1≤i≤N)发生的事件的种类用一个整数XiX_iXi表示，XiX_iXi...
2019-03-17 23:10:25
193
原创 [LOJ #565] 「LibreOJ Round #10」mathematican 的二进制
LOJ传送门题目描述有一个长度很大的二进制串，初始时它的每一位都为 000。现在有 mmm 个操作，其中第 iii 个操作是将这个二进制串的数值加上 2ai(0≤ai≤n){2}^{a_i}({0}\leq{a_i}\leq{n})2ai(0≤ai≤n)，或者说，给第 $a_i $位加上 111 并进位，我们称每次操作的代价是这次操作改变的位的数量。例如，当前的二进制串是 10111 时，...
2019-03-16 08:04:12
244
原创 [Wunder Fund Round 2016 (Div. 1 + Div. 2 combined)] - E Robot Arm
洛谷传送门Codeforces传送门题目大意给你一个有nnn段的机械臂， 给出mmm个操作， 每次将一截机械臂伸长lil_ili或顺时针旋转lll°。 在每次操作后你需要回答一开始最靠右点当前的位置。解题分析很好的一道线段树题， 假设[l−1,l][l-1,l][l−1,l]是水平的， 维护[l,r][l, r][l,r]相对于lll的位置和最右端机械臂的角度， 然后就可以用线段树合并...
2019-03-14 21:46:30
230
原创 [Luogu P4097] [BZOJ 3165] [HEOI2013]Segment
洛谷传送门BZOJ传送门题目描述要求在平面直角坐标系下维护两个操作：在平面上加入一条线段。记第 iii 条被插入的线段的标号为 iii给定一个数 kkk,询问与直线 x=kx = kx=k 相交的线段中，交点最靠上的线段的编号。输入输出格式输入格式：第一行一个整数 nnn，表示共 nnn 个操作接下来 nnn 行，每行第一个数为 000 或 111若该数为 000，则后面跟...
2019-03-14 20:31:06
171
原创 [Codeforces Round #339 (Div. 1)] - C Necklace
洛谷传送门Codeforces传送门题目大意你有一个n(n≤26)n(n\le 26)n(n≤26)种颜色的珠子， 现在你想要将它们串成手链， 手链的美观度定义为从某个位置切开后， 形成的颜色序列为回文串的方案数。 你要求出最大的可能的美观度。解题分析显然我们要构造尽量多的小回文串来构成大的回文串。如果有两个颜色的珠子数量都为奇数， 显然无解。如果有一种颜色的珠子数量为奇数， 那么方...
2019-03-14 20:21:30
173
原创 [Educational Codeforces Round 4] - E Square Root of Permutation
洛谷传送门Codeforces传送门题目大意给定一个nnn的排列pip_ipi， 求一个排列qiq_iqi， 满足对于∀i∈[1,n]\forall i\in[1,n]∀i∈[1,n]， qqi=piq_{q_i}=p_iqqi=pi。解题分析神奇的规律题…先尝试着正着推， 从iii向pip_ipi连一条边， 会构成很多的环。然后我们发现， 如果设ki=ppik_i...
2019-03-14 20:05:44
204
原创 [Codeforces Round #335 (Div. 1)] - C Freelancer's Dreams
洛谷传送门Codeforces传送门题目大意给你nnn种工作， 第iii种每天能给你aia_iai点aaa值， bib_ibi点bbb值， 每种工作可以做任意时间， 求要达到ppp点aaa值和qqq点bbb值至少需要多少天。解题分析很明显， 把(ai,bi)(a_i,b_i)(ai,bi)放在图上， 我们每天可以得到的能力值一定在这些点形成的凸包里面， 于是二分答案就好了。代码...
2019-03-14 18:43:42
215
原创 [Luogu P4590] [BZOJ 5336] [TJOI2018]游园会
洛谷传送门BZOJ传送门题目描述小豆参加了NOI的游园会，会场上每完成一个项目就会获得一个奖章，奖章只会是N,O,IN, O, IN,O,I的字样。在会场。上他收集到了KKK个奖章组成的串。兑奖规则是奖章串和兑奖串的最长公共子序列长度为小豆最后奖励的等级。现在已知兑奖串长度为NNN，并且在兑奖串上不会出现连续三个奖章为NOINOINOI，即奖章中不会出现子串NOINOINOI。现在小豆想知道...
2019-03-07 23:10:56
216
原创 [Luogu P2305] [BZOJ 3672] [NOI2014]购票
洛谷传送门BZOJ传送门题目描述今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国 nnn 个城市的OIer们都会从各地出发，到SZ市参加这次盛会。全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 nnn 个城市用 111 到 nnn 的整数编号。其中SZ市的编号为 111。对于除SZ市之外的任意一个城市 vvv，我们给出了它在这棵树...
2019-03-07 16:52:27
237
原创 [Luogu P3571] [BZOJ 3835] [POI2014]SUP-Supercomputer
洛谷传送门BZOJ传送门题目描述给定一棵NNN个节点的有根树，根节点为111。QQQ次询问，每次给定一个KKK，用最少的操作次数遍历完整棵树，输出最少操作次数。每次操作可以选择访问不超过KKK个未访问的点，且这些点的父亲必须在之前被访问过。输入输出格式输入格式第一行两个正整数N,QN, QN,Q。第二行QQQ个正整数， 分别表示每组询问中的KKK。第三行N−1N-1N−1个正整数，...
2019-03-07 14:22:58
223
原创 [AT2149] [ARC063 F] Snuke's Coloring 2
洛谷传送门Atcoder传送门题目描述在二维笛卡尔平面上， 有一个左下角为(0,0)(0,0)(0,0)， 右上角为(W,H)(W,H)(W,H)， 边平行于x、yx、yx、y轴， 初始为白色的矩形， 其中有NNN个节点。对于每个节点(xi,yi)(x_i,y_i)(xi,yi)， 你需要作出一个选择：将x≤xix\le x_ix≤xi部分的平面涂黑。将x≥xix\...
2019-03-07 11:07:38
276
原创 [AT2389] [AGC016 E] Poor Turkeys
洛谷传送门Atcoder传送门题目大意有N(2≤N≤400)N(2\le N\le 400)N(2≤N≤400)只火鸡, 编号为111 到NNN , 有M(1≤M≤105)M(1\le M\le 10^5)M(1≤M≤105) 个人, 每人指定了两只火鸡xxx 和yyy .到第iii个人选择的时候：若xxx 和yyy 都活着, 那么这个人将会等概率地随机吃掉一只若xxx 和yyy 恰...
2019-03-06 23:01:50
329
原创 [AT2383] [AGC015 E] Mr.Aoki Incubator
洛谷传送门Atcoder传送门题目大意数轴上有NNN个点，每个点初始时在位置XiX_iXi，以ViV_iVi的速度向数轴正方向前进初始时刻，你可以选择一些点为其染色，之后的行走过程中，染色的点会将其碰到的所有点都染上色，之后被染上色的点亦是如此在所有2N2^N2N种初始染色方案中，问有多少种初始染色方案，能使得最终所有的点都被染色？答案对109+710^9+7109+7取模输入输出...
2019-03-02 11:06:51
189
原创 [AT2401] [ARC072 E] Alice in linear land
洛谷传送门Atcoder传送门题目大意一开始你距离目的地有DDD的距离。 你有一个长度为NNN的数列AAA，设在第iii次操作时你在pip_ipi， 若∣pi−Ai∣&lt;pi|p_i-A_i|&lt;p_i∣pi−Ai∣<pi， 你就会移动到∣pi−Ai∣|p_i-A_i|∣pi−Ai∣去， 否则原地不动。现在有QQQ次询问， 每次询问你如果修改Aqi...
2019-03-02 10:50:38
161
原创 [AT1982] [AGC001 D] Arrays and Palindrome
洛谷传送门Atcoder传送门题目大意给你一个所有元素为正整数且和为NNN，长度为MMM的序列AAA， 要你求出AAA的一个排列A′A&#x27;A′和一个所有元素为正整数且和为NNN的序列BBB， 满足符合前A1′A&#x27;_1A1′个字符， 之后的A2′A&#x27;_2A2′个字符…组成的都是回文串，前B1B_1B1个字符， 之后的B2B_2B2个字...
2019-03-02 10:09:26
215
原创 [Luogu P3249] [BZOJ 4541] [LOJ #2052] [HNOI2016]矿区
洛谷传送门BZOJ传送门LOJ传送门题目描述平面上的矿区划分成了若干个开发区域。简单地说，你可以将矿区看成一张连通的平面图，平面图划分为了若干平面块，每个平面块即为一个开发区域，平面块之间的边界必定由若干整点(坐标值为整数的点)和连接这些整点的线段组成。每个开发区域的矿量与该开发区域的面积有关：具体而言，面积为sss的开发区域的矿量为 s2s^2s2。现在有 mmm 个...
2019-02-27 22:41:51
165
原创 [Codeforces Round #395 (Div. 1)] - E Timofey and our friends animals
洛谷传送门Codeforces传送门题目大意给你一个nnn个点mmm条边的无向图， 任意一条边ai→bia_i\to b_iai→bi满足∣ai−bi∣≤k|a_i-b_i|\le k∣ai−bi∣≤k，给出qqq组询问， 每次询问[l,r][l,r][l,r]内节点构成的子图的连通块个数。输入输出格式输入格式第一行三个正整数n,m,kn,m,kn,m,k。以下mmm行， 每...
2019-02-27 07:46:06
165
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人