这个东西还是应该写写博客的，毕竟IOI
题目连接已给出，直接点击大标题(推荐网络OJ:Universal Online Judge)

IOI2014 Rail

题目有点难看，耐心……
题目是说给出任意两段车站的距离(你只能得知其中的$3(n-1)$对距离)和$0$车站的位置，让你确定每个车站的位置和类型$C$或$D$
距离的定义请看题
题目保证$0$车站为$C$类型

直接说正确的解法(部分分很水请独立思考)
我们会发现：
1.车站$x$到$y$的距离$==$车站$y$到$x$的距离
2.离距离某个$C$类型车站最近的车站一定是右方向上最近的$D$类型车站
根据以上两条，我们可以按照如下步骤操作：
1.求出所有其它车站到$0$号车站的距离，根据性质2我们可以推出距离最近的站点的位置及类型，将其记为$right$。
由此我们可以根据距离关系将剩下的车站分为两类:
1.位于$right$的左方，满足:$dis(0,i)==dis(0,right)+dis(right,i)$
2.位于$right$的右方，满足:$dis(0,i) \neq dis(0,right)+dis(right,i)$

仔细观察发现，此时$0$与$right$只可能存在$C$类型的车站
就此我们又可以将$right$左方的车站分为两类:
1.位于$0$与$right$之间，满足$dis(right,i) \leqslant dis(right,0)$
2.位于$0$左方，满足$dis(right,i)>dis(right,0)$

现在问题剩下:$0$左边与$right$右边的了
以$right$右边的为例:
思考:
1.将右边所有车站按照到$0$或者$right$排序，最近的一定是$D$类型的车站
对于剩下来的车站，我们维护一个$D$类型车站的栈
我们每次询问$i$到栈顶$top$的距离
我们可以通过计算得到$dis(0,top)+dis(top,i)$与$dis(0,i)$
设$\Delta=(dis(0,top)+dis(top,i)-dis(0,i))/2$
计算位置$location[top]-\Delta$是否合法(在right右边)且该位置上是否存在一个$D$类型车站
如果合法且存在$D$类型车站，则说明位置$location[top]-dis(top,i)$上存在一个$C$类型车站
否则，则说明位置$location[0]+dis(0,i)$上存在一个$D$类型车站，并将其加入栈
判断位置是否存在$D$类型车站，可以使用二分或者hash

上面这是干嘛呢？
其实仔细画个图看看就能明白
拿出笔和纸吧(^o^)/~
位置:$0 ~~~1 ~~2 ~~~3 ~~4 ~~5 ~~6$
车站:$C ~D ~C ~~~~~ ~D ~D$
编号:$0 ~~1 ~~~2 ~~~~ ~~~3 ~~4$
自己用笔和纸玩一玩就明白

$0$左边的车站解法类似

这样我们就在限制条件$3(n-1)$下解决了这个问题
时间复杂度:O(n)或O(n log n)

IOI2014 Wall

维护一个长度为$n$的区间，支持两个区间操作
线段树标记大法好！
什么？你不会线段树标记？

好吧，我们简单讲讲
如果我们每次区间修改都改到每个点上，显然是会超时的对不对？
为什么？
因为这样的话线段树就太勤快了
然而事实上它是很懒的……(扯淡而已︿(￣︶￣)︿)
如果一个节点表示的区间都存在一个操作，我们可以先把这个操作放在这
也就是lazy标记
等到下次访问这个点的时候，我们再把标记下传
这样每次修改的复杂度就少了许多
但是为什么就不会TLE呢？(其实我也不知道╮(╯_╰)╭)

(网络上都说:IOI数据结构题对中国选手都是送分题……)

IOI2014 Game

这个题……
两个熊孩子玩游戏……

一个很容易理解的做法

对于每个询问$u$和$v$，考虑它们所在的连通块
如果$u$和$v$的连通块之间的其它所有边都被询问过，我们就回答这条边是存在的
否则就回答这条边不存在
为什么这样做呢？
如果我们在$u$和$v$的连通块之间的其它所有边都被还没被询问过时就回答存在，那么那条没被询问过的边就不在具有询问意义
如果这条边的询问放在后面，那么熊孩子健佳就输了……
实现可以使用邻接矩阵，并查集来实现
$ps:$两个联通块$x$和$y$之间的边数为$|x|*|y|$($|x|$表示联通块$x$所含点数)

一个比较容易写的做法

妈妈你看，为什么它们的AC代码都这么短？

#include"game.h"
int a[1510];
void initialize(int){}
int hasEdge(int u,int v) { if (u<v) u=v; return ++a[u]==u; }

这只是碰巧么？
当然不是
考虑一下特殊的连通结构：树
我们控制：对于点$i$，编号比它小的点中，与$i$相连的边只有一条
这样的话就严格控制了整个图为一棵树