2124: 等差子序列 - #include <Seter> - using namespace Orz;

2124: 等差子序列

Seter posted @ 2012年1月31日 20:20 in BZOJ with tags Hash SegTree , 5668 阅读

http://www.zybbs.org/JudgeOnline/problem.php?id=2124

RunID User Problem Result Memory Time Language Code Length Submit Time
197295 Seter 2124 Accepted 1988 kb 212 ms C/Edit 1029 B 2012-01-31 14:58:41

这道题挺好的,但是我怎么找不到题解呢……是神犇们觉得这题过于简单还是我查的关键词不对?

题意是,给定10000个数的排列,问是否存在长度为3的子序列[tex]$A_{x1}$,$A_{x2}$,$A_{x3}$[/tex],使得[tex]$A_{x2}-A_{x1}=A_{x3}-A_{x2}$[/tex]。

从数据范围估计,大概每个询问需要O(nlogn)左右的复杂度。观察到给出的数字是1~N的排列,这不止说明数字范围在1~N之内,还说明每个数出现且仅出现一次。

这个方法确实是非常的巧妙,要从诸多的嫌疑入手点中抓住这一点对于我这个弱菜来说真的非常难,在此膜拜杨天大神。

用类似离线的算法,从左到右依次加入数字,并且查询这个数字x是否可以作为等差中项。假设公差的绝对值是k,则三个数字分别是:x-k,x,x+k。如果此时,x-k与x+k两数一个已经出现过了,另一个没有出现过,则TAK了。

一个个枚举k肯定是不行的,所以做到这里很容易就会觉得这个方法不对……然后就没有然后了……


分析一下,比较的那些数字的状态分别是:

x-1 x-2 x-3 x-4 x-5 ...
x+1 x+2 x+3 x+4 x+5 ...

只要这些状态上下有一组不同(即一个出现过,一个没有出现过)则TAK。可以发现当将这串01状态看成二进制数字时,NIE的充要条件是两数相等。

如果N比较小,则算法呼之欲出:用线段树维护一段内的状态(正过去一个二进制数字,反过来一个二进制数字),然后每次比较x-1...x-k和x+1...x+k(k表示min(n-x,x),即向头尾延伸最长伸到哪里)这两条线段上的状态是否完全一样即可。

这样出现了两个问题,一个是怎么合并两条线段(这个很好想,下面也要用到),另一个是N很大,数字要变成高精度了,怎么办?


答案是……BKDRHASH……做过火星人prefix/增强型LCP的同学应该可以直接开始写代码了……

看成二进制数字不太好做,那么就看成字符串,然后HASH起来,只要HASH值一样,字符串就一样……

而BKDRHASH的好处就是可以随便乱搞,乱改,乱弄……这里不理解的同学去做做火星人prefix就可以了……

 

#include <stdio.h>
#include <string.h>
int a[32768][2],n,M;
char str[1000000],*p=str;
inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}inline void Update(i){
	int P=101;i+=M-1;
	for(a[i][0]=a[i][1]=1;i>>=1;P=P*P)a[i][0]=a[i<<1][0]*P+a[i<<1^1][0],a[i][1]=a[i<<1^1][1]*P+a[i<<1][1];
}inline Query(i,j,c)int i,j;_Bool c;{
	int ans[2]={0,0},P=101,lP=1,rP=1;
#define link(a,b,c,lP,rP) c?b*lP+a:a*rP+b
	for(i+=M-2,j+=M;i^j^1;i>>=1,j>>=1,P*=P){
		if(~i&1)ans[0]=link(ans[0],a[i^1][c],c,lP,P),lP*=P;
		if(j&1)ans[1]=link(a[j^1][c],ans[1],c,P,rP),rP*=P;
	}return link(ans[0],ans[1],c,lP,rP);
}main(){
	int t,i,s,k;fread(p,1,1000000,stdin);
	for(t=getint();t--;puts(i==-1?"N":"Y"))for(memset(a,0,(M=1<<32-__builtin_clz((i=n=getint())-1))<<4);i--;Update(s))if((s=getint())!=1&&s!=n){
		k=s-1>n-s?n-s:s-1;
		if(Query(s-k,s-1,1)!=Query(s+1,s+k,0)){while(*p++!='\n');break;}
	}return 0;
}
By Seter
Avatar_small
EVA-01 说:
2012年2月03日 09:02

orz Seter 神犇的线段树就是快!

simoncao 说:
2012年2月10日 00:51

因为太弱了所以没题解(其实是因为国家队作业满大街都能找到集合包?)

Avatar_small
Seter 说:
2012年2月10日 08:27

囧 说明我太弱了……

sillyrobot 说:
2012年7月26日 12:57

NOI 导刊的奇葩培训上扯到了这个。。。注意只是扯到了。。。
于是我一通乱搜之后还是找到你这里。。

我们的题目非常沙茶。。。。
求一个 1 至 n 的排列,
使其不存在任何长度为 3 的等差序列。
比方说 N=8 时答案可以是 <1,5,3,7,2,6,4,8>。

解法:
首先将 1 至 n 按奇偶分开,
奇数都放在左边,偶数都放在右边。
这样可以保证没有横跨左右的长度为 3 的等差序列;
递归对左右两侧进行处理即可。

接下来老师就乱扯了一堆,
说这个题目 O(N) 得解,
但是 special judge 要很艰难才做得到 O(N lg N sqrt(N))。

我原以为求出一个序列中的“最长等差子序列”可以用 dp 乱搞,
但是后来醒悟过来那只是在一个集合中求“最长等差子序列”。。。
比如序列 <1,2,5,3,4> 的最长等差子序列是 <1,2,3,4>,
但是集合 {1,2,5,3,4} 的最长等差子序列是 <1,2,3,4,5>。
而且网上的题解基本上都是关于后者的。

p.s. 我这种弱菜当然不能理解您老的题解了。。。

sillyrobot 说:
2012年7月26日 13:40

现在发现 dp 的话 O(n^2) 什么都能搞。。。
而且我肯定是听错 了。。
老师肯定是说 O(n lg n) 和 O(n sqrt(n))。。。
这就奇葩了
无视我吧。。。

Avatar_small
Seter 说:
2012年7月27日 09:50

你那个题你们老师的递归显然是O(N)的啊。。

YOUSIKI 说:
2016年7月16日 20:44

神犇代码简直了 %%%%%%% Orz Seter


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee