常用技巧精选(一)

尺取法 Subsequence POJ No.3061 (1)

求连续子序列中总和不小于S的最小长度。
由于所有的元素都大于0，如果子序列[s,t)满足a_s+···+a_t-1>=S,那么对于任何的t<t’一定有a_s+···+a_t’-1>=S。此外对于区间[s,t)上的总和来说如果令
sum(i)=a₀+a₁+···+a_i-1
那么
a_s+a_s+1+···+a_t-1=sum(t)-sum(s)
因此预先以O(n)的时间计算好sum的话，就可以以O(1)的时间计算区间上的总和。这样一来，子序列的起点s确定之后，便可以用二分搜索快速地确定使序列和不小于S的结尾t的最小值。

int a[10005],n,S;
void solve(){
	int x;
	for(int i=1;i<=n;i++){
		cin >> x;
		a[i]=a[i-1]+x;
	}
	if(a[n]<S){
		cout << 0 << endl;
		return;
	}
	int res=n;
	for(int s=0;a[s]+S<=a[n];s++){
		int t=lower_bound(a+s,a+n,a[s]+S)-a;//找始终比当前大S的子序列(即s到t这一段路程是超过S的) 
		res=min(res,t-s);
	}
	cout << res << endl; 
}
int main(){
	cin >> n >> S;
	solve();
	return 0;
}

复杂度为O(nlogn)
第二种方法
最小子序列是大于等于S的那么这个序列任意减掉一个元素它就是小于S的了。
1.将s=t=sum=0初始化
2.只要有sum<S,就不断将sum增加a，并将t增加1
3.如果2无法满足sum>=S则终止，否则跟新res=min(res,t-s)
4sum减去a_s，s增加1然后回到2

int a[10005],n,S;
void solve2(){
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	int res=n+1;
	int s=0,t=0,sum=0;
	while(true){
		while(t<n&&sum<S){
			sum+=a[t++];
		}
		if(sum<S){
			break;
		}
		res=min(res,t-s);
		sum-=a[s++];
	}
	if(res>n){
		cout << 0 << endl;
	}else{
		cout << res << endl;
	}
} 
int main(){
	cin >> n >> S;
	solve2();
	return 0;
}

像这样反复地推进区间地开头和末尾，来求取满足条件地最小区间地方法称为尺取法。

Jessica’s Reading Problem POJ No.3320 (2)

也可用尺取法

int P;
int a[1000005];
void solve(){
	set<int> all;
	for(int i=1;i<=P;i++){
		all.insert(a[i]);
	}
	int n=all.size();
	int s=1,t=1,num=0;
	int res=P;
	map<int,int> count;//知识点->使用次数
	for(;;){
		while(t<=P&&num<n){
			if(count[a[t]]==0){
				num++; 
			}
			count[a[t++]]++;
		}
		if(num<n)break;
		res=min(res,t-s);
		if(--count[a[s++]]==0){
			num--;
		}
	}
	cout << res << endl;
}
int main(){
	cin >> P;
	for(int i=1;i<=P;i++){
		cin >> a[i];
	}
	solve();
	return 0;
}

复杂度为O(PlogP)

反转(开关问题) Face The Right Way POJ No.3276 (1)

首先，交换区间反转地顺序对于结果是没有影响地。此外，可以知道对同一个区间进行两次以上地反转时多余的。由此，问题就转化为了求需要杯反转地区间的集合。于是我们先考虑一下最左端的牛。包含这头牛的区间只有一个，因此如果这头牛面朝前方，我们就能知道这个区间不需要反转。
反之，如果这头牛面朝后方，对应的区间就必须进行反转了。而且在此之后这个最左的区间就再也不需要考虑了。这样依赖，通过考虑最左边的牛，问题的规模就缩小了1，不断地重复下去，就可以无需搜索求出最少所需地反转次数了。
首先我们对所有的K都求解一次，对于每个K我们都要从最左端开始考虑N头牛地情况，此时最坏情况需要进行N-K+1次的反转操作，而每次操作又要反转K头牛，所以总的夫再度为O(N³)。但是区间反转部分还是很容易进行优化的。
记f[i]:=区间[i,i+K-1]进行了反转的话则为1，否则为0
这样，在考虑第i头牛的时，如果Σ_j=i-K+1^i-1为奇数的话，则这头牛的方向是与起始方向相反的。

int N;
int dir[5005];
int f[5005];
int calc(int K){
	memset(f,0,sizeof(f));
	int res=0;
	int sum=0;//f的和
	for(int i=0;i+K<=N;i++){
		//计算区间[i,i+K-1]
		if((dir[i]+sum)%2!=0){
			//前i到i+k-1的值为奇数代表转换过，如果本来就是面对背后的再加上当前的奇数就变为偶数了
			res++;
			f[i]=1; 
		}
		sum+=f[i];
		if(i-K+1>=0){
			sum-=f[i-K+1];//减去上一个区间的值 
		}
	} 
	//检查剩下的牛是否有面朝后方的情况
	for(int i=N-K+1;i<N;i++){
		if((dir[i]+sum)%2!=0){
			//无解
			return -1; 
		}
		if(i-K+1>=0){
			sum-=f[i-K+1];
		}
	}
	return res; 
}
void solve(){
	int K=1,M=N;
	for(int k=1;k<=N;k++){
		int m=calc(k);
		if(m>=0&&M>m){
			M=m;
			K=k;
		}
	}
	cout << K << " " << M << endl;
}
int main(){
	char c;
	cin >> N; 
	for(int i=0;i<N;i++){
		cin >> c;
		if(c=='B'){
			dir[i]=1;
		}
	}
	solve();
	return 0;
}