UVA 1213 Leonardo 의 노트북

1682 단어 해제
UVA 1213 Leonardo 의 노트북
Date 2019.8.1
제목 의 대의
대문자 26 개의 바 꾸 기 B 를 주 고 바 꾸 기 A 가 있 는 지 물 어보 면 A2 = B 가 됩 니 다.
사고의 방향
우 리 는 B 를 바 꾸 는 과정 에서 모든 고 리 를 찾 을 수 있다. 예 를 들 어 지금 B 를 'BAC' 로 바 꾸 면 두 개의 고 리 를 포함한다. 하 나 는 A, B 로 구 성 된 고리 와 하 나 는 C 로 구 성 된 자체 고 리 를 포함한다.우 리 는 고 리 를 두 가지 로 나 눌 것 이다. 기 환 과 우 환 이다.A, B 로 구 성 된 고 리 는 바로 우 환 이 고 C 의 자 환 은 기 환 이다.만약 에 특정한 길이 의 짝 고리 의 수량 이 홀수 라면 'No' 를 출력 하고 그렇지 않 으 면 'Yes' 를 출력 합 니 다.다음은 이런 방법의 정확성 을 살 펴 보 자.우 리 는 A 의 제곱 을 B, 즉 매번 이 고리 에서 두 걸음 씩 걷 게 해 야 하기 때문이다.하나의 기이 한 고리 에 대해 우 리 는 매번 가 는 일이 두 걸음 이지 만 우 리 는 고리 위의 임 의적 인 점, 즉 고리 자체 에 변화 가 없고 고리 안의 점 이 위 치 를 바 꾸 었 을 뿐 답 에 영향 을 주지 않 는 다.그러나 짝 고리 에 대해 우 리 는 한 점 에서 출발 하여 최대 수량의 절반 에 불과 하 다. 이것 은 원래 의 큰 고리 로 이해 하고 두 개의 긴 작은 짝 고리 로 나 눌 수 있다.그래서 우 리 는 B 의 각 길이 의 링 의 수량의 패 리 티 를 판단 하여 답 을 얻 을 수 있다.
다음은 본인 의 코드 를 동봉 합 니 다.
#include
using namespace std;
int vis[1009],a[1009],b[1009],cnt;
int T;
char s[1009];
int main ()
{
	scanf("%d",&T);
	for (int t=1;t<=T;t++)
	{
		scanf("%s",s+1);
		memset(vis,0,sizeof(vis));
		memset(b,0,sizeof(b));
		for (int i=1;i<=26;i++)
			a[i]=s[i]-'A'+1;
		for (int i=1;i<=26;i++)
			if (!vis[i])//B                ,     vis          
			{
				int i2=a[i];
				cnt=1;
				vis[i2]=1;
				while (i!=i2)
				{
					cnt++;
					i2=a[i2];
					vis[i2]=1;
				}
				b[cnt]++;//b       cnt      
			}
		int flag=0;
		for (int i=2;i<=26;i+=2)
			if (b[i]%2!=0)
				flag=1;
		if (!flag)
			printf("Yes
"); else printf("No
"); } return 0; }

후기
오늘 하루 종일 인터넷 흐름 을 배 웠 는데 아무것도 못 알 아 듣 고 어제 acm 문 제 를 계속 썼 습 니 다.

좋은 웹페이지 즐겨찾기