锐评

惨淡的两题结尾，而且B题还错了两发，因此连1000分都上不去，C题构造还是没想出来，感觉二进制构造是弱项了。

A. Split the Multiset

Input

Output

Example

input

output

Note

思路

这个题感觉算是比较难的A题了，14分钟做出来的时候能排5000名，其实思路蛮简单，是把不为 1 的数拆成 k 个数之和的形式即可，其实每次只要拆成 k - 1 个 1 和一个最大的数即可。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n, k;

void solve() {
	cin >> n >> k;
    if (n <= k) {//判断是否能一步拆出来
        cout << 1 << "\n";
        return;
    }else {
        int ans = 0;
        while(n >= k) {
            n -= k - 1;//每次拆成 k - 1 个 1和剩下的，直到不够
            ans ++;
        }
        if (n > 1) ans ++;//如果等于 1，就不用加一步
        cout << ans << "\n";
   }
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) solve();
	return 0;
}

B. Make Majority

Example

input

output

No
Yes
No
Yes
No

Note

思路

刚开始想了很久的题，先是因为不知名原因让我 O(n) 的情况下 T 了，然后又是没有初始化全局变量又 WA 一次，如果没有这两个错误，多的不说还是可以上 1000 分的。

其实这道题就是问你最终能不能合成1，就算是1的数量和0的数量相同，也不能合成1，说明1和0去一比一消耗是比较亏的，于是我们消除连续的 0，这样的话我们就可以得到的字符串就是 0 旁边必定有 1，但是 1 可以连续。如果再想消除 0 就一定至少是 1 0 1 消除为 1，还是一比一消耗，这样比较亏，因此这样就是最后比较的情况，再数 0 和 1 的个数，判断能否消为 1 。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n;
int pre0, pre1;
map<int, int> st;

void solve() {
	string s; 
    cin >> n >> s;
    st.clear();
    pre0 = 0, pre1 = 0;
    for (int i = 0; i < n; ++ i) {
        if (s[i] == '0') pre0 = pre0 + 1;
        else pre1 = pre1 + 1;
    }
    if (pre1 > pre0) {
        cout << "Yes\n";
        return;
    }
    pre0 = 0, pre1 = 0;
    for (int i = 0; i < n - 1; ++ i) {
        if (s[i] == '0' && s[i + 1] == '0') st[i] = 1;
    }
    string ss;
    for (int i = 0; i < n; ++ i) {
        if (st[i] == 0) {//说明是不删的
            if (s[i] == '0') pre0 ++;
            else pre1 ++;
        }
    }
    if (pre1 > pre0) cout << "Yes\n";
    else cout << "No\n";
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) solve();
	return 0;
}

C. Increasing Sequence with Fixed OR

Example

input

output

1
1
3
1 2 3
4
4 10 12 14
5
7 18 21 22 23

思路

卡住我的构造，规律是如果 n = 1 那长度为 1，序列只有一个 1 ，否则长度为 k + 1，k 是 n 的二进制中 1 的个数，每个数分别为 n - 2^k_ⁱ，k_i是二进制中 1 的位次。没有科学的证明，找规律出来的。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n;

void solve() {
	cin >> n;
    vector<int> v;
    if (n == 1) {
        cout << "1\n";
        cout << "1\n";
        return;
    }
    
    for (int i = 60; i >= 0; i --) {
        int p = 1ll << i;
        if (n & p && n != p) {
            v.push_back(n - p);
        }
    }
    v.push_back(n);
    cout << v.size() << "\n";
    for (int i = 0; i < v.size(); ++ i) cout << v[i] << " ";

    cout << "\n";
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) solve();
	return 0;
}

顺便附带一下大佬的优质码风：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n;

void solve() {
	cin >> n;
    int ans = __builtin_popcountll(n);
    if (ans == 1) {
        cout << 1 << "\n";
        cout << ans << "\n";
    } else {
        cout << ans + 1 << "\n";
        for (int i = 60; i >= 0; -- i) {
            if (n >> i & 1) {
                cout << (n ^ (1ll << i)) << " ";
            }
        }
        cout << n << "\n";
    }
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) solve();
	return 0;
}

__builtin_popcount(int x)是求二进制中 1 的个数的函数，用熟练也能避免手写了，加ll说是为了防止爆掉hhh，n ^ (1ll << i)写的也非常巧妙，不愧是大佬。

D. The Omnipotent Monster Killer

没看太懂，树上dfs+dp，属实没看懂，感觉1900才能稳稳搓出来。