CH 0503 기 디지털 문제 (역순 대)

질문
생각:
오랫동안 찾 았 지만 기 디지털 문제 와 n * 8727 ° m n * m * 8727 ° m 디지털 문제 에 대한 상세 한 증명 을 찾 지 못 했 습 니 다.결론 부터 적어.
기 디지털 게임 의 두 국면 은 도달 할 수 있 으 며, 두 국면 에서 만 네트워크 의 수 를 0 을 포함 하지 않 는 11 에서 n - 1 n - 1 n * n - 1 n - 8727 ° n - 1 의 서열 로 순서대로 쓴 후에 역순 대 개수 의 패 리 티 는 같다.
결론 의 필요 성 증명: 빈 칸 (즉 0 0 0) 이 좌우 로 이동 할 때 우리 가 열거 한 서열 은 변 하지 않 는 다. 빈 칸 이 위 (아래) 로 이동 할 때 특정한 수 와 그 뒤 (앞) 변 n - 1 n - 1 - 1 - 1 개의 수 는 위 치 를 교환 하 는 것 과 같다. n - 1 n - 1 - 1 은 짝수 이기 때문에 역순 대수 의 변화 도 짝수 이기 때문이다.
n n n 을 짝수 로 확대 하 는 상황 에서 이때 두 국면 은 도달 할 수 있다. 또한 두 국면 에 대응 하 는 네트워크 가 서열 을 작성 한 후에 '' 역순 로그 수의 차이 '와' 두 국면 에서 빈 칸 이 있 는 줄 수의 차이 '' 를 말한다.패 리 티 가 같 습 니 다.
코드:

#include 
#define sc scanf
#define pf printf
using namespace std;
const int N = 250010;

int a[N], b[N], w[N];

//         
int merge(int l, int r, int x[])
{
    if(l == r)    return 0;
    int mid = l + r >> 1;
    int res = merge(l, mid, x) + merge(mid + 1, r, x);
    
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r) {
        if(x[i] <= x[j])    w[k++] = x[i++];
        else {
            res += mid - i + 1;
            w[k++] = x[j++];
        }
    }
    while(i <= mid) w[k++] = x[i++];
    while(j <= r)   w[k++] = x[j++];
    for(i = l, j = 0; i <= r; i++, j++) x[i] = w[j];
    return res;
}

void read(int *x, int len)
{
    int k = 0;
    for(int i = 0; i < len; i++) {
        int num; sc("%d", &num);
        if(num != 0)    x[k++] = num;
    }
}

int main()
{
    int n;
    while(cin >> n) {
        read(a, n * n);
        read(b, n * n);
        int cnt_a = merge(0, n * n - 1, a);
        int cnt_b = merge(0, n * n - 1, b);
        //         
        //                            
        if((cnt_a & 1) == (cnt_b & 1))  puts("TAK");
        else    puts("NIE");
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[알고리즘 경기 진급 안내] 접두사 통계 (trie 트 리)

제목. N 개의 문자열 S1, S2... SN 을 주어진 다음 M 번 질문 을 합 니 다. 주어진 문자열 T 에 대해 물 어 볼 때마다 S1 ~ SN 에 T 의 접두사 가 몇 개 있 는 지 물 어 봅 니 다. 입력 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

CH 0503 기 디지털 문제 (역순 대)

좋은 웹페이지 즐겨찾기