>.<此题没啥好说的，二分答案+最优性剪枝+DLX。
纯粹为了存模板。
BTW,看别人代码收获真的好大。
分类存档：默认分类
[ZOJ3209 Treasure Map] DLX解决精确覆盖问题中我的一个错误>.<
HHGG出的题T_T。
本身题目没啥好说的。很容易转化为精确覆盖。
但是我之前的DLX模板超时了。
好吧，那个在HUST1017上跑了4S的模板果然是不能用的。
然后，我照着hh(the small one)的模板YY出意思然后写了一个。HUST上…还是跑了1500+MS.这题还是TLE。
我记得之前那篇CLJ留言鄙视说暴力开指针都600+MS…
我再看了好多遍，觉得和hh的没啥区别嘛…为啥人家说200+MS
好多遍好多遍以后…我突然看到了一个不一样。
hh的：
回溯部分：
for (int j=L[i];j!=i;j=L[j]) resume(Col[j]);
resume函数部分：
for (int i=U[col];i!=col;i=U[i])
for (int j=L[i];j!=i;j=L[j])
我的
回溯部分：
for (int j=R[i];j!=i;j=R[j]) resume(Col[j]);
resume函数部分
for (int i=D[col];i!=col;i=D[i])
for (int j=R[i];j!=i;j=R[j])
然而，我的其实犯了一个错误。
Dancing Link其实必须按照删除的先后顺序，依次恢复的。
比如删除的顺序是i,j，恢复的顺序就应当是j,i。举个例子就能知道原因
HUST的1017上
在for (int j=L[i];j!=i;j=L[j]) resume(Col[j]);这种方式下。无论resume函数里随便用ULDR都可以240MS左右AC。
而for (int j=R[i];j!=i;j=R[j]) resume(Col[j]);这种方式下。resume函数里如果用D可以1500MS AC。然后，如果是U的话就runtime error了。可见这种方式确实是错误的>.<
恩，终于搞了一个能用的精确覆盖模板了。
以后把mat和Num建好，一刷就好了
需要注意的是代码里，为了方便和速度，把二维点映射到一维上了。
Codeforces Beta Round #75 Div 1 (D无思路..)
A
就是加个Next[i][26]的数组来转移，基本上理清题意以后，5分钟内都出想法了吧
B
按a[i]排个序，然后顺序扫描，看最后的是谁就行了。= =脑抽写了线段树，本身线段树的话也不会写多久，但是又跑去尝试新写法。。。然后就写了巨久。。。
C
这个，看了watashi的代码，想了一下。
首先就是如果一个边集能符合题目，充要条件是每个点度数为偶数。
每当添加一条边连接两个不连通的块时，不可能会存在新的欧拉回路通过这条新加的边。所以显然答案不变。
而当添加一条边连接了两个本已连通的块时，假如是一开始只有一条边，答案必然还是0，然后接下来，每次出现这样的边，ans+=2^(k-1)。其中k代表这是第k条连接已连通的两个块的边。
为什么会这样呢？从结论往回看。。。本身的ans是不包含新加边的方案数，而2^(k-1)是包含新加边的方案数。
假设用一个mask代表那k-1条边的使用情况，那么极有可能是每个mask都对应了一种且仅一种方案。
继续YY
除去所有这k条边以后，其实图上是几棵树组成的森林！
然后假定现在这个第k条必取、、、然后前面k-1条组成的每个mask确实就唯一地对应了一种方案。
也就是说假设mask确定，我们森林边的取舍情况也就确定了。这个自行YY一下，明白过来会发现很显然
D
不会>.<
求指导。
E
这种放在省选NOI什么的就是送分题，裸考线段树
就是建一棵线段树，然后线段树每个节点里套一个线性表，以前我写这种比较疼，现在用vector简直好写到爆。。。
然后这个线性表的内容嘛，就是随着t的增长，看看这个线段里的老大是谁。
大概就是表示这样更替情况的一个队列。
然后嘛，假如区间里有i,j满足a[i]<=a[j] && b[i]<=b[j]，那么i肯定就没用了。
剔除这些以后，按a[i]递减排序，变成了b[i]递增的序列。(我的Code中的Select())
然后就是利用决策单调弄这个队列了。由于b[i]递增，所以随着t的递增，必然是越来越倾向于选后面的。
我们现在构建一个栈，使得栈内元素满足Meet_Time(Q[i],Q[i+1])>Meet_Time(Q[i],Q[i-1])，其中Meet_Time(x,y)就是使得a[x]+b[x]*t=a[y]+b[y]*t的t值。
这个很容易扫一遍得出来。(我的Code中的Form())
构建完以后，对于每个询问l,r,t。
直接在线段树里找到l,r对应区间，然后可以三分得当前的t对应的老大是谁(我还是写得二分，Code中的Get_Best())。
按Solution Size排我的还是比较靠前的= =，我也觉得写得还是比较清楚，于是推荐一下。
时间复杂度O(n lg^2 n + q lg ^2 n)
【CODE】http://ideone.com/Aga48
【update】
按照猛犸学长的指示，构造部分可以通过归并排序避免那个sort的调用。
后面可以先对答案排序，然后用指针滑的方法得到均摊的n lg n。
于是总时间复杂度可以做到O(n lg n + q lg n)。
[POJ1635 Subway tree systems]【判有根树是否同构】【例题】
>.<最近在补一些知道的，又不会的东西。神牛们就不要鄙视了。
就是最小表示法+hash。
用YY论文的做法。
对每个儿子的hash值排序以后，再通过(ret*p)^Hash[i]的方法弄出当前点的hash值。
啊呜～家里居然上不去uva了。
【CODE】
【转】GDOI结束。
今天刚刚从韶关回来。3天的GDOI结束了
前两天是比赛 第三天是闭幕式
这次比赛。足够证明我的心脏还不够强大- –
第一天各种rpoi。数据有点假。发挥还算正常。
第二天带着压力去比赛。不仅水题没有切掉、骗分的程序时候才发现有各种小错误。各种爆0
看到总成绩的时候心里很不踏实。
广东今年选前15
而我刚好第15名。但是有1个同分的。
就是说我们2个只能取1个。
结果是面试。
还好吧。心理素质还算可以。而且前一个寒假去了hk培训了一个面试的基本技巧。
没有压力地应对。
At last…..
最后一名进省队- -Orz….rp++
听老师说他打算休息一段时间了。
暑假也不给我指导了- -55555
不过貌似听他说、叫我去cwj家住一个假期。
跟师兄学学备战noi.
that’s all noi.加油！