CodeforcesRound#842(Div.2)题解（A-E）-创新互联
A Greatest Convex 签到题，注意到x=k-1必定满足题意。
#includeusing namespace std;
void solve() {
int n;
cin >>n;
cout<< n - 1<< endl;
return;
}
int main() {
int n;
cin >>n;
while (n--) {
solve();
}
return 0;
} B Quick Sort 其实就是找大的不需要进行题目中sort操作的序列，那一定是按照顺序的1，2，3，4……是原排列的子序列，剩下的数字就是要进行操作的。操作数整除k并向上取整即为最终结果。
#includeusing namespace std;
void solve() {
int n, k, tp, maxs, ls = 1;
cin >>n >>k;
maxs = n + 1;
for (int i = 0; i< n; i++) {
cin >>tp;
if (maxs >tp && tp != ls) {
maxs = tp;
} else if (tp == ls)
ls++;
}
cout<< (n - maxs + k) / k<< endl;
return;
}
int main() {
int n;
cin >>n;
while (n--) {
solve();
}
return 0;
} C Elemental Decompress
题目中给出的输入是随意的，因此可能出现数字出现的次数大于等于3，这种情况一定不符合题意，需要特判。然后把出现过2次的和出现0次的数字交换，并从小开始给每个出现2次的数字配一个最小的出现0次的数字，若即使这么操作仍然发现出现0次的数字比出现2次的数字大，则不合题意。该方法时间复杂度O(n)。
另解：也可以通过排序，a[i]>=i，且所有数字出现次数不能小于等于3则符合题意，排序的时候把原位置储存成结构体或pair一起排序，然后再转化回原位置输出结果。该方法时间复杂度O(nlog(n))也可过。
#includeusing namespace std;
void solve() {
int n;
scanf("%d", &n);
int a[n + 1];
for (int i = 1; i<= n; i++)
scanf("%d", &a[i]);
int b[n + 1], cz[n + 1], cz2[n + 1];
memset(b, 0, sizeof(b));
for (int i = 1; i<= n; i++) {
b[a[i]]++;
if (b[a[i]] == 3) {
printf("NO\n");
return;
}
if (b[a[i]] == 2)
cz2[a[i]] = i;
else
cz[a[i]] = i;
}
int c[n + 1], d[n + 1];
for (int i = 1, j = 1;;) {
if (i >j) {
printf("NO\n");
return;
}
if (j >n) {
break;
}
if (b[j] == 1) {
c[cz[j]] = j;
d[cz[j]] = j;
j++;
continue;
}
if (b[j] != 2) {
j++;
continue;
}
if (b[i] != 0) {
i++;
continue;
}
c[cz2[j]] = j;
c[cz[j]] = i;
d[cz2[j]] = i;
d[cz[j]] = j;
i++;
j++;
}
printf("YES\n");
for (int i = 1; i<= n; i++) {
printf("%d", c[i]);
if (i != n)
printf(" ");
else
printf("\n");
}
for (int i = 1; i<= n; i++) {
printf("%d", d[i]);
if (i != n)
printf(" ");
else
printf("\n");
}
return;
}
int main() {
int n;
cin >>n;
while (n--) {
solve();
}
return 0;
} D Lucky Permutation
先举个例子，如n=4时，只有
2，1，3，4；
1，3，2，4；
1，2，4，3，三种符合题意。
这一定和1，2，3，4这样按顺序sort的排列相差一步操作。
我们先找将排列按顺序sort需要的swap次数，对于这个简化问题，令p[i]=i所产生的环的元素数-1为每个环按顺序sort所需的操作数。
因此，若有c个环，则n-c就是所需的操作数。
在考虑原来的问题，如果有一个环里的两个相邻的数相差1，意味着可以不用sort这两个数，因此可以少走一步。若不存在这样的情况，则需多走一步。
#includeusing namespace std;
void solve() {
int n;
cin >>n;
int p[n + 1], v[n + 1];
for (int i = 1; i<= n; i++) {
cin >>p[i];
}
memset(v, -1, sizeof(v));
int ans = n, flg = 1;
for (int i = 1; i<= n; i++) {
if (v[i] != -1)
continue;
ans--;
int j = i;
while (v[j] == -1) {
v[j] = i;
j = p[j];
}
}
for (int i = 2; i<= n; i++) {
if (v[i] == v[i - 1]) {
flg = -1;
}
}
cout<< ans + flg<< endl;
}
int main() {
int t;
cin >>t;
while (t--) {
solve();
}
return 0;
} E Partical Sorting
首先，我们发现对于任何排列都可以使用最多3次操作达成目的。
0次操作达成目的的排列个数为cnt0=1——原排列。
1次以内操作达成目的的排列个数，要么0-n区间（左闭右开，下同）内是位置正确的，要么2n-3n如此，注意这两种情况分别为（2n）！，但重合了n!，故排列个数为cnt1=2×(2n!)−(n!)。
因此，本题还需求2次以内的操作能达成目的的排列个数。
该情况下，要么最小的n个数在0-2n间，要么大的n个数在n-3n间，这样先把这个区间内的数sort一遍，然后再sort另一边，需要2次。
这两种情况分别为C（2n,n)*n!*(2n)!，并重合了一个区间。
这个重合区间要求最小n个数在0-2n间且大的n个数在n-3n间，对于这种情况，我们可以枚举n-2n区间内有i个这样的数，这样的话0-n和2n-3n内均有n-i个这样的数，最终结果为C(n,n-i)×C(n,i)×C(2n,n)−i×n!×n!×n!
故cnt2=C（2n,n)*n!*(2n)!- 求和 (C(n,n-i)×C(n,i)×C(2n,n)−i×n!×n!×n!)
总排列数显然为cnt3=(3n)!
因此最终结果为3*cnt3-cnt2-cnt1-cnt0
#includeusing namespace std;
typedef long long ll;
#define N 3000007
ll n, mod, fac[N], ifac[N];
int fpow(int x, int t = mod - 2) {
int res = 1;
for (; t; t >>= 1, x = 1ll * x * x % mod)
if (t & 1)
res = 1ll * res * x % mod;
return res;
}
int C(int n, int m) {
if (n< m)
return 0;
return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int main() {
cin >>n >>mod;
fac[0] = ifac[0] = 1;
for (int i = 1; i< N; ++i)
fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[N - 1] = fpow(fac[N - 1]);
for (int i = N - 2; i; --i)
ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
int cnt1 = (2ll * fac[2 * n] - fac[n] + mod) % mod;
int cnt2 = 2ll * fac[n] % mod * fac[2 * n] % mod * C(2 * n, n) % mod;
int k = 1ll * fac[n] * fac[n] % mod * fac[n] % mod;
for (int i = 0; i<= n; ++i)
cnt2 = (cnt2 - 1ll * C(n, i) * C(n, n - i) % mod * C(2 * n - i, n) % mod * k % mod + mod) % mod;
int cnt3 = (fac[3 * n] + mod) % mod;
printf("%lld\n", (mod * 4 + 3ll * cnt3 - cnt2 - cnt1 - 1) % mod);
return 0;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享名称：CodeforcesRound#842(Div.2)题解（A-E）-创新互联
网页URL：http://shouzuofang.com/article/hsjcg.html