Codeforces Round #740

A. Simply Strange Sort

• 题意

给一个长度为\(n\)的数组\(A_i\),开始为S = 1，然后每次加1.

1. 当\(S\)为奇数,\(when\ a_{odd_i} > a_{odd_i + 1}\)，交换，即(1,2; 3,4; 5,6)这样。
2. 当\(S\)为偶数,\(when\ a_{even_i} > a_{even_i + 1}\)，交换。

• 思路

\(n\)最多只有1000，嘿嘿
两层循环，直接暴力就完了。

code :

int a[N], st[N];
void solve(){
    int n;
    cin >> n;
    fep(i,1,n) cin >> a[i], st[a[i]] = i;
    int ans = 0;
    int now = 1;
    while(1) {
        bool flag = 0;
        for(int i = 1;i <= n;i ++) {
            if(st[i] == i) {
                continue;
            }
            flag = 1;
        }
        if(!flag) break;
        ans ++;
        if(now & 1) {
            for(int i = 1;i < n;i += 2) {
                if(a[i] > a[i + 1]) {
                    st[a[i + 1]] = i;
                    st[a[i]] = i + 1;
                    swap(a[i], a[i + 1]);
                }
            }
        }else {
            for(int i = 2;i < n;i += 2) {
                if(a[i] > a[i + 1]) {
                    st[a[i + 1]] = i;
                    st[a[i]] = i + 1;
                    swap(a[i], a[i + 1]);
                }
            }
        }now ++;
    }
    cout << ans << endl;
}

B. Charmed by the Game

• 题意

给你两个数字\(a\),\(b\)，然后序列不动的情况下是\(A,B,A,B,A,B\)或者\(B,A,B,A,B,A\)，那么你需要将整个序列变成\(a\)个\(A\),\(b\)个\(B\)，并输出有多少种改变的情况。
例如\(2,1 = A B A(0), B A A(1), A A B(2), A B A(3)\) 4种。

• 思路

分奇偶判断，发现偶数一开始的序列定死了，即A 的个数 = B 的个数，那么只能需改偶数次的情况。
然而奇数却在边界之内都能取，因为可以改变A,B的个数，就可以取各种情况。然后求边界输出即可。

code :

void solve(){
    int a,b;
    cin >> a >> b;
    if(a == b) {
        cout << (a + b) / 2 + 1 << endl;
        for(int i = 0;i <= a + b;i += 2) {
            cout << i << ' ';
        }
        cout << endl;
        return;
    }
    int k = a + b;
    int d = abs(a - b);
    if(k % 2 == 0) {
        d = d / 2;
        cout << (k - d - d) / 2 + 1 << endl;
        for(int i = d;i <= k - d;i += 2) {
            cout << i << ' ';
        }
        cout << endl;
    }else {
        d = d / 2;
        cout << k - d - d + 1 << endl;
        for(int i = d;i <= k - d;i ++) {
            cout << i << ' ';
        }
        cout << endl;
    }
}

C. Deep Down Below

• 题意

有\(n\)个洞穴,每个洞穴有\(k_i\)只怪物，每只怪物防御力\(a_{k_i,k_{i,j}}\)。而且每打败一个怪物力量加1，问开始至少需要多少力量才能通关。

• 思路

贪心。。
记录需要通过每个洞穴的最低力量，记录其中的最大值，然后按力量排序，贪心修改即可。

code :

pii p[N];

void solve(){
    int n;
    cin >> n;
    int maxn = 0;
    fep(i,1,n) {
        cin >> p[i].second;
        p[i].first = 0;
        int x;
        fep(j,1,p[i].second) cin >> x, p[i].first = max(p[i].first, x - j + 2);
        maxn = max(maxn, p[i].first);
    }
    sort(p + 1,p + 1 + n);
    reverse(p + 1,p + 1 + n);
    fep(i,2,n) {
        if(maxn - p[i].second > p[i].first) maxn -= p[i].second;
        else {
            maxn = p[i].first;
        }
    }
    cout << maxn << endl;
}

D1. Up the Strip

• 题意

给你一个数\(n\)，每一步，可以减去从\(1 \to n - 1\)中任意数，也可以除\(2 \to n\)(下取整)之中的任意数，问\(n\)变成1有多少种方案。

• 思路

对每个数进行分解
如: 减法到达的 : f[5] += f[4] + f[3] + f[2] + f[1];
除法到达的: f[5] += f[2] + f[1] + f[1] + f[1];
那么减法到的取个前缀和就可以实现。
然后除法的可以\(\sqrt{n}\)求所有的约数，然后后面连续的部分用个整除分块的性质即可，也是\(O(\sqrt{n})\)，(直接整个数论分块也可)，即总复杂度为\(O(n * \sqrt{n})\)。

