Codeforces Round 941 (Div. 2) （A~D）

前言

听说前几题都是思维，赛后写一下

A. Card Exchange

题意是每次选K个相同的数，然后用k-1个任意数替换，问最少留几个数
如果一开始有k个相同的数，就能全部替换成与其他数相同，循环操作后一定只剩k-1。
判断能不能操作就行

void solve(){
    cin >> n >> k;
    map<int, int> mp;
    for(int i = 1, x; i <= n; i++){
        cin >> x;
        mp[x]++;
    }
    for(auto [a, b] : mp){
        if(b >= k){
            cout << k - 1 << endl;
            return;
        }
    }
    cout << n << endl;
}

B. Rectangle Filling

题意是黑白矩阵里，每次选一对同色点，将两个点间的所有点都染成同色，问能否全染成一个颜色
首先如果一对角同色，那显然成功
如果无论如何也不能使得对角同色，那显然错误，所以只要考虑对角有没有同色的可能就行
想把顶角染色那只能是他相邻两条边导致

string s[N];
void solve(){
    cin >> n >> m;
    int f[5];    // 4个角能否涂成黑白色，这里用二进制方便运算， 0位表示白，1位表示黑, 14对角，23对角
    for(int i = 1; i <= n; i++){
        cin >> s[i];
        s[i] = " " + s[i];
    }
    map<char, int> mp;
    mp['W'] = 1, mp['B'] = 2;
    f[1] = mp[s[1][1]];
    f[2] = mp[s[1][m]];
    f[3] = mp[s[n][1]];
    f[4] = mp[s[n][m]];
    for(int i = 1; i <= m; i++){   //这里其实只用O(n)考虑边上有没有这个颜色，但复杂度也够
        for(int j = 1; j <= n; j++){
            if(s[1][i] == s[j][m]) f[2] |= mp[s[1][i]]; 
            if(s[n][i] == s[j][m]) f[4] |= mp[s[n][i]]; 
            if(s[1][i] == s[j][1]) f[1] |= mp[s[1][i]]; 
            if(s[n][i] == s[j][1]) f[3] |= mp[s[n][i]]; 
        }
    }
    if(f[1] & f[4]) cout << "YES\n";
    else if(f[2] & f[3]) cout << "YES\n";
    else cout <<"NO\n";
}

C. Everything Nim

题意是每次选择不超过最少堆的石子数量，然后所有堆都移走这么多石子
首先如果最少石子数量是\(1\)的话，当前选手就没有选择，只能选\(1\)
然后对于最少石子大于\(1\)，先手的人可以全拿走，或者留个\(1\)给下一个人，所以有先手权的人能够对这堆大于\(1\)的石子进行操作，如果留\(1\)，那就保留先手权，反之转移先手权。
做法是对于如果出现能够选择的堆，那此时的先手一定必胜，因为他可以决定之后的由谁来先取下一堆。
然后判断一开始有没有\(1\)，有\(1\)的话只能拿\(1\)，如果是间隔\(1\)递增如 \(1，2，3，4\) 的话，取完\(1\)就会形成新的\(1\)。

void solve(){
    cin >> n;
    set<int> st;   //用来去重，重复的堆等同于一堆
    int f = 0, cnt = 0;
    for(int i = 1, x; i <= n; i++){
        cin >> x;
        st.insert(x);
        if(x == 1) f = 1;
    }
    n = st.size();
    if(n == 1 || f == 0){
        cout <<"Alice\n";
        return;
    }
    vector<int> v;
    for(auto i : st) v.push_back(i);
    for(int i = 1; i < v.size(); i++){
        if(v[i] != v[i - 1] + 1){
            cout << (v[i - 1] % 2 ? "Bob\n" : "Alice\n");
            return;
        }
    }
    cout << (n % 2 == 0 ? "Bob\n" : "Alice\n");
}

D. Missing Subsequence Sum

题意是构造一个不超过25个数的序列，使其能表示1~n中除了k之外的所有数。
感觉比C好想
25个数要表示1e6的范围，当然是考虑二进制
分成两部分来想，前半部分小于k，后半大于k,这样一旦取后面就大于k，只取前面永远小于k,想到\(n\)个二进制数能表示\(2^n - 1\)的所有数，比如现在是19，那我只要用二进制\(1,10,100,1000\)就能表示到\(15,\)，定义\(dis=k-(2^n - 1)\),然后\(16到18\)再加一个\(dis = 3\)就行了，因为前半部分全加起来也只能等于\(k - 1\),其次\(k-1-dis\leq (2^n - 1)\)所以k-1都能成功表示
后半部分先将\(k + 1\)放进答案，然后再\(2k,4k,8k,16k\)放入就好，剩下一点细节代码里

void solve(){
    cin >> n >> k;
    int len = 0, k1 = k;
    vector<int> ans;
    if(k == 1){    //1特判，因为1没有前半部分
        ans.push_back(3);
        for(int i = 1; i <= 24; i++) ans.push_back(1 << i);
    }   
    else{
        while(k1){
            k1 /= 2;
            len++;
        }
        int res = 1;
        for(int i = 1; i < len; i++){
            ans.push_back(res);
            res *= 2;
        }
        ans.push_back(k - (1 << (len - 1)));
        ans.push_back(k + 1);
        ans.push_back(3 * k); // 补充3k,因为前半部分加k + 1 = 2k,再下一步是4k，所以3k表示不到要补上
        res = 2;
        while(ans.size() < 25){
            ans.push_back(res * k);
            res *= 2;
        }
    }
    cout << 25 << endl;
    for(auto i : ans) cout << i << ' ';
    cout << endl;
}