SDOI2018划水记

Day -1

上午做了一道网络流,发现自己并不会当前弧优化,于是学之。

刷空间发现大家都去春游了,空间变成相册集,好感–,羡慕++

下午打板子,发现洛谷数据太弱之前的Splay打的都是错的qwq

晚上吃饭的时候才意识到大家都放假了。。。好像食堂也gg了。。超市也gg了。。

决定出去买吃的 冻死我了

在机房吃方便面居然没有被刚 , qtq

十点有一场Edu,然而怕打完太兴奋,最后缺觉而放弃了,跟着老司机(s) Sugar和Refun打了一个场外(口胡)

然而最后还是将近一点钟才睡

Day 0

上午,打盹,打板子。

中午,去潍坊,赶火车

下午,继续打板子

板子板子板子板子qwq

晚上,继续打板子

大家和Yansir一起去超市,窝给zzy安利一包辣条,然而被Yansir抓了,Yansir刚了一顿(又不是我买的吖……我提个篮子有错……罪过,罪过)

“那个爱吃零食的”……被抓颓又一顿沮丧……

最后抓一瓶茶π逃了……

Day 1

起床,吃饭,然后进场

出汗+慌……Refun小哥哥长的真好看(雾

rqy在我右面的右面的右面 ……慌+1

键盘超级脏 慌+2

发密码,慌+3

看题……慌+4

我tm什么鬼博弈…………???!?!

慌+998244353

!!去刚第二题……

不久发现是个贪心,45min写+调+拍……并没有意识到di都相等会挂掉

慌–,莫名自信(sad

天真的以为A了第二题

滚去写T1,发现状压可过,不想写++

树是一条链……强行不用主席树A掉这部分数据……唉我怎么做的来着??忘了…………

打完T3,35min passed

滚回去想T1,想出了std……好麻烦……写不完了……写暴力吧

送了25,写。 35min passed,写完了。

自信不对拍T1T3,暴力很稳的我异常自信感觉很虚

就这样滚出考场,估计25+100+15,(然而……)

滚去吃饭,被dkw Hack掉T2,sad++,感觉药丸

下午去大礼堂讲题,真tm难走都迷路了

颓废大麻茶,%rqy……等着出成绩

发现T1想的是std,然而没写……据说很短……sad++++++++

2:55被告知T2卡精, 没加eps!!panic+=998244353

这题都是什么画风啊……还有我怎么这么弱啊……

这么弱啊……

发成绩,看榜,讲题……T3是生成函数+线段树,然而并没有听懂线段树怎么用……

rk45,sad++

rqy太强啦!强力rk2

dkw在山西rk2……强啊……今年A队爷出现了……

Capella没建子文件夹,心疼Capella

cwbc拿了rk1,cwbc太强啦!

大家都比我强.jpg

……也应该吧……弱校弱选手……划水++

Refun似乎考的不好,祝他D2翻盘!

晚上去超市颓废饮料,发现没有大麻茶,sad++。 又拿了一瓶茶π跑了……茶π真好喝

颓废hp4电影,打Miller-Rabin,在群里水,和学长们讨论人生

Day 2

进场,看题。

T1一眼费用流,打!

我用费用强行创造优先级……记录一发每个导师的最靠后的学员……这不就行了?

增广完一个点我让他当前志愿的后续志愿的边强制满流,瞎证了一发好像是对的。(并没有意识到贪心可以拿分……)

打完了……过了四个鬼知道多弱的样例,扔着不管了,自信不对拍

10:40了,woc

T2弃疗,拿T3暴力去。

发现就算不kmp也有n^3的分数,真棒。写写写,分类讨论推答案推到11:45,模拟之。

好像要补集转化……?我求一下不在左面的和不在右面的区间然后合并再讨论不就好了嘛。

草稿纸好像不够……

唉。然后我枚举左端点暴力判断吧……好像很稳

我需要查询他有多少合法的右端点,显然是当前左端点后面一个合法区间里啊!先预处理。

好了,终终终于打完了。拍样例,小改一下,过了。

暴力一向很稳的我自信不对拍,发现T1第二问做错了,去改T1。有退流啊!我最后要手动枚举才行啊!

没改对,瞎证明了一发,发现之前的好像是对的(弱智的我)。

100+0+25

吃晚饭直接出了成绩,0+0+25。本来的翻盘梦想破灭了,R2再见。

没事可干,继续颓废hp4电影,内心毫无波动。等着Yansir看完测评,目测滚出前100

zzy强势翻盘,太强啦!Refun强势翻盘,太强啦!

dkw rk4进队,……祝他NOI18 Au吧。

rqy和cwbc好像都100多了,但是tyc好像拿了超级多的分????有225???!!

wodema。

迷迷糊糊滚回昌邑……在烟台南站颓hp4电影结果被Yansir刚了……sad++

最后rk68,然而rk68和rk200并没有区别,本来的翻盘梦想破灭了,R2再见。

Day 1000000007

发名单了,rk100多,NOIp强力拖后腿。

sad+=1000000007;

滚回去面对同学们……

被Yansir打电话刚,感觉嗓子都不是自己的了……

突然发现满腔热血搞了一年OI结果啥比赛也没结果……

Get lost in the cruel world.

没结果就是没结果,我也没什么话说。

真没什么话可说。

弱校,弱人,学的晚,低智商,爱颓,啥都不会。

哪天你在街上看到一个这样的人,那是我。

SDOI2005 遗传代码

此题luogu无题解

所以来一篇

用DSU+特判解决问题

 

先求一下森林和每棵树节点数

对于每个节点分别统计对答案贡献

最后特判一下单独的节点,还要+1

日常水这种题

 

BZOJ1880 | SDOI2009 Elaxia的路线

Description

最近,Elaxia和w**的关系特别好,他们很想整天在一起,但是大学的学习太紧张了,他们 必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间,他们 希望在节约时间的前提下,一起走的时间尽可能的长。 现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图:地图上有N个路 口,M条路,经过每条路都需要一定的时间。 具体地说,就是要求无向图中,两对点间最短路的最长公共路径。

Input

第一行:两个整数N和M(含义如题目描述)。 第二行:四个整数x1、y1、x2、y2(1 ≤ x1 ≤ N,1 ≤ y1 ≤ N,1 ≤ x2 ≤ N,1 ≤ ≤ N),分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号(两对点分别 x1,y1和x2,y2)。 接下来M行:每行三个整数,u、v、l(1 ≤ u ≤ N,1 ≤ v ≤ N,1 ≤ l ≤ 10000),表 u和v之间有一条路,经过这条路所需要的时间为l。 出出出格格格式式式::: 一行,一个整数,表示每天两人在一起的时间(即最长公共路径的长度)。

Output

一行,一个整数,表示每天两人在一起的时间(即最长公共路径的长度)

如果你没有意识到两个人即使对头走也算的话(既一个从x1到y1,一个从y2到x2)那你可以和我一样吐槽出题人的语文功底了。

(如果不反过来做的话建了两条边,就出环了)

先跑四次最短路

然后我们枚举所有满足条件的边Ei,j,使

dis[x1][i]+dis[j][y1]+Ei,j等于dis[x1][y1]且dis[x2][i]+dis[j][y2]+Ei,j等于dis[x2][y2]

翻译成人话也就是枚举一条公共边,使这条公共边在x1到y1的最短路上且在x2到y2的最短路上。

然后建一个新图,把这条边换成有向边加到图上去。

最后就是拓扑排序跑最长路。

注意还要反过来再做一遍(dis[x1][i]+dis[j][x2]+Ei,j = dis[y2][i]+dis[j][x2]+Ei,j)

BZOJ1924 | SDOI2010 所驼门王的宝藏

在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的Alpaca L. Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天Henry Curtis故事的起点。Henry是一个爱财如命的贪婪家伙,而又非常聪明,他费尽心机谋划了这次盗窃行动,破解重重机关后来到这座地下宫殿前。

整座宫殿呈矩阵状,由R×C间矩形宫室组成,其中有N间宫室里埋藏着宝藏,称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔,由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这N间藏宝宫室每间都架设了一扇传送门,没有宝藏的宫室不设传送门,所有的宫室传送门分为三种:

  1. “横天门”:由该门可以传送到同行的任一宫室;
  2. “纵寰门”:由该门可以传送到同列的任一宫室;
  3. “自由门”:由该门可以传送到以该门所在宫室为中心周围8格中任一宫室(如果目标宫室存在的话)。

深谋远虑的Henry当然事先就搞到了所驼门王当年的宫殿招标册,书册上详细记录了每扇传送门所属宫室及类型。而且,虽然宫殿内外相隔,但他自行准备了一种便携式传送门,可将自己传送到殿内任意一间宫室开始寻宝,并在任意一间宫室结束后传送出宫。整座宫殿只许进出一次,且便携门无法进行宫室之间的传送。不过好在宫室内传送门的使用没有次数限制,每间宫室也可以多次出入。

现在Henry已经打开了便携门,即将选择一间宫室进入。为得到尽多宝藏,他希望安排一条路线,使走过的不同藏宝宫室尽可能多。请你告诉Henry这条路线最多行经不同藏宝宫室的数目。

 

[无耻地借用洛谷的图片]

首先缩一下点……

然后跑DP……

很简单QAQ

在BZOJ写了7000B,成功拿到『最近几页的最长代码』成就

在洛谷跑了400ms,超级快。//好像空间还用的很少