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

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

@krydom1月前

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

@krydom7月前

12/6
20:30
二分法

[bzoj 1196] [HNOI2006]公路修建问题

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

 OI island是一个非常漂亮的岛屿,自开发以来,到这儿来旅游的人很多。然而,由于该岛屿刚刚开发不久,所以那里的交通情况还是很糟糕。所以,OIER Association组织成立了,旨在建立OI island的交通系统。 OI island有n个旅游景点,不妨将它们从1到n标号。现在,OIER Association需要修公路将这些景点连接起来。一条公路连接两个景点。公路有,不妨称它们为一级公路和二级公路。一级公路上的车速快,但是修路的花费要大一些。 OIER Association打算修n-1条公路将这些景点连接起来(使得任意两个景点之间都会有一条路径)。为了保证公路系统的效率, OIER Association希望在这n-1条公路之中,至少有k条(0≤k≤n-1)一级公路。OIER Association也不希望为一条公路花费的钱。所以,他们希望在满足上述条件的情况下,花费最多的一条公路的花费尽可能的少。而你的任务就是,在给定一些可能修建的公路的情况下,选择n-1条公路,满足上面的条件。

Read More →

[bzoj 1196] [HNOI2006]公路修建问题

@krydom9月前

10/15
16:09
二分法 分块

[bzoj 3343] 教主的魔法

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

教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1、2、……、N
每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R](1≤LRN)内的英雄的身高全部加上一个整数W。(虽然L=R时并不符合区间的书写规范,但我们可以认为是单独增加第LR)个英雄的身高)
CYZ、光哥和ZJQ等人不信教主的邪,于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C,以验证教主的魔法是否真的有效。
WD巨懒,于是他把这个回答的任务交给了你。

Read More →

[bzoj 3343] 教主的魔法

@krydom11月前

08/5
17:38
二分法 分块

[bzoj 2453] 维护队列

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

你小时候玩过弹珠吗?
小朋友A有一些弹珠,A喜欢把它们排成队列,从左到右编号为1到N。为了整个队列鲜艳美观,小朋友想知道某一段连续弹珠中,不同颜色的弹珠有多少。当然,A有时候会依据个人喜好,替换队列中某个弹珠的颜色。但是A还没有学过编程,且觉得头脑风暴太浪费脑力了,所以向你来寻求帮助。

Read More →

[bzoj 2453] 维护队列

@krydom12月前

07/14
09:13
二分法

[bzoj 4590] [Shoi2015]自动刷题机

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

曾经发明了信号增幅仪的发明家SHTSC又公开了他的新发明:自动刷题机--一种可以自动AC题目的神秘装置。自动刷题机刷题的方式非常简单:首先会瞬间得出题目的正确做法,然后开始写程序,每秒,自动刷题机的代码生成模块会有两种可能的结果:
A.写了x行代码。
B.心情不好,删掉了之前写的y行代码。(如果y大于当前代码长度则相当于全部删除。)
对于每个OJ所有题目,存在某个固定的长度n>0。一旦自动刷题机在某秒结束时积累了大于等于n行的代码,它就会自动提交并AC此题,然后新建一个文件开始写下一题。SHTSC在某个OJ上跑了一天的自动刷题机,得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个OJ的n究竟是多少。所幸他通过自己在OJ上的Rank知道了机一共切了k道题。希望你计算n可能的最小值和最大值。

Read More →

[bzoj 4590] [Shoi2015]自动刷题机