Monthly Archives: January 2011

WC2011

Posted on by

    在这么冷的地方>_<。。。讨厌死了>_<。。。。当面Orz了各种神犇，好高欣啊~~~~~~~~~~~

    。。。。最后的比赛悲剧的一塌糊涂T_T。。。

   。。。我似乎前两个小时在写第一题的错误算法。。。最后只能交20%。。。。>_<。。。明明就不靠谱的写神马嘛T_T。。。

   然后第二题想做部分分。。。写了CQX讲的线段树然后TLE了一堆。。。不过似乎没看清题目然后最后发现还能暴力骗点分的。。最后15分钟狂敲暴力骗分。。。似乎写错了>_<。。。。没救了55555555555555.。。。

   第三题做的时候被没多少时间了。。。裸随机化乱搞骗了50分。。。。啊啊啊啊。。。。我这么弱还是去混高考啊。。。没救了‍

notes….

Posted on by

1.LQP的那个题目二进制求结果确实很霸气。。。但其实还有更囧一点的办法。。
考虑一个经典问题，就是给你n个数和两个格子，每个格子只能记一个数，然后求这堆数中出现超过n/2的那个数。。
这个是可以搞出来的。。具体的说步骤是这样的，
记录 一个数a和一个计数器c。。
考虑下一个数b，如果a==b，那么c++

如果a!=b，如果c>1，那么c–，否则将a替换为b，令c为1。。。。
这个的证明是很显然的。。因为其它所有的数也不能吧这个出现次数最多的数消掉。。
所以最后的数必然是这个出现次数超过n/2的数。。
那么。。最关键的一点是。。这个是可以合并的。。
那么我们用Lca算法就可以搞出所有询问的可能的那个答案。。
然后验证。。。。

可以用Tarjan搞。。。

验证我也有一个很那啥的方法。。。具体就是对所有相同权值的点。。提取出来。。。。可以建成一棵树（可以看成忽略其他权值的点没有价值。。那么很多节点都可以缩在一起，同时有一些0权点去啊）。。可以通过dfs的办法在搞出所有这样的树。。然后离线所有询问。。可以得出每个节点在那些这样的数中第一个祖先，然后出现个数就是这两个节点的第一个祖先间长度和。。
就是Tarjan。。。

于是可以很复杂的用两次Tarjan搞定。。复杂度为O（N*a（N）），a为某函数的反函数>_<。。。。

复杂度似乎好了一点。。编写的话好像复杂了一点。。不过也不是很难写。。。。

 

2.Stone的那道有些相似的题似乎是POI2009的Lyz?我做过啊。。。

可是还是没想出来。。。太弱了T_T。。。。

 

3.JZP教主的题目似乎还有NLog^2N的算法。。。。如果树分治的话。。

关键的问题说白了就是给一些有序数组，然后求所有数的第K大。。。

这个问题。。。有一个论文算法是Log（总大小）*数组个数的。。

然后放到这个题目里面似乎就是N*LogN*LogN。。。

（。。。。。但那个算法似乎只有理论价值>_<。。。。。太BT了。。。）

 

不过也有一个比单纯的二分答案好很多的算法：
具体是维护所有有序数组的中点，
那么如果当前Kth>=Size/2。。那么最小的那个中点的前面是没用的。。删掉前面那些。。

如果Kth<Size/2。。那么最大的那个中点的后面是没用的。。。删掉后面那些。。

然后需要删Sum（Log Size[i]）次。。。
同时维护的代价是Log Log(N)。。。

Sum（Size[i]）=N。。

Sum(Log(Size[i]))=

Log(Mult(Size[i]))<=Log(N/Log N)^LogN)=

Log(N/LogN)*LogN。。。

 

Mult(S)表示集合S各个数相乘。。。。
那么复杂度就是Log(Log(N))*Log(N/LogN)*LogN。。。

比Log^3N的那个要好一点囧。。。。

@Update:lqp那题的证明：

设出现最多的数的出现次数大于一半，设其为x

令S表示一个序列，F(S)表示该序列的权值（见后面的定义），G(S)表示该序列中x的个数-不是x的数的个数。。

假设通过合并，S这个序列对应的二元组是a和c

令F(S)= c (a=x)

         -c (a!=x)

我们只需要证明F(S)>=G(S)。。

由于G(所有数)>0，故F(所有数)>0,既最后的a是x。。

使用归纳法。

首先长度为1的序列满足条件。

将S分成L和R顺次相接，

因为F(L)>=G(L),F(R)>=G(R)，

同时G(S)=G(L)+G(R)，

我们只需要证明F(S)=F(L+R)>=F(L)+F(R)即可。

