近期刷题总结

Codeforces Round 1045 (Div. 2)
 

Problem - B - Codeforces
这个题目可以用 k + 1 作为 gcd 的最终结果。

为什么呢？因为 (k + 1) ≡ 0 (mod k + 1) 然后根据同余的定义可以变为 k ≡ -1（mod k + 1）。后续代换非常方便。

然后就是接着替换了。 我们可以看成是 ai + k * ci ，然后根据上面的式子k ≡ -1（mod k + 1），我们可以写成是 ai + (-1) * ci ≡ 0 (mod k + 1), 然后就可以变化成为 ci ≡ ai （mod k + 1）。

到这里，我们要求的 ci 就出来了，就是等于 ai % (k + 1)。

void solve()
{int n, k; cin >> n >> k;vector<int> a(n + 1);for (int i = 1; i <= n; i ++) cin >> a[i];for (int i = 1; i <= n; i ++){a[i] += k * (a[i] % (k + 1));cout << a[i] << " ";}cout << "\n";
}

Problem - C - Codeforces

这个题目可以先研究小的数组，如下标为 l，l + 1，r 的数组，并且l 和 r 是奇数。我们可以发现要满足整个条件，只需要满足,al + ar <= al + 1，并且 al < al+1 即可。

我们可以用逆向思维，假设有一个已经操作完成的数组b[N],很容易可以知道，偶数下标的数是不能被减的，所以这些下标的数都是 b[i] = a[i] 即可。奇数下标的数我们要尽量的大。

然后我们要满足上面的条件，要从小到大来依次满足所有的这个条件。假设遍历到的奇数下标为 i，然后需要满足 b[i-2] + b[i] < a[i - 1] 这个条件，b[i - 2] 是之前已经放置好的奇数 b 数组的数，a[i - 1] 是之前就没有变的。通过简单变换我们可以得 b[i] < a[i - 1] - b[i - 2]。

第二个条件就是 b[i] < a[i + 1] ，相邻的两个数，奇数一定小于偶数。满足这两个条件就可以了。