跳转至

CF1392B

知识点

  • 模拟

题意简述

给定一个长度为 \(n\) 的整数数列 \(\{a_n\}\),我们定义一次操作为:

  • \(d \gets \max\{a_i\}\)
  • \(\forall i \in [1, n], a_i \gets d - a_i\)

\(k\) 次操作后的序列1

数据范围:\(1 \le n \le 2\cdot 10^5\)\(1 \le k \le 10^{18}\)\(-10^9 \le a_i \le 10^9\)

解题思路

一道非常有意思的性质题。

注意到第 \(k_0\) 次操作时选出了最大值 \(d\),假设此时有最小值 \(h\),那么下一轮的最大值,一定是这一轮的最大值减去这一轮的最小值得到的,即 \(d - h\)

因此第 \(k_0\) 次操作后序列会变成 \(\{d - a_n\}\)

\(k_0 + 1\) 次操作后序列会变成 \(\{(d - h) - (d - a_n)\}\),即 \(\{a_n - h\}\)

以此类推,令 \(d\) 表示数列中最大值,\(h\) 表示数列中最小值,那么:

\(2 | k\),则序列为 \(\{a_n - h\}\);否则序列为 \(\{d - a_n\}\)

代码实现

核心部分已用高亮标出。

Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define LL long long

namespace io {
    template <typename T> inline void read(T & _x) {
        int f = 0, ch; _x = 0;
        while(!isdigit(ch = getchar())) f |= ch == '-';
        while(isdigit(ch)) _x = _x * 10 + ch - '0', ch = getchar();
        if(f) _x = -_x;
    }
    template <typename T, typename ... Args> inline void read(T &_f, Args& ... args) {
        read(_f), read(args ...);
    }
    inline void _deal(char ch) { putchar(ch); }
    template <typename T> inline void _deal(T _x) {
        if (_x < 0) putchar('-'), _x = -_x;
        if (_x > 9) _deal(_x / 10);
        putchar(_x % 10 + '0');
    }
    inline void write() {}
    template <typename T, typename ... Args> inline void write(T _f, Args ... args) {
        _deal(_f), write(args...);
    }
}

const int N = 2e5 + 5;

int n;
LL k, a[N];

int32_t main() {
    int __tests;
    scanf("%d", &__tests);
    while(__tests--) {
        scanf("%d %lld", &n, &k);
        for(int i = 1; i <= n; ++i)
            scanf("%lld", &a[i]);
        int max1 = 1, min1 = 1;
        for(int i = 1; i <= n; ++i) {
            if(a[i] > a[max1])
                max1 = i;
            if(a[i] < a[min1])
                min1 = i;
        }
        if(k & 1) {
            for(int i = 1; i <= n; ++i)
                printf("%lld ", a[max1] - a[i]);
        }
        else {
            for(int i = 1; i <= n; ++i)
                printf("%lld ", a[i] - a[min1]);
        }
        puts("");
    }
    return 0;
}