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

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

@krydom6月前

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 游记

@krydom11月前

08/8
15:15
未分类

[bzoj 3036] 绿豆蛙的归宿

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

随着新版百度空间的下线,Blog宠物绿豆蛙完成了它的使命,去寻找它新的归宿。

给出一个有向无环的连通图,起点为1终点为N,每条边都有一个长度。绿豆蛙从起点出发,走向终点。
到达每一个顶点时,如果有K条离开该点的道路,绿豆蛙可以选择任意一条道路离开该点,并且走向每条路的概率为 1/K 。
现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?

Read More →

[bzoj 3036] 绿豆蛙的归宿

@krydom11月前

07/31
22:30
未分类 高精度

[bzoj 1876] [SDOI2009]SuperGCD

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

 Sheng bill有着惊人的心算能力,甚至能用大脑计算出两个巨大的数的GCD(最大公约 数)!因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你,并要求和你比 赛,但是输给Sheng bill岂不是很丢脸!所以你决定写一个程序来教训他。

Read More →

[bzoj 1876] [SDOI2009]SuperGCD

@krydom1年前

06/6
21:10
未分类 树状数组 离线

[bzoj 2743] [HEOI2012]采花

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

萧芸斓是Z国的公主,平时的一大爱好是采花。
今天天气晴朗,阳光明媚,公主清晨便去了皇宫中新建的花园采花。花园足够大,容纳了n朵花,花有c种颜色(用整数1-c表示),且花是排成一排的,以便于公主采花。公主每次采花后会统计采到的花的颜色数,颜色数越多她会越高兴!同时,她有一癖好,她不允许最后自己采到的花中,某一颜色的花只有一朵。为此,公主每采一朵花,要么此前已采到此颜色的花,要么有相当正确的直觉告诉她,她必能再次采到此颜色的花。由于时间关系,公主只能走过花园连续的一段进行采花,便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了m个行程,然后一一向你询问公主能采到多少朵花(她知道你是编程高手,定能快速给出答案!),最后会选择令公主最高兴的行程(为了拿到更多奖金!)。
(6)

Read More →

[bzoj 2743] [HEOI2012]采花

@krydom1年前

06/6
11:27
二分图匹配 未分类

[bzoj 1059] [ZJOI2007]矩阵游戏

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

小Q是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行(如同国际象棋一般,只是颜色是随意的)。每次可以对该矩阵进行两种操作:行交换操作:选择矩阵的任意两行,交换这两行(即交换对应格子的颜色)列交换操作:选择矩阵的任意行列,交换这两列(即交换对应格子的颜色)游戏的目标,即通过若干次操作,使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。对于某些关卡,小Q百思不得其解,以致他开始怀疑这些关卡是不是根本就是无解的!!于是小Q决定写一个程序来判断这些关卡是否有解。
(2)

Read More →

[bzoj 1059] [ZJOI2007]矩阵游戏

@krydom1年前

03/23
19:32
后缀数组 未分类

[bzoj 1031] JSOI2007 字符加密Cipher

00:00/00:00

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

 喜欢钻研问题的JS 同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法:把需要加密的信息排成一圈,显然,它们有很多种不同的读法。例如下图,可以读作:
1
JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序: 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符:I0O7SJ,就是加密后的字符串(其实这个加密手段实在很容易破解,鉴于这是突然想出来的,那就^^)。但是,如果想加密的字符串实在太长,你能写一个程序完成这个任务吗?

Read More →

[bzoj 1031] JSOI2007 字符加密Cipher

@krydom2年前

11/27
21:21
一般动规与递推 未分类

[bzoj 1600] [Usaco2008 Oct]建造栅栏

00:00/00:00

d1160924ab18972bf0868ff9e4cd7b899e510a40  a8773912b31bb051b7e33f1b347adab44aede03a (1)

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

 勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n(4<=n<=2500)的木板,他想把这块本板切成4块。这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意: *只要大木板的切割点不同就当成是不同的方案(像全排列那样),不要担心另外的特殊情况,go ahead。 *栅栏的面积要大于0. *输出保证答案在longint范围内。 *整块木板都要用完。

Read More →

[bzoj 1600] [Usaco2008 Oct]建造栅栏