Codeforces Round #842 (Div. 2) A-E

A - Greatest Convex

题目链接：Problem - A - Codeforces

解题思路：x! + (x-1)! = (x-1)! (x + 1)，所以当x == k - 一时，必然可以整除。

#include<bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3f#define lson l,mid,rt<<1#define rson mid+1,r,(rt<<1)|1typedeffe long long ll;const int mx = 2e5 + 10;const int mod = 1e9 + 7; int main() {int t, n;scanf("%d", &t);while (t--) {scanf("%d", &n);printf("%d\n", n-1);}return 0;}

B - Quick Sort

题目链接：Problem - B - Codeforces

解题思路：计算1、2、3...增加序列长度，这个不用动，其他的可以放在后面。

#include<bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3f#define lson l,mid,rt<<1#define rson mid+1,r,(rt<<1)|1typedeffe long long ll;const int mx = 2e5 + 10;const int mod = 1e9 + 7;int a[mx];int pos[mx];int main() {int t, n, k;scanf("%d", &t);while (t--) {scanf("%d%d", &n, &k);for (int i=1;i<=n;i++) {scanf("%d", a+i);pos[a[i]] = i;}int l = 1;while (l < n && pos[l] < pos[l+1]) {l++;}if (l == n)printf("0\n");elseprintf("%d\n", 1 + (n - l - 1) / k);}return 0;}

C - Elemental Decompress

题目链接：Problem - C - Codeforces

解决问题的想法：从给定的序列中可以得到肯定a、B两个序列中一个位置的值与之相同，因此首先将其放置在a中。如果a已经存在，则将其放置在B中。如果它们都存在，那就没有解决办法了。然后继续贪婪。一个位置的另一个序列的值应尽可能大，即x<=a[i]就行。

#include<bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3f#define lson l,mid,rt<<1#define rson mid+1,r,(rt<<1)|1typedeffe long long ll;const int mx = 2e5 + 10;const int mod = 1e9 + 7;int a[mx];int b[mx][2];bool v[mx];set <int> st[2];int main() {int t, n, k;scanf("%d", &t);while (t--) {st[0].clear();st[1].clear();scanf("%d", &n);for (int i=1;i<=n;i++) {st[0].insert(i);st[1].insert(i);scanf("%d", a+i);}bool flag = 1;for (int i=1;i<=n;i++) {int id;if (st[0].count(a[i])) {id = 0;} else if (st[1].count(a[i])) {id = 1;} else {flag = 0;break;}b[i][id] = a[i];v[i] = id ^ 1;st[id].erase(a[i]);}if (flag == 0) {puts("NO");continue;}for (int i=1; i<=n; i++) {int id = v[i];auto it = st[id].upper_bound(a[i]);if (it == st[id].begin()) {flag = 0;break;}it--;b[i][id] = *it;st[id].erase(it);}if (flag == 0)puts("NO");else {puts("YES");for (int i=0; i<2;i++) {for (int j=1;j<=n;j++) {printf("%d ", b[j][i]);}puts("");}}}return 0;}

D - Lucky Permutation

题目链接：Problem - D - Codeforces

解决问题的想法:根据位置和对应值建立一个向边，可以得到几个圈。我们每次操作都可以减少一个点，让它自环。两个圈也可以合并，但这个操作显然毫无意义。最后要留下的是一对相邻值形成的环。因此，如果一个圆圈中有两个相邻值，则操作后只能留下两个相邻值。如果没有，则需要添加另一个操作，以将两个相邻自环的点变成一个圆。

