Recollect Numbers 有 2n 张卡片，上面分别写着数字 1,1,2,2,…,n,n。换句话说，对于每个 j=1,2,…,n，恰好有两张卡片写着 j。每张卡片正面只写了一个数字。 你要玩一个翻牌游戏。初始时，所有 2n 张卡片都背面朝上（没有数字的那一面）。每一回合，你恰好翻开两张卡片。如果这两张卡片上的数字相同，就把它们丢弃；否则，把它们翻回背面朝上。当所有 2n 张卡片都被丢弃时，你就赢了。注意：你不必同时翻开两张牌，所以在看到第一张牌的数字后，你可以根据它来决定第二张要翻哪一张。 考虑下面这个“贪心”算法来玩这个游戏。初始时，2n 张卡片以任意顺序排成一行。然后每回合的策略如下： 如果有两张你之前翻开过且数字相同的卡片，就翻开那两张（配对丢弃它们）。 否则，翻开至今从未翻开过的最靠左的那张牌作为第一张。假设这张牌的数字是 x。 之后，如果之前已经翻开过另一张数字为 x 的牌，就翻开那一张（配对）。 否则，翻开至今从未翻开过（包括本回合刚翻的第一张也不算已翻开）的最靠左的那张牌作为第二张。 可以证明，这个算法在每一回合的策略都是唯一确定的。 你需要解决关于上述算法的以下问题： 给定 n 和 k，请找出一个 2n 张卡片的排列顺序，使得上述算法恰好需要 k 回合才能赢下游戏。 另外，如果这样的排列不存在，请报告出来。 做法及思路 不难想到 1 1 2 2 3 3 可以最小次数。即 n 次 Try 1 2 3 1 2 3 但是样例都过不去。 最多的次数：因为每个数字来说，第一次是得知数字是多少，第二次是删掉这对数字。因此是 n / 2 + n 但是不是这样，我们发现第一次得知数字是多少，第二次的时候没有办法直接删掉。因为他是被翻牌的一对数字中的后一个。因此没有办法直接删这对数字，还要重新删一次。 发现可以用 2 1 3 1 4 2 5 3 6 4 7 5 6 7 来构造。其实是读了样例才想到的。此时几乎所有数字，都需要两次才能被消除。 然后找到规律以后就枚举 + 构造。 ...
Hello_world
I mean is it true?
Codeforces Round 1077 Restricted Sorting
赛时不会做。知道3个数字时， k 可以等于第二小的，但是没办法推广了。 比如： 5,3,2 k = 2 的时候： 5,3,2 2,3,5 2,5,3 5,2,3 下面不会推广了。麻了。想了很多的错误答案。 比如去找第二小的逆序对，其实只是观察到 3 个数字时这种的是逆序对，然后又是第二小的作为答案，就直接当成结论做了。WA。反正也不知道该咋做，就瞎猜了，樂。 标答 任意三元组 (Max, Min, p)，当 k = max(Max - p, p - Min) 的时候。这时候 p 就可以换到任意一个位置。三元组可以以任意一个顺序排列。 考虑有很多个 p: p1, p2, … pn。当 k = min(max(Max - p1, p1- Min), max(Max - p2, p2 - Min) …) 时，可以构造出任意一种排列方法。 因此，对于所有不在有序后位置的元素，也就是 a[i] != sort(a)[i]。都当做 p，然后去找到最小的 k。 Code #include <bits/stdc++.h> #define int long long using namespace std; void solve() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } auto b = a; sort(b.begin(), b.end());z if (a == b) { cout << -1 << endl;return; } int Min = b[0], Max = b[n-1]; vector<int> temp; for (int i = 0; i < n; i++) { if (a[i] != b[i]) temp.push_back(b[i]); } int ans = LONG_LONG_MAX; for (auto v: temp) { ans = min(ans, max(v - Min, Max - v)); } cout << ans << endl; } signed main() { int T; cin >> T; while (T--) { solve(); } }
Codeforces Round 1072 (Div. 3) E. Exquisite Array
2184E 寻找有多少个子数组满足 k-exquisite，即相邻数字的差 > k。对任意 k [0, n-1] 都要有个解。 题解 不难想到 k 可以从大到小构建。 先新建差分数组，再按照其值从大到小排序，差分值为第一关键字降序， pos 第二关键字升序 我们发现，比如假设我们算好了 k = n - 1，当 k = n - 2 的时候，可以通过算贡献的方式，计算出新增的贡献。 可以发现当我们做到 k 时，我们从左到右枚举前面的 >= k 连续段任意一个 lpos 都会作为左端点，k 作为右端点，成为一个贡献。 而右边大于 k 的连续的都可以作为右断点， k 和 k 左边的 >= k 的连续段作为右断点。假设 k 左边的满足 >=k 的连续段长度为 l,右边连续段满足 >k 的的长度为 r。那么新增的贡献为 (lok + 1 + rok * (lok + 1))。 考虑边界情况，即 k = n - 1 的时候，我们发现这种规律也试用。 ...