[우 객 망] 2017 년 절강공업대학 대학생 프로 그래 밍 새해 맞이 평가 전 F 문제 사각형 I [증명 문제] [생각 문제]

[우 객 망] 2017 년 절강공업대학 대학생 프로 그래 밍 새해 맞이 평가 전 F 문제 사각형 I
시간 제한: C / C + + 1 초, 기타 언어 2 초 공간 제한: C / C + + 131072 K, 기타 언어 262144 K 64bit IO Format:% lld 제목 은 N 개의 사각형 이 한 줄 로 되 어 있 고 각 사각형 은 색 으로 염색 되 어 있 으 며 i 번 째 색 은 Ci 입 니 다. 모두 세 가지 색 이 있 습 니 다. 각각 빨간색, 노란색, 파란색 입 니 다. 지금 은 인접 한 색 이 다른 사각형 을 사용 할 수 있 습 니 다.이 를 세 번 째 색 으로 만 들 었 다. 예 를 들 어 인접 한 빨간색 사각형 과 노란색 사각형 을 사용 하면 파란색 사각형 으로 합 칠 수 있다.시전 순서 가 다 르 면 최종 결과 에 서로 다른 영향 을 미 칠 수 있 습 니 다. 가장 좋 은 전략 에서 최소 몇 개의 사각형 이 남 을 수 있 는 지 물 어보 세 요.
입력 설명: T 조 데이터.각 그룹의 데이터 한 줄 은 사각형 서열 을 문자열 형식 으로 보 여 줍 니 다. a, b, c 는 세 가지 서로 다른 색 의 사각형 을 표시 합 니 다.T < = 101 < = N < = 5000 출력 설명: 각 그룹의 데 이 터 는 하나의 정수 로 답 을 표시 합 니 다.
머리말: 이 문 제 는 사람들 속 에서 누군가가 묻 는 것 을 보고 생각 했다.방법 은 간단 하지만 증 법 은 흥 미 를 잃 지 않 으 니 차라리 오 랜 만 에 문 제 를 써 보 자 ~
사각형 의 길이 n 을 가정 하고 한 가지 색 만 포함 하면 최소 남 은 사각형 수 는 n 입 니 다.여러 색상 이 포함 되 어 있 으 면 한 색상 이 01 문자열 (ex: 0000111001000) 로 변 하 는 형식 을 제거 할 수 있 습 니 다.우 리 는 항상 01 꼬치 의 시작 을 0 으로 할 수 있 고 01 꼬치 의 수 는 적어도 3 이 고 단락 수 는 2 로 특수 처리 할 수 있다 고 가정 할 수 있다.주 방법: 왼쪽 에서 오른쪽으로 첫 번 째 1 에서 왼쪽으로 계속 합 쳐 0 의 개수 에 따라 1 또는 2 (제 거 된 세 번 째 색) 로 변 합 니 다.다음은 두 가지 상황 으로 나 뉜 다. 1. 1 이 되면 최초의 0 단 이 제거 되 고 1 단 이 하 나 를 추가 하여 재 귀 형식 이 되 어 01 꼬치 01 을 뒤 집 으 면 된다.2. 2 가 되면 꼬치 형식 은 '21111000...' 으로 바 뀌 고 그 다음 에 2 로 오른쪽으로 합병 하여 오른쪽 1 단 을 합병 한 후에 01 꼬치 는 두 가지 차이 가 있다. 2.1 '2000...'. 이때 01 만 뒤 집 으 면 상황 2 의 재 귀 형식 이다.2.2 "0000..................................................................
마지막 으로 시작 할 수 있 는 2 를 제외 하고 01 꼬치 가 두 단락 만 남 았 을 때 (ex: 0001111) 특별 처리 가 필요 합 니 다.처음에 2, 0 개의 패 리 티 가 있 는 지 에 따라 네 가지 상황 으로 나 뉜 다.처음에 2, 0 개 수 는 기 (ex: 00001111) 가 없 었 다. 주요 방법 으로 오른쪽 첫 번 째 1 에서 왼쪽으로 합병 하고 꼬치 는 2111 형식 으로 바 뀌 었 다. 다시 2 에서 오른쪽으로 합병 하면 마지막 에 반드시 하나 가 남 았 다. 0 인지 2 인지 1 의 개 수 를 보 자.처음에 2, 0 개 수 는 짝 (ex: 0001111) 이 없 었 다. 맨 왼쪽 에 있 는 모든 0 을 직접 합병 하면 1111 이 될 것 이 고 이렇게 할 수 없 을 것 이다.해결 방법 은 먼저 가장 왼쪽 에 있 는 0 을 격 리 하여 상황 [시작 에 2, 0 개 수가 없 음] 으로 처리 한 다음 에 처리 한 후에 결 과 를 0 과 합병 하려 고 시도 하 는 것 이다.한 개의 수가 기이 하면 마지막 에 1 로 합 칠 수 있 고 그렇지 않 으 면 0 이 두 개 남는다.처음에 2, 0 개 수 는 기 (ex: 20001111) 였 다. 오른쪽으로 합 쳐 0 이 남 을 때 까지 '201111' 이 되 었 고 그 다음 에 0 으로 오른쪽으로 합 쳐 마지막 으로 시작 하 는 2 와 합 쳐 보 았 다.1 개 수 는 기이 하면 2 개, 1 개 수 는 짝수 1 개 남 았 다.처음에 2, 0 개의 수 는 짝 (ex: 20001111) 이 었 다. 더 말 하지 않 고 2 는 계속 오른쪽으로 합병 하면 된다.1 개 수 는 짝수 이 고 2 개, 1 개 수 는 홀수 이 고 0 이 남는다.
득 증: 순수한 색 이 아 닌 사각형 은 마지막 에 반드시 2 개 또는 1 개의 사각형 으로 합 칠 수 있 습 니 다.
주의 하 세 요. 다음은 본 문제 의 해법 입 니 다!
위의 증명 에 의 하면 순수한 색 이 아 닌 사각형 은 마지막 에 반드시 2 개 또는 1 개의 사각형 이 남 을 수 있다 는 것 을 알 수 있다. 그러면 2 개 를 하나 로 합 칠 수 있 습 니까?
하나의 개념 을 도입 한다. 세 가지 색깔 은 각각 0, 1, 2 로 표시 한다.제목 에서 보 듯 이 합병 방식 은 01 합병 은 2, 02 합병 은 1, 12 합병 은 0 이다.이 합병 방식 은 공식 적 으로 0 ^ 1 ^ 3 = 2 0 ^ 2 ^ 3 = 1 ^ 2 ^ 3 = 0 으로 규칙 을 쉽게 찾 을 수 있 습 니 다. 두 색 을 합 쳐 세 번 째 색 으로 바 꿀 수 있 습 니 다. 즉, 대표 적 인 숫자 xor 재 xor 상 3 후의 답 입 니 다!
이 법칙 은 무슨 소 용이 있 습 니까?
합병 이 나타 나 면 이전 3, 하나의 길이 가 n 인 사각형 이 1 개의 사각형 으로 합 쳐 지면 마지막 에 남 은 사각형 의 색 은 n 개의 색 이 대표 하 는 숫자 (0, 1, 2) xor 다음 에 xor 에서 n - 1 개의 3 의 값 이 대표 하 는 색 입 니 다.
처음에 우 리 는 순수한 색 이 아 닌 사각형 이 반드시 1 또는 2 개의 사각형 으로 합 쳐 질 수 있다 는 것 을 증 명 했 기 때문이다.마지막 두 개의 사각형 이 1 개의 사각형 으로 합 쳐 질 수 있 는 지, n 개의 xor 를 본 다음 에 xor 에 n - 1 개의 3 의 값 이 3 이 아 닌 지 (x ^ x ^ 3 = 3) 를 보면 n 개의 사각형 이 마지막 에 하나 로 합 쳐 질 수 있 음 을 설명 하지 않 으 면 마지막 색상 도 확인 할 수 있 습 니 다.그렇지 않 으 면 두 개의 네모 난 덩어리 다.
최종 해법 은 매우 간단 하 다. 세 가지 색깔 은 각각 0, 1, 2 로 표시 한 다음 에 n 개의 수가 같 는 지 판단 한다.그렇다면 n 출력 하기;모든 xor 가 일어나 서 xor 에 n - 1 개 3 을 올 리 는 것 이 아니 라 3 출력 2 와 같 으 면 1 을 출력 합 니 다.
PS: 더 간단 하고 교묘 한 증명 이 있 으 면 댓 글로 남 겨 주세요 ~
my code:

#include 
using namespace std ;

const int MAXN = 5005 ;

char s[MAXN] ;

void solve () {
    int n = strlen ( s ) ;
    char c = s[0] ;
    int ans = n % 2 ? 0 : 3 , cnt = 0 ;
    for ( int i = 0 ; i < n ; ++ i ) {
        ans ^= s[i] - 'a' ;
        if ( s[i] == c ) ++ cnt ;
    }
    if ( cnt == n ) printf ( "%d
" , n ) ;
    else printf ( "%d
" , ans == 3 ? 2 : 1 ) ;
}

int main () {
    while ( ~scanf ( "%s" , s ) ) solve () ;
}