#include<bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3f#define lson l,mid,rt<<1#define rson mid+1,r,(rt<<1)|1typedeffe long long ll;const int mx = 2e5 + 10;const int mod = 1e9 + 7;set<int> st;bool vis[mx];int a[mx];int main() {int t, n, k;scanf("%d", &t);while (t--) {scanf("%d", &n);for (int i=1;i<=n;i++) {scanf("%d", a+i);vis[i] = 0;}bool flag = 0;int ans = 0;for (int i=1;i<=n;i++) {if (!vis[i]) {st.clear();int j = i, last = -1;while (!vis[j]) {vis[j] = 1;st.insert(j);j = a[j];}for (auto it: st) {if (it == last + 1) {flag = 1;break;}last = it;}ans += st.size() - 1;}}//printf("%d %d\n", ans, flag);if (ans == 0)puts("1");elseprintf("%d\n", ans - (flag? 1:-1));}return 0;}

E - Partial Sorting

题目链接：Problem - E - Codeforces

解决问题的想法：你可以得出最多只需要3次操作，0次只有当序列有序时。所以我们只需要讨论1、2、3.我们可以将三段分别标记为1、2、3。

1） 1的情况必须是1段是有序的，或者3段是有序的。所以在已知的一段有序的情况下，其他的排列是(2n)！ - 1.减1是因为排除了完全有序的0。因为1和3都可以，所以需要*2。但是一段和三段都是有序的，要减去两段的全排列，n! - 1.同上减一的原因。

2)计算2的情况其实和1差不多，都是对称的，需要容斥减一重复。以1段为例，1-n的数量应该在1-2段以内，第三段不是(2n+1~3n)有序，否则是第一种情况。然后就有了

，减一是排除第一段1-n完全有序的情况。后减n！排除第三段(2n+1~3n)的有序情况。因为对称性，第三段也是如此，所以*2。但多计算一次1-n的数量在1和2段内，(2n+1~3n)也在2和3段内。所以要减去这种情况。枚举1-n的数量可以在2段中，然后其他的可以使用排列组合。时间复杂度O(nlogn)。

3）3n! 减去0、1、2的个数是3的个数。

#include<bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3f#define lson l,mid,rt<<1#define rson mid+1,r,(rt<<1)|1typedeffe long long ll;const int mx = 3e6 + 10;ll c[mx], d[mx];ll qpow(ll x, ll y, int mod) {ll ans = 1;while (y) {if (y & 1) ans = ans * x % mod;y >>= 1;x = x * x % mod;}return ans;}int main() {int n, m;scanf("%d%d", &n, &m);d[0] = c[0] = 1;for (int i=1;i<=3*n;i++)c[i] = c[i-1] * i % m;ll ans = 0, sum = 1;// 只需要一次 ans += (c[2 * n] - 1) * 2 % m;ans -= (c[n] - 1) % m;ans = (ans + m) % m;sum = (sum + ans) % m;// 2次 ll c_2n_n = c[2*n] * qpow(c[n], m - 2, m) % m * qpow(c[n], m - 2, m) % m;ll v = (c_2n_n * c[n] % m - 1) % m * (c[2*n] - c[n] + m) % m;ans += v * 2 * 2 % m;sum += v * 2 % m;for (int i=1;i<=n;i++)d[i] = qpow(c[i], m - 2, m);// 相同的部分被容斥剪掉，也就是说，两边的操作顺序都可以。 for (int i=1;i<=n;i++) {ll c_n_i = c[n] * d[n-i] % m * d[i] % m;ll c_2ni_n = c[2*n-i] * d[n-i] % m * d[n] % m; // c[2n-i,n]////两边都可以操作的情况 v = c_n_i * c_n_i % m * c[i] % m;v = v * c_n_i % m * c[n-i] % m; // c[n, n-i]v = v * (c_2ni_n * c[n] % m - 1) % m * c[n] % m;ans = (ans - v * 2 + m) % m;sum = (sum - v + m) % m; }ll c_2ni_n = c[2*n] * qpow(c[n], m - 2, m) % m * qpow(c[n], m - 2, m) % m; v = (c[n] - 1) * (c_2ni_n * c[n] % m - 1) % m * c[n] % m; //1-n全在第一个范围内 ans = (ans - v * 2 + m) % m;sum = (sum - v + m) % m; // 三次ans += (c[3*n] - sum + m) * 3 % m;printf("%lld\n", (ans + m) % m);return 0;}