250：算出U和D分别有几个，然后显然应该先全U然后再histroy然后再全D。。判断一下即可。
550：求floyd传递闭包，如果f[i][i]=true那么显然选i没意义，无视掉这些点之后就是个DAG。那么就是求DAG最长反链，也就是n-最小链覆盖。
1000：我比赛的时候解方程写错了。。我是傻逼么？
注意到。。。我们实际上是要找n个互相独立的向量v1,v2,…,vn (mod 2下的向量)
他们跟输入向量A的"点积"(乘了之后xor起来)的和最大。
由于这是个拟阵，每次找一个跟之前选的向量独立的且跟A点积最大的向量就行了。
我们对A先高位到低位消一次元然后从大到小排序，
那么从i=0开始每次如果选ai更优就选，不然就不选，用解方程判断能不能选即可。
具体看我在Arena里面的代码。
这个空间最后一篇日志啦LOL。。。请岛娘帮忙开新空间xD
LOL。。。开个坑。。。
本来说要换新空间的但是在太懒了就拖一会儿吧。。。
目前已经在Arena里做完了Semi1 Semi 2 和Wildcard。。。
代码见Arena room
慢慢填吧。。。
Semi 1:
250:我们不妨计算白色格子的数量，注意到一个联通块显然是一个矩形，如果我们确定了S[i]=T[j]=U[k]的这个字符x，那么比如说S中a1..a2是全是x,T中b1,..b2全是x，U中c1…c2全是x，那么显然这就是一个白色的长方体，同时只要a1..a2,b1..b2,c1..c2中有一个贴着边缘，那么就全最后生下来的白色格子。
分析到这里，只要枚举是S,T,U中的哪个贴边了，然后计算答案即可。
500:注意到说白了我们得到的信息pi是说i的前面是哪一个。
那么图论化一下就是说要建立一个最小字典序的pi序列使得i->pi这个图形成一个环。
显然只需要满足2点，这个问题就是有解的：
1：图中没有长度小于N的环。
2：图中没有出度和入度大于1的点。
我们只需要用个并查集维护连通性，然后注意不要违反了这两个条件一位位给pi填上去就行了。
1000:看起来很难。。。
题目的意思实际上是要求所有连续k个都在xor下线性相关。
我们不妨倒过来求"存在连续k个在xor下线性不相关"的序列的数量。
我们注意到到实际上只需要记最后有几个数是线性不相关的就行了。
比如最后有k个数线性不相关么，那么有m-(1^k)+1种可能性新的数跟他们线性不相关
k->k+1
否则跟他们线性相关的话，实际上就是从这k个中选几个xor起来，不妨说选的最后一个是倒数第i个，
那么之后就只有i个线性不相关的数了，有2^(i-1)种可能性。
那么状态是k，用矩阵乘法加速即可。
我今天下午看了一下题目。。。。大致上感觉都是可以做的。。。随便写的解题报告。。。有错误请轻喷T_T。。。
Day1：
problem 1：40分还是比较好拿的。。。但是接下来2个task略恶心。。。我有几个思路不知道能拿几分。。。。。。
problem 2：我觉得这题挺简单的吧。。。让我们考虑什么情况下一个图全是链条。。。
条件1：所有点度数<=2(废话)
条件2: 没有环。
那么大致分几种情况讨论和维护一下就行了。。。
problem 3：rope秒杀。。。不用rope的话也可以用类似树的结构。。总之是sb题。。。
Day2：
problem 1：
我们不妨考虑一个简单的情况，如何解决凸多边形的问题？
由于凸多边形比较优美，两点间距离就是曼哈顿。。所以直接算即可。
那么如何解决复杂的情况呢。
不妨以格子为点，相邻点间连边。
给每个格子加权，a和b之间的距离要乘上a和b的权。。
首先处理一个情况，就是桥，显然桥被经过的次数是确定的，同时从其它方向来的点，直接当成权加在桥的两端上就行了。。。
那么现在没有桥了。。。
一开始权都是1。。。
那么如果有度数是1的格子，显然他必须要往它的唯一相邻格走一步，那么就把它的权加到它的相邻格上去然后删掉他，同时这可以看成他走了一步，故答案要加上他的权乘上所有格子的权和。
如果没有度数是1的格子，那么我们考虑最左边的一行，最靠下的点，毫无疑问他的上方和右方必须有点
同时他的右上方也必须有点(不然就有桥了)。
依次类推，可以证明这个点一直往上到不能往上的这一列的右边都有点。
那么显然这一列除了到自己内部之外，都要先往右走一步。
那么在答案中加上这一列内部的情况，然后把他们加到右边那一列上去。。。
同时可以证明之后如果产生了桥，只可能是因为出现了1度点，处理掉即可。。。
看起来很复杂的样子。。。不过复杂度是线性的。。。
UPD：这做法太傻逼了。。
from wqs：注意到把所有横向的最长连续块压成一个点，那么必然形成一棵树，然后树形dp就行了。
我的搞法搞了那么多实际上只是想办法找到树的一个叶子然后往上推。。。本质上是差不多的。。。但是太麻烦了。。。
不过这么搞也行，其实不用求桥，我们可以维护所有边界上的连续块来找。。。。上下左右四个边界上总能找到树的叶子。。。
problem 2:
注意到我们一个点只能保存2个bit。。。
其实2个bit就够了。。。
我们不妨balabala求一个最优解。
然后一个颜料根据是从脚手架上拿的与否跟放不放到脚手架上，有四种状态(注意到，就算一个颜料是从脚手架上拿的，也要记他放不放到脚手架上，不放到的话意思就是会在将来被扔掉)。
那么对于从脚手架上拿的，我们得到了一个rest，如果不放到脚手架上的话，我们维护一个垃圾堆，放到垃圾堆里去。
对于从新的地方拿的，如果不放到脚手架上->直接扔掉。
放到脚手架上->我们随便扔掉一个之前垃圾堆里的颜色。
我傻叉了．．．不用记是不是从脚手架拿的，直接按脚手架里有没有判断就行了．然后要记一下一开始的ｋ个是不是要直接扔掉．
那么只要N＋K bit就能搞定了。。。。
另外这个的原理是什么呢。。。只要注意到这个本质上是一个从网络流的流量中构造解决方案的过程。。。你就明白了。。。
我们可以对这个问题网络流建模，那么可以发现只要2N的信息就能记录这个网络流的流量从而构造出解决方案。
UPD：
根据wqs说的是不用记是不是从脚手架上拿的的，只要记扔不扔掉就可以了，不过这就同时要记一下一开始在脚手架里的那k个扔不扔掉。。。要N+k位。。更优一些。。。
problem 3：
我才发现原来的搞法完全是扯淡。。。
对这个比赛按位置建一个博弈树。
同时将R标称0，比他强的标成1，弱的标成-1。
那么我们注意到，实际上我们要做的是将0跟它右边位置的叶子交换位置，和从0往上数胜利者有几个0。。。
这个是很好搞的。。。
比如说找一个跟当前0 Lca最低的1。。。
这个找0前后最近的两个1试一下就行了。
总体而言day2比day1难。。但是day1有坑爹构造题。。。。momo tourist。。。。
这次还是我跟AC跟JZP。。。连续两次#1了！！！！
1001:
如果我们有个一个数据结构，能过支持两个操作：
1。返回某给定矩形中的点
2。删除某个点。
那么对于每个操作，我们只要维护一个队列。
每次找出队列中的第一个点，然后把它能影响的点全部删除并且加入队列。
类似bfs的搞就可以了。
这个数据结构我直接使用了线段树套线段树(先离散化)，勉强卡过了。
1002:
让我们只考虑上午的情况(下午一样)。
对每个柱子i分别考虑，容易发现在特定角度区间遮挡它的是特定柱子。
这个可以通过一次扫描实现，方法类似于凸包，画个图脑补一下就行了。
然后对于特定的区间，可以发现遮挡的长度是a+b*cot(t)的三角函数，
根据它跟0和H[i]的大小关系分一下段然后分别积分算答案。
(a+b*cot(t))*sin(t) = a*sin(t)+b*cos(t)。。。这个积分是比较好算的。。。
由于细节很多我跟JZP写了很久都没调出来。。。
1003:
就一坑爹题吧。。。直接爆搜，考虑一个度数剪枝。
令每个未经过点的度数为与他相邻的未经过点数。
显然除了最后一个终点，得至少有2度才能组成路径。
也就是说不能有0度点，1度点最多一个。
这样剪一下就能过了。
1004：
纱布题，不用讲吧。。。
1005：
说白了就是求一个圆跟一个多边形的并。
我们把多边形三角剖分，就能转化成圆跟很多个三角形的并(根据方向是有正负之分的)。
为了方便我们可以以圆心为坐标原点。
这样三角形的一个点就必然是圆心，求圆跟三角形的并就方便多了。
1006:
挺简单的dp呢。。令dp[i]表示从i点到终点的期望时间。。。然后dp[i]的话如果有flight就做flight做到不能做，否则就投个骰子。
1007:
比较简单的费用流问题。。。
对day和科目分别建点。。
然后从天向科目连边。。。
注意到虽然有的边费用是一个二次函数，但是由于这个函数的f[1],f[2],f[3]中，f[1]-f[0],f[2]-f[1],f[3]-f[1]是单调的。。。所以我们可以把它拆成多条边使用费用流算法。
1008:
我们可以发现一开始是1..n。这个条件很重要，因为s[i]!=i的i最多只有会O(m)个。
那样的话我们可以使用容斥原理计算出l..r这几个数跟p互质的数的和。
然后处理一下那些s[i]!=i的位置。
很多同学问如何算l..r这几个数中跟p互质的数的和.
首先不妨令p的质因子是p1,p2,p3..,pn..
同时令rec(r,i)表示1到r中跟pi,…,pn互质的数的和.
那么我们可以发现rec(r,i)=rec(r,i+1)-rec(r/pi,i+1)*pi
因为1到r中跟pi,…,pn互质的数的和=
1到r中跟pi+1,..,pn互质的数的和
-1到r中跟pi+1,…,pn互质的数,同时是pi的倍数的的数的和.
那么rec(r,0)-rec(l-1,0)就是答案了.
1009:
可以说是老原老原的题了吧。。。。
就不说了。。。
SPOJ MSTS
其它题目我不清楚。。。等下再补。。。
时间过的真快啊>_<…离上次办这样的比赛也有2年了吧…
转眼间就这样了呢…
不管怎么说又来办比赛了,希望大家做的开心吧>_<…
题目效仿东方一共有4道:Easy,Normal,Hard,Lunatic.
Lunatic的话>.<,才不是专门为你们这群神犇出的呢!>_<
网址: http://new.tyvj.cn/Test_Show.aspx?id=1092
总共3个小时.
比赛之后就会发布题解什么的.
题目见BZOJ…
其实就是zej在WC讲的那题的简化版,不过简单了不少,我就自己推了一下.
让我们考虑一棵Trie。
注意到实际上有用的结点只有O(n)个。
那么我们像后缀树一样的压缩方法。可以得到空间O(n)的Trie。
插入删除修改的复杂度变成了O(min(n,W))，W表示位数
有啥用呢？首先是降低时间复杂度的常数，因为可以使用位运算一次往下前进很多步。
其次是狂降空间。
比方说：
http://www.lydsy.com/JudgeOnline/problem.php?id=1146
这题
如果使用主席树的话空间复杂度是O(nlog^2n)了。
但是如果改用树状数组套compacted-Trie。空间复杂度就变成了O(nlogn)。
当然时间复杂度不变。
其实基本没啥用，不过在Int上速度完艹各种平衡树。。。空间也不会挂了。。
http://www.lydsy.com/JudgeOnline/problem.php?id=2804
闲的DT去写了一下。。。其实也不难写。。。
算法么也就那样。。。预处理出所有C(52,5)种牌的组合，然后将他们按大小排序，对每个我可能的牌，算出有多少个在它之前的牌与它没有重复元素，使用容斥计算就行了。。。
常数有点虚。。。预处理牌的时候尽量写的靠谱一点。。。用两个数分别压位表示点数和花色。。。然后一个type一个type的处理。。。
容斥的时候么。。。裸Hash似乎会T。。。对所有组合编个码好了。。。
code：
A:裸贪心
B:bfs,不妨令当前到了(r,c),如果存在令一个到过的格子(r’,c’) , (r%n,c%m) == (r’%n,c’%m),那么就可以无限走远,不然No.
C:构造,注意要使用极角序!!!!尼玛我比赛的时候写错了…
D:注意到只需要不要有长度为d或d+1的回文串即可,那么一个当前位置最多就2个字符不能选,只要找到第一个可以修改的位置之后后面就直接构造就行了.
E:显然要对于两个portal a,b,令他们间的边权为a,b在图中的最短距离,然后建MST.
注意到暴力显然不靠谱,我们脑补一下,可以感觉出只有"相邻"的portal要连边,
所谓的相邻就是存在一条边e(a,b),a离portal x最近,b离portal y最近,那么就给x – y连一条边.
一开始弱逼到B都不会做…
D一开始写错了,最后发现的时候一顿狂改差了30s没来得及交…
C傻逼了…
最后TM还掉rating…哭了…
