Match

Match

Time Limit:5000MS  Memory Limit:65536K
Total Submit:11 Accepted:7
Case Time Limit:1000MS

Description

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了。

TCO Final 2010 题解

首先这个题解基本上是看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]维修数列——囧。。

其实这题是没神马好讲的。。关键是程序风格神马的。。
我决定不盲目模仿开哥,探索一下自己的风格。。
首先我觉得开哥的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。。。

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

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

真囧。。。
今天去了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 。。。。。

数据结构————傻叉表

我某日在颓废的时候突然思索出这个傻叉的数据结构。。。可以在比O(N)小的时间内在线支持几乎一切询问(不能修改)。。。
但非常的傻叉。。。。
比如说考虑这个问题。。给出一个数列,每次询问从第l个到第r个中有几个不同的元素。。
。。。一定要在线。。
那么。。我们把这个数列分成L块,然后对每个第l块到第r块这样的子序列储存一个当前的结果。
然后计算的时候。在能使用的信息基础上,可以在O(N/L)的时间完成询问,然后再恢复。。
注意到需要的空间和预处理时间是L^2N的。。。所以L不能取很大。。比如说取个N^0.25次方。。
就能在N^1.5完成预处理,N^0.75完成询问了。。。
这。。。似乎对几乎一切的问题都适用。。。但速度可以去死了。。

囧。。尝试了下开哥的程序写法。。。

题目是这个。
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1975
裸的K短路,A*就可以了。。。
我上次由于代码风格过差被T神骂了。。所以去Orz了开哥的代码。。。感到压力非常大。。
就把我写的这个贴出来吧囧。。。

总的来说感觉还不错。。不过就是觉得把所有函数定义和主体分开来写工程的时候是很好。。但搞OI就有点囧了T_T。。
http://www.ideone.com/lDlIh

ZOJ Monthly, October 2010 题解

尽管比赛的时候还是很多题不会做。。不过上了nimendongde这个号看了lichao神犇和gaoxin神犇的程序之后。。总算全部都会了囧。。。
Orz Sro Orz gaoxin&lichao神犇
A,纯模拟题。。直接上就好了。。但是我一开始用cin TLE,然后改成C的后不知道哪里写二了WA囧。。
最后是gaoxin神犇做的。。我太弱了囧。。。
B,纯数学题,我一开始做WA,最后是lichao神犇A的囧。。
设上面切了A次,侧面切了B次,克隆了C次,
那么A+B+C=M
(A==0?1:2A)*(B+1)+C=N
若A为0,那么得到N=M+1。。显然此时答案为0。。
若N<M+1。。那么由于每次操作之后块数增加。。。显然是无解的。。。
那么现在A>0
解得:
2*A*B+A-B=N-M.
考虑配平。。
(A-1/2)(2*B+1)+1/2=N-M
(2A-1)(2B+1)=2N-2M-1…
然后就nimendongde了。。
枚举右边的因子。。。
C:
按最短路建图,可以发现求是求一个ACG中经过一个点的路径数。。
然后设in[t]为0->t的路径数,out[t]为t出发点路径数.
那么in[t]=Sum{in[i],有边i->t}
out[t]=Sum{out[i],右边t->i}+1。。
然后乘起来就OK了。。
注意10^10*10^10会超long long
a*b=2*a*(b/2)+a*(b%2)。。。
于是二分的乘法(这。。。)就可以避免爆long long了囧。。。
D:
非常恶心的计算几何,gaoxin神犇太强了。。硬是A掉了Orz Sro。。。
各种麻烦。。。
E:
首先将所有trap按Di排序,然后一个个处理,记录当前消耗时间的和now,
每次遇到一个trap,如果它加进去之后now超过了它的D。。
那么就把当前要修复的所有trap中花费时间最大的给删掉。用堆来维护就可以了。。
F:
很简单的DP。。就是要高精度。。
然后注意到要输出约化的分数,由于分母是b-a+1的n次方。。这个玩意的质因数不多。。
一个个的两边都除过去就可以了。。
我用Java强A掉了囧。。。
G:
注意对一个ai,我们的di肯定是它的因子,然后一个数的因子数一般是比较小的,所以我们可以枚举。。
然后考虑一个di,我们需要知道在x到y有多少数t
最大公约数(ai,t)=di。。
这个可以用容斥原理解决。。
具体的说就是设F(n)表示x到y之间有多少数与ai的最大公约数为n。。
那么F(n)=x到y之间n的倍数-Sum{F(m),m是n的倍数}。。。
算出这个就可以直接DP了。。
H:
这个太囧了。。
要各种分情况讨论:
设a<b
a=0 b=0:此时就是一个点,该点的情况决定一切
a=0 b>0:此时是一维的情况,就是满足条件的线段长度/线段总长度b
a>0 b>0:此时是二维的情况,画出图来可以发现是两条线去切一个矩形。。。
还有一点。。。就是当答案=0的时候。按上面这么写甚至有可能输出-0.000000
这。。。。
I:
计算几何的水题。。不多说了囧。。。
J:神犇题啊。。。gaoxin和lichao神犇的做法太强大了。。严重Orz!!!!
首先考虑O(n)的做法。。
注意到可以列期望方程F[n]=pre*F[n-1]+nxt*F[n+1]+1
pre和nxt分别是向前和向后走的概率。。
那么解方程就是n^3了。。
但这题跟上次CF的某题很像。。这个矩阵是一个Tridiagonal_matrix
http://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm
所以可以O(n)求解。。
然后测试组数过多。。。O(n)TLE囧。。。。
n=2的情况很很囧。。
可以发现m=2的情况关于n成二次关系。。是一个n的二次函数。。
若m>2
设F(n,m)为答案
然后神犇们似乎是发现当n变大了之后F(n+1,m)-F(n,m)快速趋向于常数。。。
所以只需要计算很少的n。。当这个常数变的足够稳定之后。。就可以直接给答案了。。
复杂度不清楚。。但0msAC了囧。。。

