CodeforcesRound#842(Div.2)題解（A-E）-創(chuàng)新互聯(lián)

A Greatest Convex 簽到題，注意到x=k-1必定滿足題意。

創(chuàng)新互聯(lián)于2013年成立，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢想脫穎而出為使命，1280元蘿北做網(wǎng)站,已為上家服務(wù),為蘿北各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話: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 其實(shí)就是找大的不需要進(jìn)行題目中sort操作的序列，那一定是按照順序的1，2，3，4……是原排列的子序列，剩下的數(shù)字就是要進(jìn)行操作的。操作數(shù)整除k并向上取整即為最終結(jié)果。

#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

題目中給出的輸入是隨意的，因此可能出現(xiàn)數(shù)字出現(xiàn)的次數(shù)大于等于3，這種情況一定不符合題意，需要特判。然后把出現(xiàn)過2次的和出現(xiàn)0次的數(shù)字交換，并從小開始給每個(gè)出現(xiàn)2次的數(shù)字配一個(gè)最小的出現(xiàn)0次的數(shù)字，若即使這么操作仍然發(fā)現(xiàn)出現(xiàn)0次的數(shù)字比出現(xiàn)2次的數(shù)字大，則不合題意。該方法時(shí)間復(fù)雜度O(n)。

另解：也可以通過排序，a[i]>=i，且所有數(shù)字出現(xiàn)次數(shù)不能小于等于3則符合題意，排序的時(shí)候把原位置儲(chǔ)存成結(jié)構(gòu)體或pair一起排序，然后再轉(zhuǎn)化回原位置輸出結(jié)果。該方法時(shí)間復(fù)雜度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

先舉個(gè)例子，如n=4時(shí)，只有

2，1，3，4；

1，3，2，4；

1，2，4，3，三種符合題意。

這一定和1，2，3，4這樣按順序sort的排列相差一步操作。

我們先找將排列按順序sort需要的swap次數(shù)，對于這個(gè)簡化問題，令p[i]=i所產(chǎn)生的環(huán)的元素?cái)?shù)-1為每個(gè)環(huán)按順序sort所需的操作數(shù)。

因此，若有c個(gè)環(huán)，則n-c就是所需的操作數(shù)。

在考慮原來的問題，如果有一個(gè)環(huán)里的兩個(gè)相鄰的數(shù)相差1，意味著可以不用sort這兩個(gè)數(shù)，因此可以少走一步。若不存在這樣的情況，則需多走一步。

#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

首先，我們發(fā)現(xiàn)對于任何排列都可以使用最多3次操作達(dá)成目的。

0次操作達(dá)成目的的排列個(gè)數(shù)為cnt0=1——原排列。

1次以內(nèi)操作達(dá)成目的的排列個(gè)數(shù)，要么0-n區(qū)間（左閉右開，下同）內(nèi)是位置正確的，要么2n-3n如此，注意這兩種情況分別為（2n）！，但重合了n!，故排列個(gè)數(shù)為cnt1=2×(2n!)?(n!)。

因此，本題還需求2次以內(nèi)的操作能達(dá)成目的的排列個(gè)數(shù)。

該情況下，要么最小的n個(gè)數(shù)在0-2n間，要么大的n個(gè)數(shù)在n-3n間，這樣先把這個(gè)區(qū)間內(nèi)的數(shù)sort一遍，然后再sort另一邊，需要2次。

這兩種情況分別為C（2n,n)*n!*(2n)!，并重合了一個(gè)區(qū)間。

這個(gè)重合區(qū)間要求最小n個(gè)數(shù)在0-2n間且大的n個(gè)數(shù)在n-3n間，對于這種情況，我們可以枚舉n-2n區(qū)間內(nèi)有i個(gè)這樣的數(shù)，這樣的話0-n和2n-3n內(nèi)均有n-i個(gè)這樣的數(shù)，最終結(jié)果為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!)

總排列數(shù)顯然為cnt3=(3n)!

因此最終結(jié)果為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;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前名稱：CodeforcesRound#842(Div.2)題解（A-E）-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://bm7419.com/article26/hsjcg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、域名注冊、網(wǎng)站排名、響應(yīng)式網(wǎng)站、網(wǎng)站設(shè)計(jì)公司、品牌網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

成都網(wǎng)站建設(shè)公司