codeforces B. Omkar and Infinity Clock codeforces

文章图片

题目题意：给你一个 n , k n,k n,k和一个 a a a序列，你可以进行操作，计算出 a a a中的最大值 d d d，然后 a i = d ? a i a_i=d-a_i ai?=d?ai?，进行 k k k次这样的操作，求出最后的 a a a序列。
思路：我们列出操作后的序列：

第一次： b 1 , b 2 , b 3 , . . . . b n ( m a x = d ) b_1,b_2,b_3,....b_n(max = d) b1?,b2?,b3?,....bn?(max=d)
第二次： d ? b 1 , d ? b 2 , d ? b 3 , . . . . , d ? b n ( m a x = d ) d-b_1,d-b_2,d-b_3,....,d-b_n(max=d) d?b1?,d?b2?,d?b3?,....,d?bn?(max=d)
第三次： d ? ( d ? b 1 ) = b 1 , d ? ( d ? b 2 ) = b 2 , . . . . . , b n ( m a x = d ) d-(d-b_1)=b_1,d-(d-b_2)=b2,.....,b_n(max=d) d?(d?b1?)=b1?,d?(d?b2?)=b2,.....,bn?(max=d)

【codeforces B. Omkar and Infinity Clock】我们可以发现这个序列是交替的，每一次的最大值都是 d d d，第一次操作后肯定有肯定存在一个 b i = 0 b_i=0 bi?=0，这里的 d d d指的是 b b b序列中的最大值，不是 a a a序列中的，然后每一次的最大值都是 d ? ( b i = 0 ) = d d-(b_i=0)=d d?(bi?=0)=d，我们计算出这两个序列，然后判断 k k k的奇偶性就可以得出最终的序列了。

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef vector veci; typedef vector vecl; typedef pair pii; typedef pair pll; template inline void read(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return ; while (c != '-' && (c < '0' || c > '9')) c = getchar(); sgn = (c == '-') ? -1:1; ret = (c == '-') ? 0:(c - '0'); while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return ; } inline void outi(int x) {if (x > 9) outi(x / 10); putchar(x % 10 + '0'); } inline void outl(ll x) {if (x > 9) outl(x / 10); putchar(x % 10 + '0'); } const int maxn = 2e5 + 10; ll a[maxn] = {0}, b[maxn]; int main() { int t; read(t); while (t--) { ll n, k; read(n), read(k); ll Max = -1e9; for (int i = 0; i < n; i++) { read(a[i]); Max = max(a[i], Max); } ll Max2 = -1e18; for (int i = 0; i < n; i++) a[i] = Max - a[i], Max2 = max(a[i], Max2); for (int i = 0; i < n; i++) b[i] = Max2 - a[i]; if (k & 1) for (int i = 0; i < n; i++) printf("%lld ", a[i]); else for (int i = 0; i < n; i++) printf("%lld ", b[i]); printf("\n"); } return 0; } /* 1 5 20 5 -1 4 2 0 */