考虑合并的过程，

令L对应的二元组为aL和cL，

R为aR和cR。。

若aL=x并且aR=x，那么F(S)=cL+cR满足条件

若aL和aR中有且只有一个不为x。。

那么F(S)=F(L)+F(R)满足条件。

若aL和aR都不等于x。

那么F(S)=-|cL-cR|>=-cL-cR=F(L)+F(R)。。

故归纳命题成立，由归纳法只F(S)衡大于等于G(S)。

CF 51

Posted on by

这次比赛。。。我吸取教训。。。踏实做题。。。
终于做到了交了的都过了。。。真高欣啊。。。
。。最后rank 9。。。rating狂涨又变红了。。。。。
A：是个送分题。。有O（N）的做法。。不过在比赛的时候显然直接模拟10^7次就差不多了。。。
B：爆搜。。。
C：忽悠题。。。自己多试几次可以发现只要有个棋子跟边缘的距离小于等于4。。那么必然能弄出去。。
E：USACO和APIO的原题？乱搞就行了。。。。。
D：数位统计Dp。。注意一点，如果要记录mod 8*9*5*7=2520。。。可能就要MLE了>_<。。
解决的办法是注意到mod 10只跟最后一位有关。。那么只需要记录mod 252的值就行了。。
同时没有必要记录用过的数位。。。它们只有最小公倍数是管用的。。。
那么状态就是长度，用过的数位的最小公倍数，mod 252的值。。。。
可惜我写了一半的时候被我爸拉去吃饭了哎T_T。。。。

增强型LCP

Posted on by

增强型LCP

Time Limit:10000MS  Memory Limit:165536K
Total Submit:21 Accepted:3 
Case Time Limit:1000MS

Description

 

Input

 

Output

对于每个Lcp(a,b)操作输出最长公共前缀

Sample Input

47 abab L 13 A 1 ab L 1 3 C 56 cb L 1 3 D 1 2 L 1 3

Sample Output

2 4 2 0

Source

看这个规模和时限Splay维护Hash值显然不靠谱。。
关键是修改操作很少。。于是我们平衡一下。。
那么就用块状链表吧。对每个块维护一个hash数组。
假设长度为N，分成S快。。那么可以在O(S+Log(N/S))的时间求出Lcp。。。
同时修改是O(N/S)的。。。
由于修改很少。。把S改的很小就可以让效率大幅提高。。。
由于本人代码能力太差。。就不写了T_T。。。
开哥就是用块链A的。。Orz啊！！！！！！

CF 50

Posted on by

。。。。悲剧了。。。rating跌停。。。直接变黄55555555555555

。。。。fail了两题。。
‍
@Update：
总结：。。悲剧了就悲剧了。。要吸取教训！
B：。。。居然是因为题目看的不仔细。。把面积最小看成了x最小然后y最小。。。
5555555555555555555555555太傻叉了。。。。
D：。。。。完全是在乱做啊。。。胡乱构造怎么行呢555555555555555我是不是脑残啊。。。
好伤心。。。求安慰。。求抱抱。。。

SRM 460 Div I…一种数学方法

Posted on by

。。。这个题目的官方题解还是很霸气的。。。复杂的动态规划。。。

但其实也是有比较简单的数学方法。。。

题目：http://www.topcoder.com/stat?c=problem_statement&pm=10773&rd=14146

题目简述：给一个图，里面每对点之间最多有两条简单路径（可以没有）。。

让你加入一些边。。使得每对点之间都有1或两条简单路径。。。

求加入边的方法数（顺序无视）。。。

首先。。可以发现结果的图最多只有一个环。。。

考虑结果无环的情况。。也就是当前就没有环。。

然后考虑目前的联通分量..设大小为v1,v2,v3。。。。vM。。。

那么把联通分量看成一个点。。考虑这M个点之间所有的生成树。。

考虑一个特定的生成树。。

设vi的度数为di。。那么这个情况对结果的贡献就是所有vi^di的积。。

根据prufer-code。。这样的可能性的个数是C(M-2,d1-1,d2-1,d3-1…dM-1)。。

C(N,a1.aM)表示把N个数染成M种颜色，第i种颜色有ai个的情况数。。。

把所有结果都+起来。。

那么答案就是。。

Mult(v1..vM)*Sum(v1..vM)^n-2
Mult表示括号内所有数的和。。。

。。。然后考虑有环的情况。。

有两种。。一种是环在一个联通分量内部。。这很好解决。。

还有一种是环在联通分量之间。。

那么枚举环上的元素是哪些。。把这些元素看成一个大的节点就可以了。。。