完全动态最小生成树维护问题。。

PP发明了一种新的串匹配！
给出一个长度为N的整数串A，和一个长度为K（K<=N）的整数串B，A和B中的元素均是不大于S的正整数，我们认为两个串是相等的，当两个串的长度相当，并且两个串中，对于任意的i，第i个元素在两个串中的排名是一样的。
例如：
1 2 3 5 4
8 10 23 25 24
这两个串是相等的。
现在要求在A的所有长度=B的长度的子串中，有多少子串与B串相等。

Input

第一行三个整数N，K，S。
第二行N个整数表示A串。
第三行K个整数表示B串。

Output

第一行一个P表示A串中一共有多少个子串和B串相等，
接下来P行从小到大每行一个整数，表示和B串相等的A串的子串的第一个元素的位置。

Sample Input

9 6 10
5 6 2 10 10 7 3 2 9
1 4 4 3 2 1

Sample Output

1
3

数据规模：
对于20%的数据N<=10000
对于100%的数据N<=500000，S<=10000

Source

By Mt

这个题目看到之后的第一想法是扩展性的匹配问题。。
那么自然是要改造经典算法了。。
RK算法。。想了一会儿觉得不太靠谱。。
KMP算法。。
KMP算法的使用条件是。。
空串只能等于空串。
两个串相等，那么他们的任意等长前缀也相等。。
这个在此题中是成立的。。
那么我们只需要算出前缀函数。。然后KMP一遍就解决了。。
因为计算前缀函数需要快速知道两个原本相等的字符串，各自+上一个字符之后是否还是相等。。
那么也就是说要有能力计算出一个子序列最后一个字符在这个子序列中的排名。。
这。。。
似乎是划分树的经典应用。。但用划分树是不是太囧了一点？
线段数LogN^2估计会超时。。
那么只好观察一下问题看看有没有神马区间的特殊性质了。。
可以发现需要进行的询问有两种。。一种是在开头处进行。。为A[0…p-1]中有几个数比A[p]小。。扫描一遍就可以了。。
还有一种在KMP过程中的询问。。左右端都是单调递增的。。。
OK了。

SRM199 ClosestPoints

Posted on October 21, 2010 by wjmzbmr

随机分布的三维最近点统计问题。。
注意到点是随机分布的。。弄个KD树瞎搞。。。

TCO Final 2010 题解

Posted on October 19, 2010 by wjmzbmr

首先这个题解基本上是看Petr的分析和rng_58的代码。。
题目自己去看TC看吧囧。。
第一题：
此题看上去很容易。。其实很恶心。。各种贪心很容易悲剧。。
最好的办法是用对偶原理
就是最小必定可行值=最大不可行值+1
我们只需要通过DP求得最大不可行值即可。。
状态可以是Dp[i][win][lose]表示前i个位置，win个位置取得了胜利，lose个位置挂掉了的最大投票数。。
然后DP出这个玩意。。。
再以此求出最大不可行值就可以了。。
第二题：
这个题目很囧。。由于机房要关门了。。晚上再发。。
第三题：
首先显然对于一个特定的取方格的方式，只有RGB的数量有关系。。
然后欲处理一下。。枚举出所有可行的R，G，B的数量。。
然后我们枚举R，G的数量，设Max[r][g]为R选r个，G选g个，B最多有几个。。
那么如果我们无视那个两个串翻转之后一样算一个的条件。。
设Max[r][g]=b
那么在这种情况下。。答案为C(r+g,r)*(C(r+g,0)+C(r+g+1,1)+C(r+g+2,2)…+C(r+g+b,b))
那么看右边(C(r+g,0)+C(r+g+1,1)+C(r+g+2,2)…+C(r+g+b,b))
。。这式子只跟r+g和b有关系。。所以随便预处理一下就OK了。。
然后考虑翻转的条件。。只要算出所有对称的字符串的数量就OK了。。
而对称的字符串由前半部分决定。。。
用一样的办法就可以了。。
注意一下处理长度的奇偶性。。。
//嘿嘿。。我是WJMZBMR的分割线
看了这些题目之后。。我感觉TCO的难度其实是不及NOI的。。。
由于时间限制的原因，TCO的题目也不会考那种特别难的算法或者数据结构。。。
但是题目还是很考验各种能力的。。rng_58确实是强到极点了。。Orz Sro Orz。。。
我决定去看看他之前在各种SRM和TCO中的代码。。。从中吸取经验囧。。。
//嘿嘿。。我是WJBZBMR的分割线。。
其实。。我打算再去弄场模拟赛。。大家说是搞成ACM形式放在BZOJ上好呢？
还是搞成OI形式放在TYVJ或者RQNOJ上好呢？

