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

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

@krydom10月前

12/24
21:39
期望动规 线性代数

[bzoj 3270] 博物馆

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

有一天Petya和他的朋友Vasya在进行他们众多旅行中的一次旅行,他们决定去参观一座城堡博物馆。这座博物馆有着特别的样式。它包含由m条走廊连接的n间房间,并且满足可以从任何一间房间到任何一间别的房间。
两个人在博物馆里逛了一会儿后两人决定分头行动,去看各自感兴趣的艺术品。他们约定在下午六点到一间房间会合。然而他们忘记了一件重要的事:他们并没有选好在哪儿碰面。等时间到六点,他们开始在博物馆里到处乱跑来找到对方(他们没法给对方打电话因为电话漫游费是很贵的)
不过,尽管他们到处乱跑,但他们还没有看完足够的艺术品,因此他们每个人采取如下的行动方法:每一分钟做决定往哪里走,有Pi 的概率在这分钟内不去其他地方(即呆在房间不动),有1-Pi 的概率他会在相邻的房间中等可能的选择一间并沿着走廊过去。这里的i指的是当期所在房间的序号。在古代建造是一件花费非常大的事,因此每条走廊会连接两个不同的房间,并且任意两个房间至多被一条走廊连接。
两个男孩同时行动。由于走廊很暗,两人不可能在走廊碰面,不过他们可以从走廊的两个方向通行。(此外,两个男孩可以同时地穿过同一条走廊却不会相遇)两个男孩按照上述方法行动直到他们碰面为止。更进一步地说,当两个人在某个时刻选择前往同一间房间,那么他们就会在那个房间相遇。
两个男孩现在分别处在a,b两个房间,求两人在每间房间相遇的概率。

Read More →

[bzoj 3270] 博物馆

@krydom10月前

12/24
12:42
一般动规与递推

[bzoj 4282] 慎二的随机数列

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

间桐慎二是间桐家著名的废柴,有一天,他在学校随机了一组随机数列, 准备使用他那强大的人工智能求出其最长上升子序列,但是天有不测风云,人有旦夕祸福,柳洞一成路过时把间桐慎二的水杯打翻了……
现在给你一个长度为 n 的整数序列,其中有一些数已经模糊不清了,现在请你任意确定这些整数的值,使得最长上升子序列最长(为何最长呢?因为间桐慎二向来对自己的人品很有信心)。

Read More →

[bzoj 4282] 慎二的随机数列

@krydom10月前

12/18
10:23
可持久化trie

[bzoj 3261] 最大异或和

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

给定一个非负整数序列 {a},初始长度为 N。
有   M个操作,有以下两种操作类型:
1 、A x:添加操作,表示在序列末尾添加一个数 x,序列的长度 N+1。
2 、Q l r x:询问操作,你需要找到一个位置 p,满足 l<=p<=r,使得:
a[p] xor a[p+1] xor ... xor a[N] xor x 最大,输出最大是多少。

Read More →

[bzoj 3261] 最大异或和

@krydom10月前

12/17
23:53
树链剖分 线段树

[bzoj 4538] [Hnoi2016]网络

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

 一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据的交互时,数据会经过连接这两个服务器的路径上的所有服务器(包括这两个服务器自身)。由于这条路径是唯一的,当路径上的某个服务器出现故障,无法正常运行时,数据便无法交互。此外,每个数据交互请求都有一个重要度,越重要的请求显然需要得到越高的优先处理权。现在,你作为一个网络系统的管理员,要监控整个系统的运行状态。系统的运行也是很简单的,在每一个时刻,只有可能出现下列三种事件中的一种:1.  在某两个服务器之间出现一条新的数据交互请求;2.  某个数据交互结束请求;3.  某个服务器出现故障。系统会在任何故障发生后立即修复。也就是在出现故障的时刻之后,这个服务器依然是正常的。但在服务器产生故障时依然会对需要经过该服务器的数据交互请求造成影响。你的任务是在每次出现故障时,维护未被影响的请求中重要度的最大值。注意,如果一个数据交互请求已经结束,则不将其纳入未被影响的请求范围。

