URAL 1827 Indigenous Wars(排序、乱搞)

题意:给一个长度为n数组{a[i]}。有m个操作Ti,Si,Li表示找以Ti值结束,以Si值开始,长度为Li的连续子串。找到后,将区间的答案值设为1。一开始答案值全部为0。最后输出n个答案值。

 

好久没打题了

算法:排序,乱搞。主要是要考虑到排序的时候,len大的放前边,这样可以break省掉不少时间。最后注意题目要求的输出顺序,是类似于输入顺序的理解。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
using namespace std;

#define ll long long
#define MP make_pair

#define inf 0x3f3f3f3f
#define eps 1e-8

#define maxn 100010

int a[maxn];
struct node{
	int r,len;
	node(int _r,int _len):r(_r),len(_len){}
	bool operator < (const node& b) const{
		return len < b.len;
	}
};
vector<node>v[maxn];
int xx[maxn];
int main(){
	int n,m;
	while(~scanf("%d",&n)){
		for(int i=n-1;i>=0;--i) scanf("%d",a+i), xx[i] = a[i];
		sort(xx,xx+n);
		int nn = unique(xx,xx+n) - xx;
		for(int i=0;i<n;++i) a[i] = lower_bound(xx,xx+nn,a[i]) - xx;
		for(int i=0;i<=nn;++i) v[i].clear();
		scanf("%d",&m);
		for(int i=0;i<m;++i){
			int li,ri,leni;
			scanf("%d%d%d",&li,&ri,&leni);int lval=li,rval=ri;
			if(leni > n) continue;
			li = lower_bound(xx,xx+nn,li) - xx;
			ri = lower_bound(xx,xx+nn,ri) - xx;
			if(li==nn || ri==nn) continue;
			if(xx[li]!=lval || xx[ri]!=rval) continue;
			v[li].push_back(node(ri,leni));
		}
		for(int i=0;i<=nn;++i) sort(v[i].begin(),v[i].end());
		int add[maxn];
		memset(add,0,sizeof(add));
		for(int i=0;i<n;++i){
			for(int j=v[a[i]].size()-1;j>=0;--j){
				int len = v[a[i]][j].len;
				int val = v[a[i]][j].r;
				if(i+len-1 >= n) continue;
				if(a[i+len-1] == val){
					add[i]++;
					add[i+len]--;
					break;
				}
			}
		}
		for(int i=1;i<n;++i) add[i] += add[i-1];
		for(int i=n-1;i>=0;--i) printf("%c",add[i]>0?‘1‘:‘0‘);
		puts("");
	}
	return 0;
}

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。