>.<最近在补一些知道的，又不会的东西。神牛们就不要鄙视了。
就是最小表示法+hash。
用YY论文的做法。
对每个儿子的hash值排序以后，再通过(ret*p)^Hash[i]的方法弄出当前点的hash值。
啊呜～家里居然上不去uva了。
【CODE】
作者存档：edward_mj
【转】GDOI结束。
今天刚刚从韶关回来。3天的GDOI结束了
前两天是比赛 第三天是闭幕式
这次比赛。足够证明我的心脏还不够强大- –
第一天各种rpoi。数据有点假。发挥还算正常。
第二天带着压力去比赛。不仅水题没有切掉、骗分的程序时候才发现有各种小错误。各种爆0
看到总成绩的时候心里很不踏实。
广东今年选前15
而我刚好第15名。但是有1个同分的。
就是说我们2个只能取1个。
结果是面试。
还好吧。心理素质还算可以。而且前一个寒假去了hk培训了一个面试的基本技巧。
没有压力地应对。
At last…..
最后一名进省队- -Orz….rp++
听老师说他打算休息一段时间了。
暑假也不给我指导了- -55555
不过貌似听他说、叫我去cwj家住一个假期。
跟师兄学学备战noi.
that’s all noi.加油！
[BZOJ1006 [HNOI2008]神奇的国度]【弦图】
【题目大意】
给一个弦图。问色数是多少。
【算法】
先是有显然的定理：色数(用最少种颜色涂满图中的点，使得每条边两端的点颜色都不同)>=团数(最大团的点数)
因为是弦图，由完美消除序列的性质可以构造得色数=团数，于是达到下界。
于是直接利用完美消除序列的性质求出团数即可。
【其它】
完美消除序列的性质是：
对于序列中第i个点Vi。
令S={Vj | (j>i) && ((Vi,Vj) in E)}，那么S+Vi成一个团。
>.<还是V^2。虽然O(V+E)也不难写。求不鄙视。
【CODE】
[ZOJ 1015]【弦图判定】【例题】
>____<觉得必要记录一下。
使用WC2009 CDQ PTT的最大势方法标号，然后check。O(n^2)的。
【弦图】不存在环满足(长度大于3)&&(环上任意非相邻点间无边) 的一个图。
【CODE】https://ideone.com/8QX5e
[Practice]SRM 490 DIV I
>.<深切感受到自己蒟蒻。
250题意
N,M<=10^9
i=N;
j=M;
while (j<=lcm(N,M)){
while (i ans+=j-i; j+=M; } return (double)ans/(lcm(N,M)/M);(平均数) 、 然后发现其实每次j-i都是gcd(N,M)的倍数，设g=gcd(N,M)，然后j-i刚好是0,g,2*g,3*g,…,(lcm(N,M)/M-1)*g 、 lcm(N,M)/M=N/g 于是ans=(N/g)*(N/g-1)/2 * g / (N/g) 然后最终代码是
int gcd(int x,int y){return y?gcd(y,x%y):x;}
double Starport::getExpectedTime(int N, int M) {
long long g=gcd(N,M);
long long t=N/g;
return g*(t*(t-1)/2)/(double)(t);
}
550
弄完以后交FST了….
题目大意就是给定一组字典，再给出一个字符串，让你用手机T9的方式最少要多少次按键把字符串打出来。
对我来说很考验coding啊>.<...
思路不太难，就模拟每次弄一个字典里字符的前缀。然后由于是类似栈的形式，只能从后面删和插入，所以可以F[i]表示前i个弄好最少多少次按键，然后弄个邻接矩阵mat[i][j]表示两两状态间转移最少需要多少步.
最后来个floyd就OK…
个中细节和处理技巧多多= =，请自行体会。。。
2Y。
被屠什么的，无所谓的。