Contestant~. Rank 955. Rating +11.有种瓶颈期的美
A. Buttons
题意
给定三种只能按一次的按钮，按钮 \(a\) 只能被 \(First\) 按，按钮 \(b\) 只能被 \(Second\) 按下，按钮 \(c\) 能被两个人按下。
无法按按钮的玩家输。输出赢者。
思路
\(First\) 能按 \(a + \lceil \frac{c}{2} \rceil\) 个按钮，\(Second\) 能按 \(b + \lfloor \frac{c}{2} \rfloor\) 个按钮，比较大小即可。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int a, b, c;
cin >> a >> b >> c;
c %= 2;
a += c;
cout << (a <= b ? "Second\n" : "First\n");
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}当然不是 \(a+b+c\) 的奇偶性了
B. The Walkway
题意
给定一个数轴，数轴上有 \(m\) 个点上有卖家。
\(A\) 从 \(1\) 走到 \(n\)，定义满足下面的任意一个条件，\(A\) 会在当前位置 \(i\) 吃一个饼干：
还没吃过饼干；
当前位置有卖家；
在 \([\max(1, i - d + 1), i - 1]\) 区间内没吃饼干
现在，输出移走一个卖家后，吃饼干的数量最小值，以及对应的移除方案数。
思路
这是一个思路很清楚但特判比较多的模拟题，但题面表述我只能说 \(\mathtt{no}\) \(\mathtt{comment}\)。
首先，条件 \(1\) 就等价于，\(A\) 在点 \(1\) 一定会吃饼干。
其次，剩下的两个条件可以合并为，在有卖家的位置都会吃饼干，并且对于所有相邻的卖家的距离 \(D\)，会 多出 \(\frac{D - 1}{d}\) 个吃饼干的点。
如果要让吃饼干的数量减少，我们就得枚举三个卖家，将中间的卖家去掉后，得到的叠加距离不会使 多出的吃饼干的点 增加。
我们还得对点 \(n\) 进行单独处理，因为可能在走到 \(n\) 前，又出现了长度大于 \(d\) 的情况。
如上，我们先预处理出不移走卖家的饼干数，然后三个三个枚举即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, m, d;
cin >> n >> m >> d;
vector<int> s(m + 1);
for(int i=1;i<=m;i++) cin >> s[i];
int sum = 0;
vector<int> cnt(m + 2);
for(int i=1;i<=m;i++){
if(i == 1){
if(s[1] == 1){
sum ++;
cnt[1] = 1;
}else{
sum += (s[1] - 1 - 1) / d + 2;
cnt[1] += (s[1] - 1 - 1) / d + 2;
}
}else{
sum += (s[i] - s[i - 1] - 1) / d + 1;
cnt[i] += (s[i] - s[i - 1] - 1) / d + 1;
}
if(i == m){
sum += (n - s[i]) / d;
cnt[m + 1] += (n - s[i]) / d;
}
}
int ans = inf, tot = 0;
for(int i=1;i<=m;i++){
int now;
if(i == 1){
now = sum - (cnt[i] + cnt[i + 1]) + (s[i + 1] - 1 - 1) / d + 1 + 1;
}else if(i == m){
now = sum - (cnt[i] + cnt[i + 1]) + (n - s[i - 1]) / d;
}else{
now = sum - (cnt[i] + cnt[i + 1]) + (s[i + 1] - s[i - 1] - 1) / d + 1;
}
if(ans > now){
ans = now;
tot = 1;
}else if(ans == now){
tot ++;
}
}
cout << ans << ' ' << tot << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}不予置评
C. Yet Another Permutation Problem
题意
给定排列的长度 \(n\)，构造排列，满足将其首尾相连后，相邻数的 \(gcd\) 的不同数量最大。
思路
很显然，我们先在开头置 \(1\)，然后枚举 \(x \in [2, \inf]\)。
对于 \(x\)，我们循环乘 \(2\)，并将其放入排列中，如果遇到之前放进去的数，我们直接跳出循环。
上述贪心的正确性是很显然的，因为更小的数拥有更多的在范围内的倍数，并且 \(2\) 是我们最小可以乘上的数。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<int> ans;
vector<bool> vis(n + 10);
int cur = 2;
ans.pb(1);
while (ans.size() < n) {
int t = cur;
vis[cur] = true;
while (t <= n) {
ans.pb(t);
vis[t] = true;
t *= 2;
}
while (vis[cur]) {
cur++;
}
}
for (auto e : ans) cout << e << ' ';
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}《Div. 2 C》
D. Trees and Segments
题意
给定一个长为 \(n\) 的二进制字符串，定义操作为选定一个字符，并将其反转。
在不超过 \(k\) 次操作的条件下，得到最大连续 \(0\) 的长度 \(l_0\)，最大连续 \(1\) 的长度 \(l_1\)。
在所有可能的操作中，对 \(a \in [1, n]\)，输出 \(a \times l_0 + l_1\) 的最大值。
思路
我们定义 \(len[i]\) 为 操作后 最大的连续 \(1\) 的长度为 \(i\)，且该条件下最大的连续 \(0\) 的长度为 \(len[i]\)。
其中，我们可以用 \(O(n ^ 2)\) 的复杂度，遍历所有的连续区间，并得到将每个区间所有数都改为 \(1\) 需要的操作数 \(x\)，通过操作数 \(x\) 来计算答案。
我们以一个区间为例，如果该区间内，我们操作了 \(x\) 次来让所有数都变成 \(1\)，那么我们就剩下 \(k - x\) 次操作提供给拓展连续 \(0\) 的操作。并且 我们一定会将这 \(k-x\) 次操作都用完，因为这样可以最大化答案。
显然，因为最长的连续 \(0\) 一定在该区间的左边或者右边，那么我们考虑维护一个前缀 \(pre[i][j]\) 和后缀 \(suf[i][j]\)，分别代表 前 \(i\) 个数 操作了 \(j\) 次后 最长的 连续 \(0\) 区间 的长度，以及 后 \(i\) 个数中 操作了 \(j\) 次后 最长的 连续 \(0\) 区间 的长度。
那么，对于区间 \([i + 1, j - 1]\)，操作了 \(x\) 次，\(len[j - i] = \max(len[j - i], \max(pre[i][k - x], suf[j][k - x]))\)。
接下来，我们考虑如何递推。
我们遍历 \(i \in [1, n], j \in [i + 1, n + 1]\)，满足区间 \([i + 1, j - 1]\) 内所有元素都是 \(0\)，那么 我们可以在遍历的时候 处理出 当前区间需要操作几次 以达到 全变成 \(1\) 的目标。
我们记操作数为 \(x\)，那么前 \(j\) 个数中，操作 \(x\) 次后 最大连续 \(0\) 的长度至少为 \(j - i\)，后 \(i\) 个数同理。
也就是说，\(pre[j][x] = \max(pre[j][x], j - i), suf[i][x] = \max(suf[i][x], j - i)\)。
处理完成后，我们得到的 \(pre[i][j]\) 为以 \(i\) 结尾的，操作 \(j\) 次得到的 最大连续 \(0\) 的长度，后缀同理。
我们以前缀为例，继续递推，以得到我们需要的前缀：
如果我们不操作，那么我们从 前 \(i-1\) 个字符 且 操作 \(j\) 次 递推状态；
如果我们操作，那么我们从 前 \(i\) 个字符 且 操作 \(j - 1\) 次 递推状态
根据我们最开始的处理，我们只需在递推的时候取最大值即可。
时间复杂度：\(O(nk + n ^ 2)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
s = " " + s;
vector<vector<int>> pre(n + 2, vector<int>(k + 1)),
suf(n + 2, vector<int>(k + 1));
for(int i=1;i<=n;i++){
int x = 0;
for(int j=i+1;j<=n+1;j++){
if(s[j - 1] == '1') x ++;
if(x > k) break;
pre[j][x] = max(pre[j][x], j - i);
suf[i][x] = max(suf[i][x], j - i);
}
}
for(int i=1;i<=n+1;i++){
for(int j=0;j<=k;j++){
if(i > 1) pre[i][j] = max(pre[i][j], pre[i - 1][j]);
if(j > 0) pre[i][j] = max(pre[i][j], pre[i][j - 1]);
}
}
for(int i=n+1;i>=1;i--){
for(int j=0;j<=k;j++){
if(i <= n) suf[i][j] = max(suf[i][j], suf[i + 1][j]);
if(j > 0) suf[i][j] = max(suf[i][j], suf[i][j - 1]);
}
}
vector<int> len(n + 1, -inf);
for(int i=1;i<=n;i++){
int x = 0;
for(int j=i;j<=n+1;j++){
if(j > i && s[j - 1] == '0') x ++;
if(x > k) break;
len[j - i] = max(len[j - i], pre[i][k - x]);
len[j - i] = max(len[j - i], suf[j][k - x]);
}
}
for(int a=1;a<=n;a++){
int ans = 0;
for(int i=0;i<=n;i++) {
if(len[i] == -inf) continue;
ans = max(ans, i + len[i] * a);
}
cout << ans << ' ';
}
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}感觉官方题解的式子有点抽象