[NOI2005]维修数列——囧。。

Posted on October 17, 2010 by wjmzbmr

其实这题是没神马好讲的。。关键是程序风格神马的。。
我决定不盲目模仿开哥，探索一下自己的风格。。
首先我觉得开哥的namespace非常神犇。。但我觉得把主体和定义声明分开总归有点不爽T_T囧。。
所以我还是用了namespace。然后我直接在namespace里面写程序。。就不分开了。。
然后我写了一些库。。比如
namespace Constant
{
const int ND_MAX=500000+10;
const int inf=~0U>>2;
const int CM_MAX=100;
}
namespace Function
{
inline int Max(int x,int y)
{
int m=(x-y)>>31;
return y&m|x&~m;
}
template<class T>
inline void Swap(T&a,T&b)
{
T c=a;a=b;b=c;
}
}
namespace Scanner
{
inline void scan_str(char*s)
{
char c;while(c=getchar(),c==’ ‘||c==’n’);*s++=c;
while(c=getchar(),c!=’ ‘&&c!=’n’)*s++=c;*s++=’’;
}
inline void scan(int&t)
{
int sign=1;char c;
while(c=getchar(),c<‘0’||c>’9’)
if(c==’-‘)break;
if(c==’-‘)t=0,sign=-1;
else t=c-‘0’;
while(c=getchar(),c>=’0’&&c<=’9′)t=t*10+c-‘0’;
t*=sign;
}
}Scanner的名字来源于Java囧。。
然后要用的时候就using一下就可以了。。
然后为了感觉一下这种编程方式。。
我决定去A这道XX的Spaly维护题。。。（裸的数据结构神马的，最喜欢了）
写了很久。。
1A嘻嘻。。。（第一次交的5KB那个没写完。。纯属保存代码囧。。）
Code非常囧。。写了10KB+。。见网盘。。

数学联赛_End。。。

Posted on October 17, 2010 by wjmzbmr

。。我似乎打文章名都有OI的风格了这。。。
数学联赛似乎RP不错。。。尽管我已经几乎N久没有碰数学了。。。但对那个组合和数论的题目还是有点感觉囧。。
然后考试的时候1试挂的很惨。。很多题目都跳着做。。解答错了2道。。刚刚看了答案之后一对是68的样子囧。。。
2试的时候本来我是想全不会做然后打酱油提前交卷的。。结果发现组合题很水。。于是我弄了一会儿A掉了。。
然后我就想我反正几何代数都不行。。于是就去试图做数论。。发现也是水题这。。。
然后我直接在总分中扣除了几何题的分数（就是无视掉了囧。。）去做代数。。。
其实那题感觉还是挺可做思路很多的。。但是由于我过于傻叉。。证了半天以为自己没错。。。
到快结束的时候发现我那么证有漏洞。。。修复了半天发现必须要n>=10（这。。。）。。。
于是我只好写:手工验算得，当n<10时结论成立。。
。。。。。。。。。。。。肯定0分。。。。
总哦那个也就90+68 150+的样子了T_T。。得奖是没戏了囧。。
Orz 豪哥虐爆全场无压力200+
Orz 高远神犇虐爆全场无压力200+。。

好吧。。。初赛我悲剧了。。。。

Posted on October 16, 2010 by wjmzbmr

真囧。。。
今天去了14中参加了比赛。。然后发现14中门口有一个巨大的屏幕在播出一些宣传片，其中就有Lou Tian Cheng Win The First Price In IOI.。。果断Orz楼教主，然后14中还有2个人生物拿过国际金牌啊。。Orz。。。。。。
然后来的有点早。。。于是就想去见一下学军的gaoxin和lichao神犇，不过惊讶的发现没有学军的考场是设在图书馆囧。。然后就没找到T_T。。快开始的时候在考场里进来了两个帅哥（事后知道是gaoxin和lichao神犇。。）。。我居然没有认出来。。这。。太囧了。。话说两个神犇长的都很帅啊。。Orz Sro Orz。。。。
然后又见到了杭二的某个猥琐男WQX。。这家伙物理都1=了还来混NOIP。。Orz囧。。。
然后考试。。。
这。。我太SB了。。由于去年初赛选择题挂了N道，后面还可以。。于是考试前完全没有复习过程序填空神马的。。。就是仔细复习了一下各种知识。。。。。
然后我就悲剧了。。求答案第三题我SB的写了17。。。没有多想。。我的数学是不是白学了囧？
然后看程序写结果也错了一题。。。程序填空也错了个。。让我去死吧。。
单选很信春哥的全对了。。但多选错了一个囧。。HTTP完全不会T_T。。。
Orz NZK神犇96.5 GX神犇92.5 。。。。。