CF2040A Game of Division

Tag：数学

题目描述

给你一个长度为 \(n\) 的整数数组 \(a_1, a_2, \ldots, a_n\) 和一个整数数组 \(k\) 。

两个玩家正在玩一个游戏。第一个玩家选择一个索引 \(1 \le i \le n\) 。然后第二个玩家选择不同的索引 \(1 \le j \le n, i \neq j\) 。如果 \(|a_i - a_j|\) 不能被 \(k\) 整除，则第一个玩家获胜。否则，第二个玩家获胜。

我们扮演第一个玩家。确定是否可能获胜，如果可能，应该选择哪个索引 \(i\) 。

数字 \(x\) 的绝对值用 \(|x|\) 表示，如果是 \(x \ge 0\) ，则等于 \(x\) ，否则等于 \(-x\) 。

数据说明：

\(1 \leq n,k,a_i \leq 100\)

分析

因为题目中所考虑的是 \(|a_i - a_j|\) 能否被 \(k\) 整除。那么在什么时候，能被 \(k\) 整除呢？答案显而易见是当 \(a_i\) 与 \(a_j\) 相差的数为 \(k\) 的倍数的时候，这代表这两个数字在模 \(k\) 意义下相等。

所以我们直接把所有数字模 \(k\) 处理，之后用容器记录出现次数，只要模 \(k\) 之后有一个任意一个数字只出现了一次，那么就代表存在答案。

代码实现

void NeverSayNever() {
    int n,k; cin >> n >> k;
    vector<int> vec(n);
    vector<int> cnt(101,0);
    for(auto &x : vec) {
        cin >> x;
        x %= k;
        cnt[x]++;
    }
    for (int i = 0; i < n ; ++i) {
        if(cnt[vec[i]] == 1){
            cout << "YES" << endl << i + 1 << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

日志

本页面创建于 2024/1/21 10:17