11
30
2015
1

CERC2012的一道『暴力』题与一个有趣的递归式

 

 [Cerc2012]Non-boring sequences

 

Description

我们害怕把这道题题面搞得太无聊了,所以我们决定让这题超短。一个序列被称为是不无聊的,仅当它的每个连续子序列存在一个独一无二的数字,即每个子序列里至少存在一个数字只出现一次。给定一个整数序列,请你判断它是不是不无聊的。

Input

第一行一个正整数T,表示有T组数据。每组数据第一行一个正整数n,表示序列的长度,1 <= n <= 200000。接下来一行n个不超过10^9的非负整数,表示这个序列。

Output

对于每组数据输出一行,输出"non-boring"表示这个序列不无聊,输出"boring"表示这个序列无聊。

由于是权限题窝就贴下题面吧。。做法可以看hgr同学的博客(http://blog.csdn.net/geotcbrl/article/details/49797889)或者是tjz唐老师的博客。。

然而窝第一眼看到这个做法的时候和hgr一样,认为这个做法是暴力。。唐老师说可以证明,问了唐老师,唐老师表示这个其实是证明

$T(n)=\max\{T(k)+T(n-k)+\min(n,n-k)\}=O(nlogn)$

然后使用归纳法证明。。。

嗯。。的确可以这么做。。但是看上去是不是不太直观啊。。

于是窝想了一个(两个?)直观的证明,是这样的:

我们考虑每个对时间复杂度有贡献的下标,它一定属于两段中比较小的那一段,于是。。每次每个下标被算一次,它的所在块就会缩小一倍,那么显然每个下标的贡献就是$O(logn)$,它的总时间复杂度就是$O(nlogn)$

 

说到底,我们不断拆分这个过程,分开后就不会再合并,而且每次拆开的复杂度就是拆成的两个序列中较小的一个,很自然地想到把这个过程倒过来,那么这就是一个启发式合并的过程,显然时间复杂度就是$O(nlogn)$啦

 

感觉这个可以叫『启发式拆分』?233 总之要注意这样的做法不是暴力,相反复杂度还很优秀。。

Category: oi题解 | Tags:
6
23
2015
0

BZOJ3653: 谈笑风生

题意(一开始理解错了的版本)
Q个询问、n个点
 
每个询问是p k
 
求 p的子树中(不包括p)有多少个二元组 (b,c) 满足:
b,c互不相等
b为c的祖先
p和b的距离不超过k
 
n<=3*10^5 Q<=3*10^5
 
 
简单思考一下可以发现如下性质:
  1. 对于任何一个满足8的b,满足条件的c的个数就是b的子树大小(不包括b)
  2. 对于任何一个在p的子树中的c,满足条件的b的个数是min(dep[c] - dep[p], k)
 
  哪个更好用?
  性质1的子树大小不变,但是b的范围是不好处理的
  性质2的k的大小是不确定的每个点的贡献不方便确定
 
难点集中在对k的处理上
 
p的子树中距离小于等于k的b?注意这里p是b的祖先,dis(p,b) 不就是dep[p] - dep[b] ?
也就是子树中dep[b] <= dep[p] + k的b
 
然后我们每次询问的就是在[pre[p] + 1, last[p]] 这段内dep[b] <= dep[p] + k的
而dep[p] + k又是可以确定的,那么我们就可以离线询问、按照dep加入一个BIT
就不用写主席树了
 
 
写完才发现上面理解错了题意,b不一定在p的子树中,但是它和p都是c的祖先
所以如果它不在p的子树中,那么它就是p的祖先,而此时c只能是sz[p] - 1个,修正一下把这块加上即可
 
所以误打误撞学会了一种分析题目的办法,按照它在p的子树内,还是子树外分类
这里这么分类是因为这两种情况的贡献一个是sz[b] - 1 一个是sz[p] - 1,是一道明显的界限
 
 
http://www.cnblogs.com/zyfzyf/p/4252291.html另外一种办法(慢一点)
 
第一次在数据结构相关的题上时间rank1 好开心
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define reg(i,a) for(int i=u[a];i;i=e[i].pre)
#define v e[i].to
using namespace std;
const int N = 300010;
typedef long long LL;
struct edge{
	int to,pre;
}e[N * 2];
int l = 0, u[N];
inline void ins(int a,int b){
	e[++l] = (edge){b, u[a]}, u[a] = l;
}
int pre[N], dep[N], dfs_clock = 0, last[N], sz[N];
void dfs(int x,int f){
	pre[x] = ++dfs_clock, sz[x] = 1;
	reg(i,x) if (v != f){
		dep[v] = dep[x] + 1, dfs(v,x), sz[x] += sz[v];
	}
	last[x] = dfs_clock;
}
#define mp(a,b) make_pair(a,b)
pair<int,int> y[N];
struct query{
	int l,r,t,pos,szp,dep,k;//(l,r]
}q[N];
LL ans[N];
inline bool cmp(const query &a, const query &b){
	return a.t < b.t;
}
inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}

    return x*f;

}
int n;
struct BIT{
	LL s[N];
	inline void add(int x, int d){
		while (x <= n){
			s[x] += d;
			x += (-x) & x;
		}
	}
	inline LL sum(int x){
		LL ans = 0;
		while (x > 0){
			ans += s[x];
			x -= (-x) & x;
		}
		return ans;
	}
}b;
#undef v
int main(){
	int Q;n = read(); Q= read();
	rep(i,1,n-1){
	    int u,v;
	    u = read(),v = read();
		ins(u,v), ins(v,u);
	}
	dep[1] = 1;dfs(1,0);
	rep(i,1,n) y[i] = mp(dep[i],i);
	sort(y+1, y+n+1);
	rep(i,1,Q){
		int p, k;p = read(), k =read();
		q[i] = (query){pre[p], last[p], dep[p] + k, i, sz[p], dep[p], k};
	}
	sort(q+1, q+Q+1, cmp);

	int j = 1;
	rep(i,1,Q){
		for(;y[j].first <= q[i].t && j <= n; j++) {
			int x = y[j].second;
			b.add(pre[x], sz[x] - 1);
		}
		ans[q[i].pos] = b.sum(q[i].r) - b.sum(q[i].l) +1LL * min(q[i].k, q[i].dep - 1) * (q[i].szp - 1);
	}
	rep(i,1,Q) printf("%lld\n", ans[i]);
}

 

Category: oi题解 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com