Read More →

[bzoj 4538] [Hnoi2016]网络

@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

@krydom10月前

12/14
20:41
未分类

NOIP 2016 游记

闲来无事.... 写个游记玩玩

00:00/00:00

Day -7 ~ Day -1

好不容易可以停课了啊....众所周知,吾等弱校没有学长带我们玩.... 所以就只好我这种弱成渣的人再随便讲讲一些内容了,每天都是上午做题下午讲点东西,顺便每天抽出一点时间来颓一颓.....不过day-1的时候补下了一个今年wc上没做对的树链剖分的长达300天的远古巨坑而且1A了,还是提升了不少信心的。毕竟去年要不是爆空间就585了(雾),今年应该也差不多吧(不要插旗啊喂!)

Day 0

常州和南京还是算离得比较近的吧,所以中午才出发。上午就是和学长一起颓颓颓,而且有一件最为重要的事情.... 舰队collection要开秋活了!....(乙烷预定)上午走之前穿上了我的ak战袍(其实就是艾米莉亚碳的斗篷 国庆去魔都萤火虫漫展买的),还得到了退役的学长的祝福,披着它一路到了南京。中途大概有2个小时就是睡过去的。啊走之前还在我的mac上卸载了windows这个垃圾软件正式加入了mac os党,顺便加入了Sublime邪教。

话说今年住的宾馆和前两年的不一样了诶...(据说是因为之前的早饭发霉了...?)到了房间里立刻发现了一件非常可怕的事实——没网。其实是因为我们的房间位置特别不好离所有wifi点都特别远,只好去学长的房间避难。其实就是一边写题一边玩舰C,把E1甲通关了(萌新的第一个甲章),然后E2磨血的时候捞到了山风(掉rp的开始)。大概这么一天就过去了吧.... 对了房间的隔音特别不好,不过还是勉强能睡着。

Day 1

早上起来吃完了早饭,发现外面的雾特别大,能见度不超过5米... 听说某省已经开始下大雪了,南方人并不理解这种东西... 走到南航的时候和去年一样放了一首豪勇七蛟龙助兴,到了集合地点以后开始膜拜各路神犇,其实对今天的试题还是心有忐忑的.....

到机房试机.... 键盘烂得和什么一样.... 也许是因为我打惯了机械键盘的缘故吧... 不过并没有什么影响,于是就拍了几个模板....

T1果然还是送分题,不过讲道理的话应该比去年的难...... 10min搞定后去看了T2.... 沃日smg啊,这真tm是noip的d1t2吗... 一眼看上去根本没有思路.... 想了大概半个小时还是并不能想到(我还是弱啊)就去看T3了,发现T3似乎就是floyd之后一个期望dp,于是就开始写。写了大概20min左右突然T2有了一个树链剖分的思路(当时庆幸自己前几天刚刚拍对了一个树剖,不过noip真的会有树剖吗喂!),于是就先把T3放下去写T2了。写了大概一个小时似乎把T2调对了就继续去写T3了。大概在2h30min的时候把三题都写完了.... 而且都过了大样例,去年的大样例还是很强的今年应该也不弱吧(不要插旗啊喂!)于是肉眼查错大概没有问题之后就去玩扫雷了,还创了一个119s的个人新纪录...(这时候还在掉dp啊喂!)估分大概是100+95+100=295吧,比去年day1低了5分。

考完出来之后发现大家似乎都已经弃疗了.... 的确今年noip肯定比前两年的难吧... 午饭也没什么兴趣吃就匆匆回房间了。依然是一遍拍代码一遍玩舰C。把E2 E3通关了,顺便在E3磨血的时候出了朝风(大概这个时候rp已经被我掉光了)(2艘活动船居然都立刻捞到了,而且捞到了梦寐以求的天津风时津风....rp爆炸)。晚上的时候根据今天day1的难度,对明天的难度非常的忐忑.... 按照惯例比day1难吧....就带着这样的想法睡了下去。

Day 2

早上起来收拾好东西就走了,似乎并没有day1那么兴奋了....

T1一看k特别小,看起来可以分解质因数解决啊,就无脑拍了一个分解质因数花了20min,后来从考场出来听到直接杨辉三角形取模之后瞬间觉得自己的智商在考试时简直没有什么下限.... T2想了一会儿并没有想到什么ac做法就直接把所有的部分分全部写了一遍大概花了1h不到吧.... T3一看就是状压dp啊.... 今天怎么这么水啊和昨天完全不是一个画风吧,就直接拍了一个(2^n*n^2)的算法完事,没高兴再优化掉一个n,day2似乎花了2h左右吧.... 理论分数大概就是100+90+100=290了... 这样就算发挥最好似乎也只是585来着,和去年差不多吧.... 于是这一场noip就结束了

出考场的时候发现xy居然把自己头发剪了.... 一眼没认出来.... 在大巴车上回到学校的一瞬间根据noi2015d2t1想出来了t2的ac做法,维护三个队列就行了.... 遗憾啊.... 回到学校以后继续穿上ak战袍颓颓颓。

Day ???-???

得知自己d1t23全炸了的时候其实是非常不知所措的,洛谷的数据非常弱我已经完蛋了,但是余姚的数据比较强我似乎还在js的省队线里面.... 而且全省高一第一(除去nfls的神犇)被一个南师大的人夺走了.... 难受.... 嘛不过省选正常发挥就好了吧....

正式结果出来了,尴尬的是似乎我错的题官方数据都挺强而我对的题似乎数据挺弱的,而且D2T2无脑priority_queue和T3都被卡场了... 尴尬.... 离省队线还有8分的差距,按照我省折换成100分就是0.4分... 果然省选正常发挥还是没问题的吧... 啊还有省常中THU爷zrl简直是难兄难弟.... 连续3年noip和我的分数差不多,去年和今年甚至和我名次一上一下... 而且去年都是爆的同一题的空间.... 不过人家比我强啊.... 还是要努力提高自己的姿势水平才行...

 

 

NOIP 2016 游记

@krydom10月前

12/14
19:53
并查集

[bzoj 4668] 冷战

00:00/00:00

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

1946 年 3 月 5 日,英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁幕演说”,正式拉开了冷战序幕。美国和苏联同为世界上的“超级大国”,为了争夺世界霸权,两国及其盟国展开了数十年的斗争。在这段时期,虽然分歧和冲突严重,但双方都尽力避免世界范围的大规模战争(第三次世界大战)爆发,其对抗通常通过局部代理战争、科技和军备竞赛、太空竞争、外交竞争等“冷”方式进行,即“相互遏制,不动武力”,因此称之为“冷战”。
Reddington 是美国的海军上将。由于战争局势十分紧张,因此他需要时刻关注着苏联的各个活动,避免使自己的国家陷入困境。苏联在全球拥有 N 个军工厂,但由于规划不当,一开始这些军工厂之间是不存在铁路的,为了使武器制造更快,苏联决定修建若干条道路使得某些军工厂联通。Reddington 得到了苏联的修建日程表,并且他需要时刻关注着某两个军工厂是否联通,以及最早在修建哪条道路时会联通。具体而言,现在总共有M 个操作,操作分为两类:
• 0 u v,这次操作苏联会修建一条连接 u 号军工厂及 v 号军工厂的铁路,注意铁路都是双向的;
• 1 u v, Reddington 需要知道 u 号军工厂及 v 号军工厂最早在加入第几条条铁路后会联通,假如到这次操作都没有联通,则输出 0;
作为美国最强科学家, Reddington 需要你帮忙设计一个程序,能满足他的要求。

Read More →

[bzoj 4668] 冷战