CodeforcesRound#842(Div.2)题解(A-E)-创新互联
A Greatest Convex 签到题,注意到x=k-1必定满足题意。
创新互联于2013年成立,是专业互联网技术服务公司,拥有项目成都网站建设、网站建设网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元萝北做网站,已为上家服务,为萝北各地企业和个人服务,联系电话:028-86922220#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)-创新互联
本文路径:http://myzitong.com/article/hsjcg.html