【codeforces】CF1345C Hilbert's Hotel

原题传送门

题目大意:酒店有无数间客房,给每个客人按照 (k + a_{k mod n}) 分配房间((k)可以是任意数),问能否给每个客人分配到各不相同的客房。

做题过程

题目强调了 (k mod n)是最小的非负整数,即((-1337) mod 3 = 1)(按照程序跑出来的应该是(-2),但这里是(1(-2 + 3))

(a_{k mod n})也很好理解,即(a_i)的下标一直在(0)(n-1)循环(数组的下标从(0)开始)

对于样例第4点过程分析:

0 + 3 = 3 —— k = 0

1 + 2 = 3 —— k = 1

(dots)

(两位客人都被分配到同一房间(3)

对于样例第5点过程分析:

0 + 0 = 0 —— k = 0

1 + 1 = 2 —— k = 1

2 + 0 = 2 —— k = 2,(2 mod n = 0,n = 2,a_0 = 0)

(dots)

(后两位客人被分配到相同房间(2)

题解

经过多组数据的分析,可以写出下列推导过程:

当$ k < n $时,

(0 + a_0,1 + a_1,dotsb,(n-1)+a_{n-1})

(n le k < 2n)时,

(0 + n + a_0,1 + n + a_1,dotsb, (n-1) + n + a_{n-1})

可得到:

(bn le k < (b + 1)n)时((b)为任意整数)

(0+bn+a_0,1+bn+a_1,dotsb,(n-1)+bn+a_{n-1})

调整:

(bn + (0 + a_0),bn + (1+a_1),dotsb,bn+(n-1+a_{n-1}))

要使每个数两两不相等,只有(())里面的内容不等才成立(因为都有(an)

根据取模公式,对式子(mod n)即可得到(())里的内容,注意取模得到负数的情况。

所以只需要判断(())里的内容是否相等即可。

此外,要注意(())里大于(n)的数据,因为此时可以把(n)提出来,此时就不满足(bn le k < (b + 1)n)。例子就是:样例第5个测试点。

代码:

//
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int n, T;
int num[200005];

int main()
{
    scanf("%d", &T);
    while(T--){
        bool flag = true;
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%d", &num[i]);
            num[i] += i;
            num[i] %= n;
            if(num[i] < 0) num[i] += n;
        }

        if(n == 1) puts("YES");
        else {
            sort(num, num + n);
            for(int i = 1; i < n; i++){
                if(num[i] == num[i - 1]){
                    flag = false;
                    break;
                }
            }
            if(flag) puts("YES");
            else puts("NO");
        }
    }

    return 0;
}

原文地址:https://www.cnblogs.com/Ayanowww/p/12856156.html