Codeforces Round \ # 656 (Div. 3) A, B, C, D, (기타 보충)

목차

[ A. Three Pairwise Maximums](https://codeforces.ml/contest/1385/problem/A)

[B. Restore the Permutation by Merger](https://codeforces.ml/contest/1385/problem/B)

[C. Make It Good](https://codeforces.ml/contest/1385/problem/C)

[D. a-Good String](https://codeforces.ml/contest/1385/problem/D)

A. Three Pairwise Maximums

제목 x = max (a, b) y = max (a, c) z = max (b, c) x, y, z 에 게 a, b, c 가 존재 하 는 지 물 어보 고 임의의 답 을 출력 합 니 다

입력

5 3 2 3 100 100 100 50 49 49 10 30 20 1 1000000000 1000000000

출력

YES 3 2 1 YES 100 100 100 NO NO YES 1 1 1000000000

문제 풀이 방향 은 a < = b < = c 는 x = max (a, b) = b y = max (a, c) = c z = max (b, c) = c 이 므 로 먼저 x, y, z 를 작은 것 에서 큰 것 으로 정렬 합 니 다. 만약 x

코드

#include
#include
using namespace std;
int main()
{
	int t,a[3];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&a[0],&a[1],&a[2]);
		sort(a,a+3);
		if(a[1]==a[2])
		{
			printf("YES
");
			printf("%d %d %d
",a[0],a[0],a[2]);
		}
		else printf("NO
");
	}
	return 0;
} 

B. Restore the Permutation by Merger

두 개의 길이 가 n 인 교체 합병 수열 을 주 고 원 교체 합병 은 원 교체 중의 순 서 를 바 꾸 지 않 습 니 다

.

입력

5 2 1 1 2 2 4 1 3 1 4 3 4 2 2 5 1 2 1 2 3 4 3 5 4 5 3 1 2 3 1 2 3 4 2 3 2 4 1 3 4 1

출력

1 2 1 3 4 2 1 2 3 4 5 1 2 3 2 3 4 1

문제 풀이 사고 표시 + 무 거 운 것 을 제거 하고 1 - n 처음 나타 난 것 만 남긴다

코드

#include
#include
#include
using namespace std;
int t,n,x,a[110],b[55],cnt;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		cnt=0;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		for(int i=1;i<=2*n;i++)
		{
			scanf("%d",&x);
			if(!b[x])
			{
				b[x]++;a[++cnt]=x;
			}
		}
		for(int i=1;i<=cnt;i++)printf("%d ",a[i]);
		printf("
");
	}
	return 0;
}

C. Make It Good

문 제 는 n 길이 의 수열 을 주 고 접두사 가 얼마나 있어 야 좋 은 수열 이 될 수 있 는 지 물 어 본다.좋 은 수열 의 정의: 이 수열 의 머리 나 끝 을 다른 수열 c 에 넣 을 때마다 이 수열 의 수 를 다 뽑 을 때 까지 c 는 단 조 롭 게 증가 합 니 다.

입력

5 4 1 2 3 4 7 4 3 3 8 4 5 2 3 1 1 1 7 1 3 1 4 5 3 2 5 5 4 3 2 3

출력

0 4 0 2 3

문제 풀이 방향 은 뒤에서 앞 을 보고 산봉우리 하 나 를 찾 았 다 (먼저 증가 하고 다시 감소). 불필요 한 것 을 삭제 했다

.

코드

#include
#include
#include
using namespace std;
int const N=2e5+5;
int t,n,a[N];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		int i=0,j=0;
		for(i=n-1;i>=1;i--)
			if(a[i]<a[i+1])break;
		
		for(j=i;j>=1;j--)
			if(a[j]>a[j+1])break;
		printf("%d
",j);
	}
	return 0;
}

D. a-Good String

제목: n = 2k 길이 의 소문 자로 구 성 된 문자열 s 를 드 리 겠 습 니 다. 최소한 몇 글자 만 바 꾸 어 a - good a - good 로 정의 하 십시오.

n==1 s1=a

n > = 1 s 의 앞부분 은 모두 a 후반 부 (a + 1) - good

n > = 1 s 의 앞부분 은 (a + 1) - good 후반 부 는 모두 a

입력

6 8 bbdcaaaa 8 asdfghjk 8 ceaaaabb 8 bbaaddcc 1 z 2 ac

출력

0 7 4 5 1 1

문제 풀이 방향 은 문제 의 뜻 에 따라 a - good 이 재 귀적 으로 정 의 된 것 임 을 알 수 있 기 때문에 풀이 도 재 귀적 으로 한다.dfs 는 가능 한 모든 상황 을 매 거 합 니 다. 왼쪽 절반 은 현재 문 자 를 선택 하 시 겠 습 니까? 오른쪽 절반 은 현재 문 자 를 선택 하 시 겠 습 니까? 서로 다른 문자 수 를 계산 하 시 겠 습 니까? 작은 것 을 취하 시 겠 습 니까?

코드

#include
#include
#include
using namespace std;
int const N=2e5;
char s[N];
int t,n;
int dfs(int l,int r,char ch)
{
	if(l==r)//n=1   
	{
		if(ch==s[l])return 0;//     
		return 1; //    
	}
	int cnt1=0,cnt2=0,x=(l+r)/2;
	for(int i=l;i<=x;i++)
		if(ch!=s[i])cnt1++;
	for(int i=x+1;i<=r;i++)
		if(ch!=s[i])cnt2++;
	return min(dfs(l,x,ch+1)+cnt2,cnt1+dfs(x+1,r,ch+1));
	//          （ch+1）-good    ch        ch    （ch+1）-good       
}
int main()
{
	scanf("%d
",&t);
	while(t--)
	{
		scanf("%d
",&n);
		scanf("%s",s+1);
		printf("%d
",dfs(1,n,'a'));
	}
	return 0;
}