CF1073

CF1073A

一道水题。
首先从题意可知,当连续两个字符不同的时候,这样的字符串就是合法的。
所以找第一组两个不同的字符即可。

CF1073B

没什么好说的,依照题意大力模拟即可。

CF1073C

有一定难度的水题,但是我考场上没 调 出 来!
其实很容易可以想到,因为当长度为\(len\)的可行,长度为\(len+1\)的也一定可行。
所以考虑二分答案。
如何检验呢?其实就是将一连串的移动移除了,然后考虑它前面的部分加上后面的部分,再加上长度为len的移动序列,要怎样才能走到终点。
因此我们可以预处理曼哈顿距离前缀和。于是可以\(O(1)\)检验。
这题就做完了。
但是,我调了一个多小时——
因为我的Abs函数写挂了!!!!!
于是就从开心上分场变成了掉分场。
缺省源能写挂也是很厉害。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
#define INF 0x3f3f3f3f
#define Abs(_A) ((_A)>0?(_A):(-(_A)))
/*
CF1073A
*/
int n;
char ch[1005];
inline void pt(const char &a,const char &b){
	puts("YES");
	putchar(b),putchar(a);
} 
void init(){
	scanf("%d",&n);
	cin>>ch;
	int nw=0;
	for(int i=0;i<n;++i){
		if(!i){
			nw=ch[i];
		}
		if(ch[i]!=nw){
			pt(ch[i],nw);
			return;
		}
	}
	puts("NO");
}
int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
#define INF 0x3f3f3f3f
#define Abs(_A) ((_A)>0?(_A):(-(_A)))
/*
CF1073B
*/
int n,a[200005],b[200005];
bool bckt[200005];
priority_queue< int,vector<int>,greater<int> > q;
void init(){
	scanf("%d",&n);
	memset(bckt,0,sizeof(bckt));
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int cnt=0,p=1;
	for(int i=1;i<=n;++i){
		scanf("%d",&b[i]);
		cnt=0;
		if(bckt[b[i]]){
			printf("0 ");
			continue;
		}
		while(a[p]!=b[i]&&p<=n){
			bckt[a[p]]=1;
			++cnt;
			++p;
		}
		if(a[p]==b[i]){
			bckt[a[p]]=1;
			++cnt;
			++p;
		}
		printf("%d ",cnt);
	}
	
}
int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
#define INF 0x3f3f3f3f
#define Abs(_A) ((_A)>0?(_A):(-(_A)))
/*
CF1073C
有一定难度的水题,但是我考场上没 调 出 来!
其实很容易可以想到,因为当长度为$lated len$的可行,长度为\(len+1\)的也一定可行。
所以考虑二分答案。
如何检验呢?其实就是将一连串的移动移除了,然后考虑它前面的部分加上后面的部分,再加上长度为len的移动序列,要怎样才能走到终点。 
因此我们可以预处理曼哈顿距离前缀和。于是可以\(O(1)\)检验。
这题就做完了。
但是,我调了一个多小时——
因为我的Abs函数写挂了!!!!!
于是就从开心上分场变成了掉分场。
缺省源能写挂也是很厉害。 
*/
int n;
char ch[200005];
int X,Y,smx[200005],smy[200005];
inline bool cckk(const int &s,const int &t,const int &len){
	int dx=X-(smx[n]-smx[t])-smx[s-1],dy=Y-(smy[n]-smy[t])-smy[s-1];
	if(((dx+dy)&1)!=(len&1)){
		return 0;
	}
	if((Abs(dx)+Abs(dy)>len)){
		return 0;
	}
	return 1;
}
inline bool chck(const int &len){
	for(int i=1;i-1+len<=n;++i){
		if(cckk(i,i+len-1,len)){
			return 1;
		}
	}
	return 0;
}
void init(){
	scanf("%d",&n);
	cin>>ch+1;
	scanf("%d%d",&X,&Y);
	smx[0]=smy[0]=0;
	for(int i=1;i<=n;++i){
		if(ch[i]=='U'){
			smy[i]=smy[i-1]+1;
			smx[i]=smx[i-1];
		}else if(ch[i]=='D'){
			smy[i]=smy[i-1]-1;
			smx[i]=smx[i-1];
		}else if(ch[i]=='L'){
			smx[i]=smx[i-1]-1;
			smy[i]=smy[i-1];
		}else if(ch[i]=='R'){
			smx[i]=smx[i-1]+1;
			smy[i]=smy[i-1];
		}
	}
	int l=0,r=n+1,mid;
	while(l<r){
		mid=(l+r)>>1;
		if(chck(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	if(l>n){
		puts("-1");
	}else{
		printf("%d",l);
	}
}
int main(){
	init();
	return 0;
}

 

发表评论

您的电子邮箱地址不会被公开。