Codeforces Round #136 (Div. 二)

Codeforces Round #136 (Div. 2)

转载请注明出处，谢谢http://blog.****.net/acm_cxlove/article/details/7854526 by---cxlove

好欢乐的一场CF，不过玩过头了，最后还是跪了。

这份题解来得有点晚，最近状态很差

A：Little Elephant and Function

一个递归，开始看错了，是先递归，然后再交换。

可以发现就是先交换前两个，然后依次下去，最后交换最后两个

序列为n,1,2,……n-1

B. Little Elephant and Numbers

简单数学题。直接暴力枚举n的约数，sqrt(n)的复杂度，然后判断是否有相同的数字

C. Little Elephant and Problem

直接把原数组排序之后，然后依次比对，如果有两位以上不同的，说明一次交换不能完成，否则交换一次就可以了

D. Little Elephant and Array

当时欢乐过头了，然后就SB了。开始以为是统计区间不同数字的个数，迅速敲了一个线段树，然后样例不能过。然后就开始SB。后来看懂题意之后，觉得之前的线段树还有利用价值，就保留了，奠定了悲剧，之后的线段树+SET常数过大。最终还是T了。

其实可以发现1+2+……450>10^5。所以有效的数字肯定不超过450个，只要预处理找到这些数字，然后对于每一次查询枚举这些数字就可以了。但是可以知道，每一次查询，也是可以预处理的，当然可以用线段树之类的，dp[i][j]表示第i个数在1……j这j个位置中出现了多少次。

这样预处理的复杂度上限为450*n,每一次查询的复杂度为O(450)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<vector>
#define eps 1e-7
#define LL long long
#define N 100005
#define zero(a) fabs(a)<eps
#define lson step<<1
#define rson step<<1|1
#define pb(a) push_back(a)
using namespace std;
int dp[500][N];
int n,q;
int a[N],b[N];
int c[N][2];
int main(){
    while(scanf("%d%d",&n,&q)!=EOF){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        int cnt=-1;
        sort(b+1,b+1+n);
        b[0]=-1;
        memset(c,0,sizeof(cnt));
        for(int i=1;i<=n;i++){
            if(b[i]!=b[i-1]) cnt++;
            c[cnt][0]=b[i];
            c[cnt][1]++;
        }
        vector<int>v;
        for(int i=0;i<=cnt;i++){
            if(c[i][1]>=c[i][0])
                v.pb(c[i][0]);
        }
        for(int i=0;i<v.size();i++){
            dp[i][0]=0;
            for(int j=1;j<=n;j++){
                if(a[j]==v[i])
                   dp[i][j]=dp[i][j-1]+1;
                else
                   dp[i][j]=dp[i][j-1];
            }
        }
        while(q--){
            int l,r;
            scanf("%d%d",&l,&r);
            int ans=0;
            for(int i=0;i<v.size();i++)
               ans+=(dp[i][r]-dp[i][l-1])==v[i];
            printf("%d\n",ans);
        }
    }
    return 0;
}

E. Little Elephant and Shifts

这题因为当时太欢乐，后来都没有研究，其实当时还有一个小时。。。伤心

问有两个序列，求出题目指定的最短距离，而且其中一个序列，每次左移一位。

题解啥的，之后再加。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#define N 100005
#define eps 1e-8
#define inf 1<<30
#define zero(a) fabs(a)<eps
using namespace std;
struct N1{
	int step,pos;
	N1(){}
	N1(int x,int y):step(x),pos(y){}
	bool friend operator<(const N1 &a,const N1 &b){
		return a.step>b.step;
	}
};
struct N2{
	int step,pos;
	N2(){}
	N2(int x,int y):step(x),pos(y){}
	bool friend operator<(const N2 &a,const N2 &b){
		return a.step<b.step;
	}
};
priority_queue<N1>q1;
priority_queue<N2>q2;
int a[N],b[N],in[N],n;
int main(){
	while(scanf("%d",&n)!=EOF){
		while(!q1.empty()) q1.pop();
		while(!q2.empty()) q2.pop();
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
			in[a[i]]=i;
		}
		for(int i=0;i<n;i++){
			scanf("%d",&b[i]);
			if(i>in[b[i]]) q1.push(N1(i-in[b[i]],i));
			else q2.push(N2(i-in[b[i]],i));
		}
		for(int i=0;i<n;i++){
			int ans=inf;
			if(!q1.empty()) ans=min(ans,abs(q1.top().step-i));
			if(!q2.empty()) ans=min(ans,abs(q2.top().step-i));
			printf("%d\n",ans);
			q1.push(N1(n+i-in[b[i]],inf));
			while(!q1.empty()&&(q1.top().pos<=i||q1.top().step-i-1<=0)){
				if(q1.top().pos<=i){q1.pop();continue;}
				q2.push(N2(q1.top().step,q1.top().pos));
				q1.pop();
			}
			while(!q2.empty()&&q2.top().pos<=i) q2.pop();
		}
	}
	return 0;
}

Codeforces Round #136 (Div. 二)

相关推荐