Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom4月前

08/2
13:33
一般动规与递推 构造 贪心

Codeforces Round #427 (Div. 2)

A. Key races

prob:

总共要打 s 个字

第一个人打一个字需要 v1 ms,网络延迟 t1 ms

第二个人打一个字需要 v2 ms,网络延迟 t2 ms

发题和交题各有两次网络延迟,问哪个人快

sol:

time = v * s + 2 * t

 

B. The number on the board

prob:

给出一个长度为 n 的数,要求改变一些数字,是的各位数字和大于等于 k,要求变的数字尽量少

k \le 10^9,n \le 10^6

sol:

从0到8依次变

 

C. Star sky

prob:

给出一个长宽不大于 100 的矩形,上面有 n 颗星星,每颗星星一开始的亮度是 s_i

每过去一秒,亮度为 x 的星星亮度会变成 x % (c + 1)

给出 q 个询问,每次询问 t,x_1,y_1,x_2,y_2 询问 t 秒后这个矩形之内的星星亮度和是多少

n, q \le 10^5, c \le 10, t \le 10^9

sol:

对于每种亮度的星星维护一个二维前缀和,询问的时候枚举每种亮度,算出最后变成了哪个亮度和矩形内有多少个,乘起来

 

D. Palindromic characteristics

prob:

给出一个长度为 s (s \le 5000) 的字符串,问 i1 \sim si- 回文子串一共有多少个

1. 如果一个字符串是回文串,它就是 1- 回文串

2. 如果一个字符串左右对称(是回文串),设它的左半边是 k- 回文串,它就是 k+1- 回文串

sol:

f[i][j] 表示 [i,j] 这个子串最多是多少回文串

如果 f[i+1][j-1] != 0s[i]=s[j] 那么它就是一个回文串,直接计算即可

注意到如果一个字符串是 k- 回文串,那么它肯定也是 1 \sim k- 回文串

统计一下每种回文串有多少个,做一个后缀和就可以了

 

E. The penguin's game

prob:

这是一道交互题

给出一个长度为 n 的序列,其中有且仅有 2 个位置是 y ,其他位置都是x

你可以给出不超过 19 个询问,每次询问可以选择 1 \ sim n 的一个子集,交互库会给出这些位置数字的异或和

最后让你求出是 y 的位置

n \le 1000, x \not = y, 1 \le x,y \le 10^9

sol:

考虑一下几种情况:

1. 询问偶数个数,给出的答案是 0 (这些位置特殊位置的数量是偶数)

2. 询问偶数个数,给出的答案是 x \hat{} y (这些位置特殊位置的数量是奇数)

3. 询问奇数个数,给出的答案是 x (这些位置特殊位置的数量是偶数)

4. 询问奇数个数,给出的答案是 y (这些位置特殊位置的数量是奇数)

所以,我们可以用一次询问得知任意子集特殊位置的奇偶性

总共只有 1000 个数,所以每个位置的二进制只有 10 位,用 10 次询问枚举这些位置,询问当前二进制为 1 的所有数,这样我们就可以得知两个特殊位置那些二进制位不一样

我们从中选取一个不一样的位置,那么就把 n 个数分成了 2 个集合,每个集合不超过 500 个数

我们在 500 个数中用二分查找出一个特殊位置的位置,只需要 9

由于我们已经知道了另外一个位置和这个位置的那些二进制位不一样,可以直接求另外一个位置,总共需要 19 次询问

 

F. Roads in the Kingdom

prob:

给出一个 n 个点的环套树,让你在环上删去一个点,使得剩下的树的直径最小

n \le 2 \ times 10^5

sol:

先找到这个环套树的环,假设环上有 k个点,然后需要预处理出这些东西:

d_i 环上第 i 个点挂着的树的最深深度

w_i 环上第 i 个点到顺势针下一个点的长度

prefdiam_i 环上第 1 个点到第 i 个点挂着的树中,离得最远的距离

(不考虑同一颗树内的情况,毕竟删了任意一条边也不能改变这些东西,下同)

suffdiam_i 环上第 i 个点到第 k 个点挂着的树中,离得最远的距离

preffar_i 环上第 1 个点到第 i 个点挂着的树中,距离环上第 1 个点最远的距离

sufffar_i 环上第 i 个点到第 k 个点挂着的树中,距离环上第 1 个点最远的距离

同时,我们可以规定 sufffar_i = suffdiam_i = -inf

这些东西都是可以 O(n) 预处理的

我们考虑删去环上第 i 个点到它下一个点之间的那一条边,经过环的最远距离就是max(preffar[i]+sufffar[i+1],prefdiam[i],suffdiam[i+1]) ,枚举每条边,删去这个最远距离最小的边

删边之后用 2dfs 求出剩下树的直径就是答案

Codeforces Round #427 (Div. 2)

@krydom7月前

05/19
21:29
一般动规与递推

[bzoj 4897] [Thu Summer Camp2016]成绩单

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