code :

void solve(){
    int n;
    ans = 0;
    cin >> n >> mod;
    f[1] = 1, f[2] = 2, f[3] = 5, f[4] = 12;
    s[1] = 0, s[2] = 2, s[3] = 7, s[4] = 19;
    fep(i,5,n) {
        f[i] = 1;
        f[i] = (f[i] + s[i - 1]) % mod;
        int j;
        for(j = 2;j * j <= i;j ++) { // 约数
            f[i] = (f[i] + f[i / j]) % mod;
        }
        while(j < i) { // 整除分块
            int k = i / j;
            int d = i / k;
            f[i] = (f[i] + 1LL * (d - j + 1) * f[k]) % mod;
            j = i / k;
            j ++;
        }
        s[i] = (s[i - 1] + f[i]) % mod;
    }
    cout << f[n] << endl;
}

D2. Up the Strip

• 题意

同上

• 思路

慢慢的再去挖掘其中的性质，那么发现，如 \(99\)中有一个 \(33\)，\(100\)里也有33，一直到\(34 * 3\)之前的数都有一个\(33\)对吧，然后到了\(34 * 3\)后就从从\(33 \to 34\)，那么发现这个除数的变化是和约数有关的。
那么在列出一些例子除数部分
11 : 5 3 2 2 1 1 1 1 1 1
12 : 6 4 3 2 2 1 1 1 1 1
然后发现，如果一个数是偶数，那么肯定会比前一个数少一个1，且那个1是会变成2的(11 / 6 = 1， 12 / 6 = 2)，那么其实就是找到每个数的约数(无1)，如: 12 中 6 4 3 2都是约数,那么在计算它之前，12 : \((6 - 5, 4 - 3, 3 - 2, 2 - 1) + f[11] = 5,3,2,2,1,1,1,1,1 \to 6,4,3, 2, 2, 1, 1, 1, 1, 1\)​​​然后就找约数即可，然后减去的部分也要加一个f[11]即可算答案。

即如果一个数有\(k\)个(不含1和本身的)约数，那么\(n / k_i\)的的值，一定比前一个多 \(1\)，妙啊

code :

ll f[N], s[N];
void solve(){
    int n;
    cin >> n >> mod;
    f[1] = 1;
    for(int i = 2;i <= n;i ++) {
        s[i] = (s[i] + s[i - 1]) % mod;
        s[i] = (s[i] + f[1]) % mod;
        s[i] = (s[i] + f[i - 1]) % mod;
        f[i] = s[i];
        for(int j = 2 * i;j <= n;j += i) {
            s[j] = (s[j] + f[i] - f[i - 1] + 2 * mod) % mod;
        }
    }
    cout << f[n] << endl;
}

E. Bottom-Tier Reversals

• 题意

给你一个长度为\(n\)(n 为奇数)的数列A，你可以选择一个奇数p
令\(a_1,a_2,a_3,a_4 \cdots,a_p \to a_p,a_{p-1},\cdots,a_2,a_1\)
需要你输出操作的步骤即次数，且次数不超过\(\frac{5n}{2}\)次。

• 思路

在纸上模拟一下，其实刚刚好那么多次，y1s1,这题没上一题恶心
偶数不在偶数位置就是错的。。
从后往前找，每次确定最大两个数，\(a_n\)转至头，然后在把\(a_n\)转到\(a_n - 1\)之前，然后整个选择\(pos[a_n - 1] + 1\)选择，然后在选择3旋转，然后就是\(n,n-1,\cdots\),然后在旋转至尾部确定最大的一段数并之后不再动它，重复\(n / 2\)次即可。

code :

int a[N];
int st[N];
vi ans;

void wk(int p){
    ans.push_back(p);
    for(int i = 1;i <= p / 2;i ++) {
        swap(st[a[i]], st[a[p - i + 1]]);
        swap(a[i], a[p - i + 1]);
    }
}
void solve(){
    int n;
    cin >> n;
    
    fep(i,1,n) cin >> a[i], st[a[i]] = i;
    fep(i,1,n) {
        if(a[i] % 2 == 0 && (i & 1)) {
            cout << "-1" << endl;
            return;
        }
    }
    for(int i = n;i > 1;i -= 2) {
        int pos = st[i];
        wk(pos);
        int p = st[i - 1];
        wk(p - 1);
        wk(p + 1);
        wk(3);
        wk(i);
    }
    cout << ans.size() << endl;
    for(auto it : ans) {
        cout << it << ' ';
    }
    if(ans.size())
    cout << endl;
    ans.clear();
}