题解 | #Kevin翻硬币#

Kevin is Counting Stars

https://ac.nowcoder.com/acm/contest/68258/A

欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏


D. Kevin翻硬币

比赛的时候,一直在猜结论,一共wa了17次,泪目。

但有一个想法,慢慢浮现出现来,比较硬核。

硬核解法

  • 模拟 + 环形差分

先来说下模拟,实际上从原点出发,每次走k步,在环形的n中,一定可以回到原点的。最简单的验证,就是做n次的k步,必然回到原点。

更通俗的数学证明

kx = 0 mod n

gcd(k, n) | 0 必然成立,也就说 x 有解.

根据鹊巢原理,最多走n次,就能回到原点.

为了方便处理,我们把 1-index 转换为 0-index


那剩下的核心问题是:

如何判定是否能够翻转呢?

这个问题可以抽象为,从0点每次走k,然后回到0点的过程中,[0, n - 1]中的每个数的翻转次数都是奇数? 那就一定可以。

假设当前点位t,翻转k,那相当于 [t, t + k - 1] 区间翻转次数整体+1

这里的一个难点,其实环形结构,如何处理这种跨区间的。

比如 [t, t + k - 1], t + k - 1 >= n - 1

那其实可分成两段[t, n - 1], [0, (t + k - 1) % n]做差分

这就是为什么说,环形结构的差分.

最后就是差分的常见累加计算,然后判定[0, n - 1]的数,改变次数都是奇数,那一定可行,否则不行。

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt(), k = sc.nextInt();

            // 模拟 + 环形差分
            // 构建每次走k就行,难在于可行解的判定上
            int[] diff = new int[n + 1];
            List<Integer> res = new ArrayList<>();
            int x = 0;
            do {
                res.add(x);
                diff[x]++;
                if (x + k >= n) {
                    // 跨区间,就两段
                    diff[n]--;

                    diff[0]++;
                    diff[(x + k) % n]--;
                } else {
                    diff[x + k]--;
                }
                x = (x + k) % n;
            } while (x != 0);

            // 差分验证, 如果一个数的改变次数是偶数,则无解
            boolean f = true;
            int acc = 0;
            for (int i = 0; i < n; i++) {
                acc += diff[i];
                if (acc % 2 == 0) {
                    f = false;
                    break;
                }
            }

            if (!f) {
                System.out.println(-1);
            } else {
                System.out.println(res.size());
                System.out.println(res.stream().map(y -> String.valueOf(y + 1)).collect(Collectors.joining(" ")));
            }
        }
    }

}
全部评论
diff[n]++有什么用吗
1
送花
回复 分享
发布于 2023-11-07 14:12 四川

相关推荐

4 1 评论
分享
牛客网
牛客企业服务