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)

@krydom8月前

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

@krydom1年前

08/7
12:32
贪心

[bzoj 2802] [Poi2012]Warehouse Store

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

 有一家专卖一种商品的店,考虑连续的n天。
第i天上午会进货Ai件商品,中午的时候会有顾客需要购买Bi件商品,可以选择满足顾客的要求,或是无视掉他。
如果要满足顾客的需求,就必须要有足够的库存。问最多能够满足多少个顾客的需求。

Read More →

[bzoj 2802] [Poi2012]Warehouse Store

@krydom1年前

08/5
22:56
贪心

[bzoj 2697] 特技飞行

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

 神犇航空开展了一项载客特技飞行业务。每次飞行长N个单位时间,每个单位时间可以进行一项特技动作,可选的动作有K种,每种动作有一个刺激程度Ci。如果连续进行相同的动作,乘客会感到厌倦,所以定义某次动作的价值为(距上次该动作的时间)*Ci,若为第一次进行该动作,价值为0。安排一种方案,使得总价值最大。

Read More →

[bzoj 2697] 特技飞行

@krydom1年前

07/31
14:20
贪心

[bzoj 1029] [JSOI2007]建筑抢修

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

 小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏:经过了一场激烈的战斗,T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤,如果不尽快修复的话,这些建筑设施将会完全毁坏。现在的情况是:T部落基地里只有一个修理工人,虽然他能瞬间到达任何一个建筑,但是修复每个建筑都需要一定的时间。同时,修理工人修理完一个建筑才能修理下一个建筑,不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕,这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序,以抢修尽可能多的建筑。

Read More →

[bzoj 1029] [JSOI2007]建筑抢修

@krydom1年前

07/16
08:48
模拟 贪心

[bzoj 3709] [PA2014]Bohater

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

 在一款电脑游戏中,你需要打败n只怪物(从1到n编号)。为了打败第i只怪物,你需要消耗d[i]点生命值,但怪物死后会掉落血药,使你恢复a[i]点生命值。任何时候你的生命值都不能降到0(或0以下)。请问是否存在一种打怪顺序,使得你可以打完这n只怪物而不死掉

Read More →

[bzoj 3709] [PA2014]Bohater

@krydom1年前

07/15
08:41
STL 拓扑排序 贪心

[bzoj 4010] [HNOI2015]菜肴制作

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

知名美食家小 A被邀请至ATM 大酒店,为其品评菜肴。

ATM 酒店为小 A 准备了 N 道菜肴,酒店按照为菜肴预估的质量从高到低给予1到N的顺序编号,预估质量最高的菜肴编号为1。由于菜肴之间口味搭配的问题,某些菜肴必须在另一些菜肴之前制作,具体的,一共有 M 条形如“i 号菜肴‘必须’先于 j 号菜肴制作”的限制,我们将这样的限制简写为<i,j>。现在,酒店希望能求出一个最优的菜肴的制作顺序,使得小 A能尽量先吃到质量高的菜肴:也就是说,(1)在满足所有限制的前提下,1 号菜肴“尽量”优先制作;(2)在满足所有限制,1号菜肴“尽量”优先制作的前提下,2号菜肴“尽量”优先制作;(3)在满足所有限制,1号和2号菜肴“尽量”优先的前提下,3号菜肴“尽量”优先制作;(4)在满足所有限制,1 号和 2 号和 3 号菜肴“尽量”优先的前提下,4 号菜肴“尽量”优先制作;(5)以此类推。
例1:共4 道菜肴,两条限制<3,1>、<4,1>,那么制作顺序是 3,4,1,2。例2:共5道菜肴,两条限制<5,2>、 <4,3>,那么制作顺序是 1,5,2,4,3。例1里,首先考虑 1,因为有限制<3,1>和<4,1>,所以只有制作完 3 和 4 后才能制作 1,而根据(3),3 号又应“尽量”比 4 号优先,所以当前可确定前三道菜的制作顺序是 3,4,1;接下来考虑2,确定最终的制作顺序是 3,4,1,2。例 2里,首先制作 1是不违背限制的;接下来考虑 2 时有<5,2>的限制,所以接下来先制作 5 再制作 2;接下来考虑 3 时有<4,3>的限制,所以接下来先制作 4再制作 3,从而最终的顺序是 1,5,2,4,3。 现在你需要求出这个最优的菜肴制作顺序。无解输出“Impossible!” (不含引号,首字母大写,其余字母小写)

Read More →

[bzoj 4010] [HNOI2015]菜肴制作

@krydom1年前

06/14
16:43
贪心

[bzoj 1034] [ZJOI2008]泡泡堂BNB

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

 第XXXX届NOI期间,为了加强各省选手之间的交流,组委会决定组织一场省际电子竞技大赛,每一个省的代表队由n名选手组成,比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前,对阵双方的教练向组委会提交一份参赛选手的名单,决定了选手上场的顺序,一经确定,不得修改。比赛中,双方的一号选手,二号选手……,n号选手捉对厮杀,共进行n场比赛。每胜一场比赛得2分,平一场得1分,输一场不得分。最终将双方的单场得分相加得出总分,总分高的队伍晋级(总分相同抽签决定)。作为浙江队的领队,你已经在事先将各省所有选手的泡泡堂水平了解的一清二楚,并将其用一个实力值来衡量。为简化问题,我们假定选手在游戏中完全不受任何外界因素干扰,即实力强的选手一定可以战胜实力弱的选手,而两个实力相同的选手一定会战平。由于完全不知道对手会使用何种策略来确定出场顺序,所以所有的队伍都采取了这样一种策略,就是完全随机决定出场顺序。当然你不想这样不明不白的进行比赛。你想事先了解一下在最好与最坏的情况下,浙江队最终分别能得到多少分。

Read More →

[bzoj 1034] [ZJOI2008]泡泡堂BNB

@krydom1年前

03/18
19:19
manacher 一般动规与递推 字符串 贪心

神奇项链 [bzoj 3790]

00:00/00:00

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

母亲节就要到了,小 H 准备送给她一个特殊的项链。这个项链可以看作一个用小写字
母组成的字符串,每个小写字母表示一种颜色。为了制作这个项链,小 H 购买了两个机器。第一个机器可以生成所有形式的回文串,第二个机器可以把两个回文串连接起来,而且第二个机器还有一个特殊的性质:假如一个字符串的后缀和一个字符串的前缀是完全相同的,那么可以将这个重复部分重叠。例如:aba和aca连接起来,可以生成串abaaca或 abaca。现在给出目标项链的样式,询问你需要使用第二个机器多少次才能生成这个特殊的项链。

Read More →

神奇项链 [bzoj 3790]