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/20
16:12
上下界网络流

[bzoj 3698] XWW的难题

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

XWW是个影响力很大的人,他有很多的追随者。这些追随者都想要加入XWW教成为XWW的教徒。但是这并不容易,需要通过XWW的考核。
XWW给你出了这么一个难题:XWW给你一个N*N的正实数矩阵A,满足XWW性。
称一个N*N的矩阵满足XWW性当且仅当:(1)A[N][N]=0;(2)矩阵中每行的最后一个元素等于该行前N-1个数的和;(3)矩阵中每列的最后一个元素等于该列前N-1个数的和。
现在你要给A中的数进行取整操作(可以是上取整或者下取整),使得最后的A矩阵仍然满足XWW性。同时XWW还要求A中的元素之和尽量大。

Read More →

[bzoj 3698] XWW的难题

@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/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]补退选

@krydom5月前

05/17
22:37
kmp

[bzoj 3620] 似乎在梦中见过的样子

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

“Madoka,不要相信 QB!”伴随着 Homura 的失望地喊叫,Madoka 与 QB 签订了契约.
这是 Modoka 的一个噩梦,也同时是上个轮回中所发生的事.为了使这一次 Madoka 不再与 QB签订契约,Homura 决定在刚到学校的第一天就解决 QB.然而,QB 也是有许多替身的(但在第八话中的剧情显示它也有可能是无限重生的),不过,意志坚定的 Homura 是不会放弃的——她决定
消灭所有可能是 QB 的东西.现在,她已感受到附近的状态,并且把它转化为一个长度为 n 的字符串交给了学 OI 的你.
现在你从她的话中知道 , 所有形似于 A+B+A 的字串都是 QB 或它的替身 , 且len(A)>=k,len(B)>=1 (位置不同其他性质相同的子串算不同子串,位置相同但拆分不同的子串算同一子串),然后你必须尽快告诉 Homura 这个答案——QB 以及它的替身的数量.

Read More →

[bzoj 3620] 似乎在梦中见过的样子

@krydom5月前

05/17
22:33
树链剖分 线段树

[bzoj 2819] Nim

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

 著名游戏设计师vfleaking,最近迷上了Nim。普通的Nim游戏为:两个人进行游戏,N堆石子,每回合可以取其中某一堆的任意多个,可以取完,但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。
为了设计漂亮一点的初始局面,vfleaking用以下方式来找灵感:拿出很多石子,把它们聚成一堆一堆的,对每一堆编号1,2,3,4,...n,在堆与堆间连边,没有自环与重边,从任意堆到任意堆都只有唯一一条路径可到达。然后他不停地进行如下操作:

1.随机选两个堆v,u,询问若在v到u间的路径上的石子堆中玩Nim游戏,是否有必胜策略,如果有,vfleaking将会考虑将这些石子堆作为初始局面之一,用来坑玩家。
2.把堆v中的石子数变为k。

由于vfleaking太懒了,他懒得自己动手了。请写个程序帮帮他吧。

Read More →

[bzoj 2819] Nim

@krydom5月前

05/17
22:30
搜索

[bzoj 1024] [SCOI2009]生日快乐

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

 windy的生日到了,为了庆祝生日,他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy,一共有 N 个人来分这块大蛋糕,要求每个人必须获得相同面积的蛋糕。windy主刀,每一切只能平行于一块蛋糕的一边(任意一边),并且必须把这块蛋糕切成两块。这样,要切成 N 块蛋糕,windy必须切 N-1 次。为了使得每块蛋糕看起来漂亮,我们要求 N块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么?

Read More →

[bzoj 1024] [SCOI2009]生日快乐