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

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

@krydom10月前

09/11
14:33
树链剖分 线段树

[bzoj 4448] [Scoi2015]情报传递

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

奈特公司是一个巨大的情报公司,它有着庞大的情报网络。情报网络中共有n名情报员。每名情报员口J-能有若T名(可能没有)下线,除1名大头日外其余n-1名情报员有且仅有1名上线。奈特公司纪律森严,每名情报员只能与自己的上、下线联系,同时,情报网络中仟意两名情报员一定能够通过情报网络传递情报。
奈特公司每天会派发以下两种任务中的一个任务:
1.搜集情报:指派T号情报员搜集情报
2.传递情报:将一条情报从X号情报员传递给Y号情报员
情报员最初处于潜伏阶段,他们是相对安全的,我们认为此时所有情报员的危险值为0;-旦某个情报员开始搜集情报,他的危险值就会持续增加,每天增加1点危险值(开始搜集情报的当天危险值仍为0,第2天危险值为1,第3天危险值为2,以此类推)。传递情报并不会使情报员的危险值增加。为了保证传递情报的过程相对安全,每条情报都有一个风险控制值C。余特公司认为,参与传递这条情报的所有情报员中,危险值大于C的情报员将对该条情报构成威胁。现在,奈特公司希望知道,对于每个传递情报任务,参与传递的情报员有多少个,其中对该条情报构成威胁的情报员有多少个。

Read More →

[bzoj 4448] [Scoi2015]情报传递

@krydom10月前

09/11
12:51
线段树

[bzoj 4499] 线性函数

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

小C最近在学习线性函数,线性函数可以表示为:f(x) = kx + b。现在小C面前有n个线性函数fi(x)=kix+bi ,他对这n个线性函数执行m次操作,每次可以:
1.M i K B 代表把第i个线性函数改为:fi(x)=kx+b 。
2.Q l r x 返回fr(fr-1(...fl(x)))  mod  10^9+7 。

Read More →

[bzoj 4499] 线性函数

@krydom11月前

08/8
15:30
线段树

[bzoj 3038] 上帝造题的七分钟2

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

 XLk觉得《上帝造题的七分钟》不太过瘾,于是有了第二部。
"第一分钟,X说,要有数列,于是便给定了一个正整数数列。
第二分钟,L说,要能修改,于是便有了对一段数中每个数都开平方(下取整)的操作。
第三分钟,k说,要能查询,于是便有了求一段数的和的操作。
第四分钟,彩虹喵说,要是noip难度,于是便有了数据范围。
第五分钟,诗人说,要有韵律,于是便有了时间限制和内存限制。
第六分钟,和雪说,要省点事,于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。
第七分钟,这道题终于造完了,然而,造题的神牛们再也不想写这道题的程序了。"
——《上帝造题的七分钟·第二部》
所以这个神圣的任务就交给你了。

Read More →

[bzoj 3038] 上帝造题的七分钟2

@krydom11月前

08/8
14:53
线段树

[bzoj 2957] 楼房重建

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

         小A的楼房外有一大片施工工地,工地上有N栋待建的楼房。每天,这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆,数自己能够看到多少栋房子。
为了简化问题,我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置,第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示,其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交,那么这栋楼房就被认为是可见的。
施工队的建造总共进行了M天。初始时,所有楼房都还没有开始建造,它们的高度均为0。在第i天,建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大---修建,也可以比原来小---拆除,甚至可以保持不变---建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后,他能看到多少栋楼房?

Read More →

[bzoj 2957] 楼房重建

@krydom11月前

08/2
09:52
线段树

[bzoj 4653] [Noi2016]区间

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

在数轴上有 个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间,使得这 m 个区间共同包含至少一个位置。换句话说,就是使得存在一个 x,使得对于每一个被选中的区间 [li,ri],都有 lixr

对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 rili,即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案,输出 1

Read More →

[bzoj 4653] [Noi2016]区间

@krydom11月前

07/17
15:35
线段树

[bzoj 3878] [Ahoi2014]奇怪的计算器

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

【故事背景】

JYY有个奇怪的计算器,有一天这个计算器坏了,JYY希望你能帮助他写一个程序来模拟这个计算器的运算。
【问题描述】
JYY的计算器可以执行N条预设好的指令。每次JYY向计算器输入一个正整数X,计算器就会以X作为初始值,接着依次执行预设的N条指令,最后把最终得出的结果返回给JYY。
每一条指令可以是以下四种指令之一:(这里a表示一个正整数。)
1、+a:表示将当前的结果加上a;
2、-a:表示将当前的结果减去a;
3、*a:表示将当前的结果乘以a;
4、@a:表示将当前的结果加上a*X(X是一开始JYY输入的数)。
计算器用于记录运算结果的变量的存储范围是有限的,所以每次运算结束之后会有计算结果溢出的问题。
JYY的计算器中,存储每计算结果的变量只能存储L到R之间的正整数,如果一次指令执行过后,计算结果超过了R,那么计算器就会自动把结果变成R,然后再以R作为当前结果继续进行之后的计算。同理,如果运算结果小于L,计算器也会把结果变成L,再接着计算。
比如,假设计算器可以存储1到6之间的值,如果当前的计算结果是2,那么在执行+5操作之后,存储结果的变量中的值将会是6。虽然2+5的实际结果是7,但是由于7超过了存储范围的上界,所以结果就被自动更正成了上界的大小,也就是6。
JYY一共想在计算器上输入Q个值,他想知道这Q个值输入计算器之后,分别会得到什么结果呢?

Read More →

[bzoj 3878] [Ahoi2014]奇怪的计算器

@krydom11月前

07/17
12:13
线段树

[bzoj 3526] [Poi2014]Card

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

 有n张卡片在桌上一字排开,每张卡片上有两个数,第i张卡片上,正面的数为a[i],反面的数为b[i]。现在,有m个熊孩子来破坏你的卡片了!
第i个熊孩子会交换c[i]和d[i]两个位置上的卡片。
每个熊孩子捣乱后,你都需要判断,通过任意翻转卡片(把正面变为反面或把反面变成正面,但不能改变卡片的位置),能否让卡片正面上的数从左到右单调不降。

Read More →

[bzoj 3526] [Poi2014]Card