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

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

@krydom3月前

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)

@krydom5月前

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]成绩单

@krydom5月前

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] 两双手

@krydom5月前

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] 上学路线

@krydom5月前

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

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

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

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

Read More →

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

@krydom7月前

04/5
14:50
一般动规与递推

[bzoj 4806] 炮

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

众所周知,双炮叠叠将是中国象棋中很厉害的一招必杀技。炮吃子时必须隔一个棋子跳吃,即俗称"炮打隔子"。
炮跟炮显然不能在一起打起来,于是rly一天借来了许多许多的炮在棋盘上摆了起来……他想知道,在N×M的矩形方格中摆若干炮(可以不摆)使其互不吃到的情况下方案数有几种。棋子都是相同的。

Read More →

[bzoj 4806] 炮

@krydom10月前

12/24
12:42
一般动规与递推

[bzoj 4282] 慎二的随机数列

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

间桐慎二是间桐家著名的废柴,有一天,他在学校随机了一组随机数列, 准备使用他那强大的人工智能求出其最长上升子序列,但是天有不测风云,人有旦夕祸福,柳洞一成路过时把间桐慎二的水杯打翻了……
现在给你一个长度为 n 的整数序列,其中有一些数已经模糊不清了,现在请你任意确定这些整数的值,使得最长上升子序列最长(为何最长呢?因为间桐慎二向来对自己的人品很有信心)。

Read More →

[bzoj 4282] 慎二的随机数列

@krydom11月前

12/7
18:24
一般动规与递推

[bzoj 3892] [Usaco2014 Dec]Marathon

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

Unhappy with the poor health of his cows, Farmer John enrolls them in an assortment of different physical fitness activities. His prize cow Bessie is enrolled in a running class, where she is eventually expected to run a marathon through the downtown area of the city near Farmer John's farm! The marathon course consists of N checkpoints (3 <= N <= 500) to be visited in sequence, where checkpoint 1 is the starting location and checkpoint N is the finish. Bessie is supposed to visit all of these checkpoints one by one, but being the lazy cow she is, she decides that she will skip up to K checkpoints (K < N) in order to shorten her total journey. She cannot skip checkpoints 1 or N, however, since that would be too noticeable. Please help Bessie find the minimum distance that she has to run if she can skip up to K checkpoints. Since the course is set in a downtown area with a grid of streets, the distance between two checkpoints at locations (x1, y1) and (x2, y2) is given by |x1-x2| + |y1-y2|.

在二维平面上有N个点,从(x1,y1)到(x2,y2)的代价为|x1-x2|+|y1-y2|。
求从1号点出发,按从1到N的顺序依次到达每个点的最小总代价。
你有K次机会可以跳过某个点,不允许跳过1号点或N号点。

Read More →

[bzoj 3892] [Usaco2014 Dec]Marathon