陪你开始OI的人未必能陪你走到散场。一次擦肩而过之后可能就再也见不到了。

这几天过得好乱,也不知该说些什么。

Day 0

今年省选在河北师大,和去年noip一样。

听说dyf大爷要来,也不知道来干啥。

考试前一天去试机萌萌哒。

键盘软的不行不行的。

打了个SA,FFT?调了半天才对,反正估计考的可能性不大。

╮(╯▽╰)╭

然后高一的连试机都不来。(真是厉害。

Day 1

第一天好紧张啊好紧张,一想弄不好就滚粗了就害怕。

然后一切正常的进了考场。

看了第一题。发现只会三十分树形背包。

看了第二题。发现只会三十分暴力。

看了第三题。好像是乱搞题。

maya。。看了第一题数据范围那么大。

就去想跟m无关的算法了,后来想到贪心,和暴力拍的没问题。

一想“富贵险中求”,就决定交了贪心。

后来觉得第二题分块可搞,就写了,拍了,没问题,好像有点卡时。

然后第三题sb题,随便搞搞和暴力拍。

就结束了。

先去吃饭。

没食欲QAQ。

题意:

给你n个不相交的凸多边形或圆,每个图形有一个权值。
询问m次,从一个点到另一个点,穿越过的图形的权值异或和。

题解:

扫描线+树链剖分。
这些图形的互相包含关系形成了一些树。
每次相当于求从树上一个点走到另一个点边上的权值异或和。
扫描线算法$O(nlgn)$求出这颗树,然后树链剖分维护下就好了。

代码:

不知道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也有一段时间了,从原来的非常弱变到了现在的很弱。(也是一种进步呢。)

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


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

以上。

Mastodon