不知道OI是啥或者信息学竞赛是啥的可以按Ctrl+W

很早开始写的。。准备出分之后再发布。

谨以此文纪念我信息学竞赛的第一次正式考试。

考前一些天写的:

11.5

下午想转发一下去年的RP++的说说。发现去年没有发(或被删?)。。

真想认识一下heoi群里其他学校那些人。

晚上回忆了回忆去年noip的作死种种。发现新高一的比我们去年厉害多了。

11.7

上午吃完早饭发现过了上学的点了,于是就又没去。

下午去河北师大试机。

去的很早,先去看了吃饭的地方。

后来进了机房。试着打了打字。

准考证很久很久后才下来。

我竟然是 HE-001。RP++

晚上看了看秩序册之类的文件就睡觉了。(睡得还不错。

正式开始:

11.8

因为APEC会议减排限行,打车去的。去的很早很早。

很早很早到了那里,早了约1个小时,只好在那里等着好了。

河北师大数信楼,天气有点微冷。

过了会老师发了下座位号码条,一条一条手撕下来的。

看到了一大群衡x中学的。

又过了会,看时间差不多了就开始进场了,和去年noip一模一样的机房,可惜忘了去年坐的位置。

这个题在bzoj上好像是个权限题,想做的可以去Vani的博客下载测试数据。
这里有题面。

简单叙述一下题意
给你一个n个点、m条边的带权无向图,S点和T点,询问Q次删一条给定的边的S-T最短路。

其中 1<=n,m,q<=200000

ps. 1.这个题网上好多解法都是错的。2.这个题数据范围很大。

先求S到每个点的距离ds[i]。如果ds[T]为inf的话,输出Q个无解好了。
然后再求每个点到T的距离dt[i]。(用堆优化的Dijkstra即可。)

建一张最短路径图Gs仅包含ds[v]==ds[u]+w[u,v]这样的有向边。
同理再建一张最短路径图Gt仅包含dt[v]==dt[u]+w[u,v]这样的有向边。

我们可以发现在这两张最短路径图上,有一些关键边,与桥边类似,从S-T的最短路必经这些边。
可以知道,如果删掉的不是这些关键边,那么答案不会变,只有删掉关键边答案才会变。

这些关键边如何求呢?网上有些题解写的是把最短路径图看成无向图的桥边。(这个是有明显反例的,随便一拍都是反例,但是有的代码就是能过题 - -|)
还有的是用对Tarjan求桥边的时候做了一些限制,但是我觉得正确性未知。

我用了一种比较保(qi)险(guai)的方法,求出的这些关键边。

首先假设每条边的容量都是1,像网络流一样做两次增广,注意不需完整的最大流,只需两次增广。
如果流量>=2,说明这个图里没有关键边,直接输出Q个ds[T]即可。

那么我们来看流量是1的时候,很显然关键边就是能成为最小割的边(流量只有1),我们用Tarjan对这个图求一次强连通分量,设id[i]表示i这个点所属的连通分量编号。如果一条边(u,v)满流且id[u]!=id[v]那么这条边就可以成为最小割的一条边,即为关键边。
如果把Gs中的关键边反向就是Gt中的关键边。

“很难想象自己一年后的样子呢。”


如果没记错,一年前的今天应该是中考的日子,当时考完感觉很爽。(考完很爽的考试这辈子应该也没几次。) 过了几天后得知happyending,然后就玩了一个暑假,去了好多地方。

时间过得好快呢~

来省理科实验班也一年了吧,现在依然是天天被虐的感觉。

刚开学的时候老师说高一会过得很快,现在看应该是真的。


学OI也有一段时间了,从原来的非常弱变到了现在的很弱。(也是一种进步呢。)

学了许多神奇的算法,认识了许多人,达到了自己想象不到的打字速度。除了这些,收获应该还有许多。


中考,高考。“你觉得对自己很重要的考试,对别人来说也许就只是几天假。”

以上。

HEOI2014 标程数据下载.

百度盘 http://pan.baidu.com/s/1qWx7YAo

有版权问题的话下面留言…


又到了一年一度的HEOI呢。
我果然还是太弱了呢。


(省选是在5月17、18日举行)


Day0

报到日啊,省选今年在河北经贸大学举办,还算很便利的。

于是下午翘了一节语文课,出校门打了辆车,就去了。

我跟那位司机说河北经贸大学,他说“是五七路那个么”,我说就那个红旗大街附近那个。

然后就直奔五七路了。。。。。

走到一半左右,在手机GPS上发现自己已经偏离了方向,就跟司机说啊,于是发现走错了路,原路返回。。(打车花了好多钱。 )

最后竟然按时到了报到的机房。

见到了gmh同学,还有高二的qy,mhr,fy,wsh,lah,wrd神犇们,还有一大波衡水的。

交了钱,发了准考证,开始试机。

在试机过程中,手贱把dev-cpp给卸了。。一时找不到安装文件,他们都在敲模板,我在玩notepad++。

大概半个小时?说:没事的可以走了,我想了想,我是没事的,于是我走了。

回到了学校,他们还没下课。。先去吃饭。吃完饭,他们还是没下课。。。

晚自习写了写学校作业。。

晚上在群里问了下longlong怎么输出,是I64d 还是lld,隧知为lld。


Day1

第一天比赛日,去早了,于是与众神一同在考场外等候。

到了考场。老师让建一个叫noip2014的文件夹。

我想:“这么快就到noip2014了。。”。

然后试题发下来。

一看t1,组合游戏?类似nim之类的。于是准备放弃。

再看t2,矩阵乘法吧。但是付出$t^2$的体力没法整啊。

看看t3,树形动规吧。

然后开始写t3,写着写着,突然不知道草稿纸上的方程怎么转移了,遂放弃。

然后写了个裸地倍增lca先留着,对拍用。。

看t1,发现如果没有$a+b<=m$这个条件,也就是$m>=n$,直接判断下奇偶性就好了,于是遂写,10分到手。

发现这种题竟然连暴搜都不会写,想开一个n维的数组,(后来证明当时傻了。),然后就发现存在一种情况,使它最终停止状态是$ceil(n/m)$,于是就想根据这个状态判断下奇偶,结果过了样例。不管了。。

看t2,发现$t^2$的体力,是不是可以拆成1+3+5+7...转移。于是打开excel构造矩阵,一个小时之后,准备放弃。。写了个朴素的

OPEN

世界应该是开放的。

互联网应该是开放的。

愿我以后仍能坚守这一点。