期末考试结束了,班主任L老师要将成绩单分发到每位同学手中。L老师共有n份成绩单,按照编号从1到n的顺序叠放在桌子上,其中编号为i的成绩单分数为w_i。成绩单是按照批次发放的。发放成绩单时,L老师会从当前的一叠成绩单中抽取连续的一段,让这些同学来领取自己的成绩单。当这批同学领取完毕后,L老师再从剩余的成绩单中抽取连续的一段,供下一批同学领取。经过若干批次的领取后,成绩单将被全部发放到同学手中。然而,分发成绩单是一件令人头痛的事情,一方面要照顾同学们的心理情绪,不能让分数相差太远的同学在同一批领取成绩单;另一方面要考虑时间成本,尽量减少领取成绩单的批次数。对于一个分发成绩单的方案,我们定义其代价为:
其中,k是方案中分发成绩单的批次数,对于第i批分发的成绩单,〖max〗_i是最高分数,〖min〗_i是最低分数。a,b是给定的评估参数。现在,请你帮助L老师找到代价最小的分发成绩单的方案,并将这个最小的代价告诉L老师。当然,分发成绩单的批次数k是由你决定的。

Read More →

[bzoj 4897] [Thu Summer Camp2016]成绩单

@krydom7月前

05/17
20:58
一般动规与递推 容斥原理 数学其他 组合数/lucas

[bzoj 4767] 两双手

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

老W是个棋艺高超的棋手,他最喜欢的棋子是马,更具体地,他更加喜欢马所行走的方式。老W下棋时觉得无聊,便决定加强马所行走的方式,更具体地,他有两双手,其中一双手能让马从(u,v)移动到(u+Ax,v+Ay)而另一双手能让马从(u,v)移动到(u+Bx,v+By)。小W看见老W的下棋方式,觉得非常有趣,他开始思考一个问题:假设棋盘是个无限大的二维平面,一开始马在原点(0,0)上,若用老W的两种方式进行移动,他有多少种不同的移动方法到达点(Ex,Ey)呢?两种移动方法不同当且仅当移动步数不同或某一步所到达的点不同。老W听了这个问题,觉得还不够有趣,他在平面上又设立了n个禁止点,表示马不能走到这些点上,现在他们想知道,这种情况下马有多少种不同的移动方法呢?答案数可能很大,你只要告诉他们答案模(10^9+7)的值就行。

Read More →

[bzoj 4767] 两双手

@krydom7月前

05/17
20:54
一般动规与递推 中国剩余定理 容斥原理 组合数/lucas

[bzoj 3782] 上学路线

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 小C所在的城市的道路构成了一个方形网格,它的西南角为(0,0),东北角为(N,M)。小C家住在西南角,学校在东北角。现在有T个路口进行施工,小C不能通过这些路口。小C喜欢走最短的路径到达目的地,因此他每天上学时都只会向东或北行走;而小C又喜欢走不同的路径,因此他问你按照他走最短路径的规则,他可以选择的不同的上学路线有多少条。由于答案可能很大,所以小C只需要让你求出路径数mod P的值。

Read More →

[bzoj 3782] 上学路线

@krydom7月前

05/17
20:35
一般动规与递推

[bzoj 4884] [Lydsy2017年5月月赛]太空猫

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

太空猫(SpaceCat)是一款画面精致、玩法有趣的休闲游戏,你需要控制一只坐在迷你飞碟上的猫咪在太空里不断探索,让大家看看你能飞得多远。游戏地图可以看成一个二维的网格图,上下是两段障碍物。在游戏的一开始,太空猫位于地图最左边的下边界之上,且重力方向向下。
在每个时刻,你可以用手指点击屏幕,翻转重力的方向,或者通过遥感控制太空猫往左或往右移动。每次翻转重力方向时,你需要消耗的能量值等于上下底边之间的高度差。在左右移动的时候,太空猫可以下降到对应重力方向更低的位置,但不能往上爬。当然,太空猫也不能穿墙而过。在重力翻转的过程中,直到碰到地面之前,你都不能操控太空猫左右移动。太空猫的终点位于地图的最右端的下底边之上,请计算为了让太空猫到达终点,需要消耗能量的最小值。

Read More →

[bzoj 4884] [Lydsy2017年5月月赛]太空猫

@krydom7月前

05/17
20:07
树形动规

[bzoj 4813] [Cqoi2017]小Q的棋盘

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

小Q正在设计一种棋类游戏。在小Q设计的游戏中,棋子可以放在棋盘上的格点中。某些格点之间有连线,棋子只能在有连线的格点之间移动。整个棋盘上共有V个格点,编号为0,1,2…,V-1,它们是连通的,也就是说棋子从任意格点出发,总能到达所有的格点。小Q在设计棋盘时,还保证棋子从一个格点移动到另外任一格点的路径是唯一的。小Q现在想知道,当棋子从格点0出发,移动N步最多能经过多少格点。格点可以重复经过多次,但不重复计数。

Read More →

[bzoj 4813] [Cqoi2017]小Q的棋盘

@krydom8月前

04/8
19:45
斜率优化

[bzoj1010] [HNOI2008]玩具装箱toy

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具,第i件玩具经过压缩后变成一维长度为Ci.为了方便整理,P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物,形式地说如果将第i件玩具到第j个玩具放到一个容器中,那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过L。但他希望费用最小.

Read More →

[bzoj1010] [HNOI2008]玩具装箱toy