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:21
二分法 可持久化trie

[bzoj 4896] [Thu Summer Camp2016]补退选

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

X是T大的一名老师,每年他都要教授许多学生基础的C++知识。在T大,每个学生在每学期的开学前都需要选课,每次选课一共分为三个阶段:预选,正选,补退选;其中"补退选"阶段最忙碌。在补退选阶段,学生即可以选课,也可以退课。对于X老师来说,在补退选阶段可能发生以下两种事件:
1:一个姓名为S的学生选了他的课(姓名S将出现在X的已选课学生名单中)
2:一个姓名为S的学生退了他的课(姓名S将从X的已选课学生名单中移除)
同时,X老师对于有哪些学生选了他的课非常关心,所以他会不定时的查询已选课学生名单,每次查询的格式如下:最早在哪个事件之后,姓名以S为前缀的学生数量超过了vX老师看你骨骼惊奇,所以想用这个问题考考你,你当然不会畏惧,所以勇敢的接下了这个任务。
注意1:学生的姓名可能相同,如果有p个姓名相同的学生都选了X老师的课,则他们的姓名将出现在X老师的名单上p次。
注意2:只有已经选了课的学生才会退课,如果姓名为S的学生退课,则在他退课之前X老师的名单上一定有姓名S。
注意3:选课,退课和查询都被定义为"事件","事件"的编号从1开始

Read More →

[bzoj 4896] [Thu Summer Camp2016]补退选

@krydom6月前

04/19
21:26
spfa 乱搞 暴力 离线

[czyz 2017.04.16 noip- 模拟赛]

A:http://czyzuoj.com/problem/77

B:http://czyzuoj.com/problem/78

C:http://czyzuoj.com/problem/79

 

A:

【防AK好题(???)(雾)】

假·在线,从前往后做应该是不能做的....

因为最后一行解密出来是0,0,0,所以我们先可以直接知道最后一个询问的答案

然后发现如果已经知道了第i个询问的答案,求解第i-1个询问的答案只要接一个一元一次方程就可以了... Read More →

[czyz 2017.04.16 noip- 模拟赛]

@krydom7月前

04/5
15:16
组合数/lucas 高精度

[bzoj 4807] 車

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

众所周知,車是中国象棋中最厉害的一子之一,它能吃到同一行或同一列中的其他棋子。車跟車显然不能在一起打起来,于是rly一天又借来了许多许多的車在棋盘上摆了起来……他想知道,在N×M的矩形方格中摆最多个数的車使其互不吃到的情况下方案数有几种。但是,由于上次摆炮摆得实在太累,他为了偷懒,打算增加一个条件:对于任何一个車A,如果有其他一个車B在它的上面(車B行号小于車A),那么車A必须在車B的右边(車A列号大于車B)。
棋子都是相同的。

Read More →

[bzoj 4807] 車

@krydom10月前

01/1
21:42
基础算法

[bzoj 4723] [POI2017]Flappy Bird

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

《飞扬的小鸟》是一款风靡的小游戏。在游戏中,小鸟一开始位于(0,0)处,它的目标是飞到横坐标为X的某个位置上。每一秒,你可以选择点击屏幕,那么小鸟会从(x,y)飞到(x+1,y+1),或者不点击,那么小鸟会飞到(x+1,y-1)。在游戏中还有n个障碍物,用三元组(x[i],a[i],b[i])描述,表示在直线x=x[i]上,y<=a[i]或者y>=b[i]的部分都是障碍物,碰到或者擦边都算游戏失败。请求出小鸟从(0,0)飞到目的地最少需要点击多少次屏幕。

Read More →

[bzoj 4723] [POI2017]Flappy Bird

@krydom10月前

12/17
16:47
贪心

[bzoj 4619] [Wf2016]Swap Space

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

你有许多电脑,它们的硬盘用不同的文件系统储存数据。你想要通过格式化来统一文件系统。格式化硬盘可能使它的容量发生变化。为了格式化,你需要买额外的硬盘。当然,你想要买容量最小的额外储存设备以便省钱。你可以按任意顺序格式化硬盘。格式化之前,你要把该硬盘上所有数据移到一个或更多的其他硬盘上(可以分割数据)。格式化后,该硬盘可以立刻开始使用。你没有必要把数据放到它原来所在的硬盘上。数据也可以被放到你额外买的硬盘上。举个例子,假设你有4个硬盘A、B、C、D,容量分别为6、1、3、3(GB)。新的文件系统下,它们的容量变为6、7、5、5(GB)。如果你只买1GB额外空间,你可以把B硬盘的数据放过去然后格式化硬盘B。现在你的B硬盘有7GB容量了,那么你就可以把A的数据放过去然后格式化A,最后把C、D的数据放到A上,再格式化C和D。

Read More →

[bzoj 4619] [Wf2016]Swap Space