usaco /the second wave

bzoj4582:简单递推题。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define REP(i,s,t) for(int i=s;i<=t;i++)

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=50005;

int a[nmax],rmax[nmax],res[nmax];

int main(){

	int n=read(),k=read();

	REP(i,1,n) a[i]=read();

	sort(a+1,a+n+1);

	REP(i,1,n){

		int tmp=i;

		while(a[tmp]-a[i]<=k&&tmp<=n) tmp++;

		rmax[i]=tmp-i;

	}

	for(int i=n;i;i--) res[i]=max(res[i+1],rmax[i]);

	int ans=-1;

	REP(i,1,n) ans=max(ans,rmax[i]+res[i+rmax[i]]);

	printf("%d\n",ans);

	return 0;

}

bzoj4525:二分答案+贪心判断。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define REP(i,s,t) for(int i=s;i<=t;i++)

#define clr(x,c) memset(x,c,sizeof(x))

const int nmax=50005;

int a[nmax],n,m;

int read(){

	int x=0;char c=getchar();bool f=true;

	while(!isdigit(c)){

		if(c=='-') f=false;c=getchar();

	}

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return f?x:-x;

}

bool check(int x){

	int ans=0;

	REP(i,1,n){

		int temp=a[i];

		while(a[i]-temp<=x*2&&i<=n) i++;

		i--;

		ans++;

	}

	if(ans<=m) return true;

	return false;

}

int main(){

	n=read(),m=read();

	REP(i,1,n) a[i]=read();

	sort(a+1,a+n+1);

	int l=0,r=1000000000,mid,ans;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)) ans=mid,r=mid-1;

		else l=mid+1;

	}

	printf("%d\n",ans);

	return 0;

}

bzoj4511:模拟。。。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

int x;char c;

int read(){

	x=0;c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

int a[7],n,tmp,sum=0,ans=0;

int main(){

	memset(a,-1,sizeof(a));

	a[0]=0;

	n=read();

	for(int i=1;i<=n;i++){

		tmp=read();

		sum+=tmp,sum%=7;

		if(a[sum]!=-1) ans=max(ans,i-a[sum]);

		else a[sum]=i;

	}

	printf("%d\n",ans);

	return 0;

}

bzoj4397:模拟。。。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define REP(i,s,t) for(int i=1;i<=t;i++)

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=100005;

int a[nmax],b[nmax],c[nmax];

int main(){

	int n=read(),m=read();

	REP(i,1,n) {

		a[i]=a[i-1],b[i]=b[i-1],c[i]=c[i-1];

		int tmp=read();

		if(tmp==1) a[i]++;

		else if(tmp==2) b[i]++;

		else c[i]++;

	}

	REP(i,1,m){

		int s=read(),t=read();

		printf("%d %d %d\n",a[t]-a[s-1],b[t]-b[s-1],c[t]-c[s-1]);

	}

	return 0;

}

bzoj4396:简单递推题。。。

#include<cstdio>

#include<iostream>

using namespace std;

const int nmax=100005;

bool vis[nmax];

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

int main(){

	int n=read();

	for(int i=1;i<=n;i++) vis[read()]=true;

	n+=n;

	int l=1,ans=0;

	for(int i=1;i<=n;i++) if(!vis[i]){

		while(!vis[l]) l++;

		if(l<i) l++,ans++;

	}

	printf("%d\n",ans);

	return 0;

}