Codeforces Round 889 (Div. 2) A-D

https://codeforces.com/contest/1855
打的太烂了，决心好好复盘

A. Dalton the Teacher

#include <bits/stdc++.h>

using namespace std;

void solve () {
    int n, cnt = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x == i) cnt++;
    }
    cout << (cnt + 1) / 2 << endl;
}

int main () {
    int t;
    cin >> t;
    while (t--)     solve ();
}

B. Longest Divisors Interval

#include <bits/stdc++.h>
#define ll long long

using namespace std;
typedef pair<ll, ll> pii;

void solve () {
    ll n, m, ans = 1;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        //if (s.count (i))    continue;
        if (n % i) {
            cout << i - 1 << endl;
            return ;
        }
    }
    cout << n << endl;
}

int main () {
    int t;
    cin >> t;
    while (t--)     solve ();
}

C1. Dual (Easy Version)

利用一个最大的正数把所有数变为正数，然后只需类似前缀和操作，把前边的数依次累加到后面的数即可。

心路历程：先是读错题以为是求最小操作次数，然后想到变为全正，但是没有注意到前缀和性质（全正的数的前缀和必然递增）

分析最大操作次数：
最小负数为 \(-20\)，最大正数为 \(1\)，时，需要 \(5\) 次把 \(1\) 变为 \(32\)，假设除了 \(1\) 以外剩下的数都是 \(-20\)，那么共需要 \(19\) 次把所有数变为正数，最后前缀和需要消耗 \(19\) 次，所以总共是 \(5+19+19=43<50\)。

若无正数，即所有数都 \(\leq0\) 的话，只需求一遍后缀和。因为负数的累加会使得数变得更小，类比正数求和去逆向思考。

#include <bits/stdc++.h>
#define ll long long

using namespace std;
typedef pair<int, int> pii;
const int N = 25;
int a[N], b[N], n;

void solve () {
    cin >> n;
    //int mi = 0;
    int s = 0;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    int it = max_element (a + 1, a + n + 1) - a, mx = a[it];
    int mi = *min_element (a + 1, a + n + 1);

    vector<pii> v;
    //变为全正
    if (mx > 0) {
        if (mi < 0) {
            mi = abs (mi);
            while (mx < mi) mx *= 2, v.push_back ({it, it});
            for (int i = 1; i <= n; i++) {
                if (a[i] < 0)   a[i] += mx, v.push_back ({i, it});
            }
        }
        //变为全正之后做一个前缀和就行
        for (int i = 2; i <= n; i++)    v.push_back ({i, i - 1});
    }
    else { //全<=0
        //对于负数做后缀和
        for (int i = n - 1; i >= 1; i--)    v.push_back ({i, i + 1});
    }
    //cout << mx << ' ';
    cout << v.size () << endl;
    
    for (auto i : v)    cout << i.first << ' ' <<  i.second << endl;
}

int main () {
    int t;
    cin >> t;
    while (t--)     solve ();
}

C2. Dual (Hard Version)

考虑在 C1 的基础上优化操作，使得最大操作次数不超过 31。
我们发现 C1 可优化的地方主要在这里：

假设除了 \(1\) 以外剩下的数都是 \(-20\)，那么共需要 \(19\) 次把所有数变为正数

怎么把这里的次数缩小呢？
我们发现此时的数组中，负数的个数要远多于正数的个数，所以可以尝试把他往全负去转化。此时变为全负的次数更少（因为负数远多于正数），共 \(1 + 19=20\)。

所以我们就得到了两种策略，正数多就把负数全转为正数，负数多就把负数全转为正数。
考虑正负数各占一半的情况：\(10\) 个 \(-20\) 和 \(10\) 个 \(1\)，把所有 \(1\) 变为负数，消耗 \(10\) 次，最后求前缀和 \(19\) 次,共 \(29\) 次。
（如果是 \(-1\) 和 \(20\) 就变为全正）

#include <bits/stdc++.h>
#define ll long long

using namespace std;
typedef pair<int, int> pii;
const int N = 25;
int a[N], b[N], n;

void solve () {
    cin >> n;
    //int mi = 0;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    int it = max_element (a + 1, a + n + 1) - a, mx = a[it];
    int it2 = min_element (a + 1, a + n + 1) - a, mi = a[it2];
    int s = mx;
    vector<pii> v;
    //变为全正
    if (mx > 0) {
        if (mi < 0) {
            mi = abs (mi);
            while (mx < mi) mx *= 2, v.push_back ({it, it});
            for (int i = 1; i <= n; i++) {
                if (a[i] < 0)   v.push_back ({i, it});
            }
        }
        //变为全正之后做一个前缀和就行
        for (int i = 2; i <= n; i++)    v.push_back ({i, i - 1});

        if (v.size () > 31) {
            v.clear ();
            //全变为负数
            ///mi<0
            mi = abs (mi);
            while (mi < s) mi *= 2, v.push_back ({it2, it2});
            for (int i = 1; i <= n; i++) {
                if (a[i] > 0)   v.push_back ({i, it2});
            }
            //cout << v.size () << endl;
            for (int i = n - 1; i >= 1; i--)    v.push_back ({i, i + 1});
        }
    }
    else { //全<=0
        //对于负数做后缀和
        for (int i = n - 1; i >= 1; i--)    v.push_back ({i, i + 1});
    }
    //cout << mx << ' ';
    cout << v.size () << endl;
    
    for (auto i : v)    cout << i.first << ' ' <<  i.second << endl;
}

int main () {
    int t;
    cin >> t;
    while (t--)     solve ();
}

D. Earn or Unlock

注意卡牌若用于激活后面的牌就不能计数了。

考虑朴素 dp：\(dp_{i, j}\) 表示操作到第 \(i\) 张牌，已经解锁了后面 \(j\) 张牌的状态是否存在。则朴素转移的复杂度是 \(O(n^2)\)，而又因为状态的值只有 \(0,1\) 两种情况，容易联想到 \(bitset\) 进行优化，滚掉第一维（感觉确实不太会用bitset）

（学习bitset卡常小技巧bushi）

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 1e5 + 5;
ll a[N], s[N], n, ans;
bitset<N*2> f; //f[i][j]: 操作到i,已经解锁了后面j张牌,滚掉第一维

int main () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i], s[i] = s[i-1] + a[i];
    
    f[a[1]] = 1, f[0] = 0, ans = a[1]; //至少拥有第一张牌
    for (int i = 2; i <= n; i++) {
        if (f[i-1])     ans = max (ans, s[i] - (i - 1)); //把值为i-1的那张用来unlock的牌拿走了
        f |= f << a[i];
        f[i-1] = 0; //操作之后把上一张牌拿走了
        //cout << ans << ' ';
    }
    //cout << ans << ' ';
    //for (int i = 0; i < 10; i++)    cout << f[i];
    for (int i = n; i < n * 2; i++) { //从n开始
        if (f[i])   ans = max (ans, s[n] - i);
    }
    cout << ans;
}

//把bitset看成一个字符串

EF to be solved