ZOJ Monthly, October 2010


哇咔咔。。我们队A光了所有题目!!!!!
比赛前。。我跟高欣神犇和李超神犇组了个队。。队名就叫nimendongde嘿嘿。。。
然后去参加比赛。。
我一开始去做B。。然后各种WA。。又去写A。。还是各种WA。。然后我囧死。。
然后李超神犇去做B。。A掉了。。我连A都写错囧的要死。。后来高欣神犇去A掉了A..
不过我也造成了巨大的罚时。。。幸好没别的人AK囧。。
然后高欣神犇发现I是水题,就A掉了。。
同时高欣神犇也A掉了E。貌似是道几何题。。。接着我发现F似乎是道水题,不过需要高精度,就写了Java。。1Y了。。
然后我去做C。。发现是个图论的XX题。。于是强A。。
但我发现似乎这题有点猥琐。。因为10^10*10^10会超long long。。
幸好a*b=2*a*(b/2)+a*(b%2)。。
所以可以二分做乘法
然后J是道非常BT的题目。。我是毫无思路。。李超神犇有O(n)的做法。。但是会TLE。
一直也没有神马好点的办法。。李超神犇最后还是A掉了。。太神犇了Orz!!
接着我去作G。。。一开始没有处理好。。
导致TLE。。不过最后通过各种努力。。还是A掉了。。
gaoxin神犇则一直在写D。。一道非常XX的计算几何题。。
但是因为精度神马的问题。。一直在悲剧。。
最后换成long double。。于是A掉了。。
当时我们队8题。。有队9题。。。时间已经不多了。。
然后是J题。。。李超神犇在最后关头A掉了。。方法我也不知道囧。。
然后H题是XX的几何。。非常恶心。。有各种XX的特况。。我WA了好几次也终于A掉了。。。
然后在还剩几分钟的样子我们AK了。。
。。话说三道Special Judge的题目全是我A的囧。。是不是因为我常上SPOJ的缘故囧。。。

Page 2 of 41234