Contestant. Rank 2617. Rating -37.
A. Matching
题意
给定一个匹配字符串，包含 \(?\) 和 \([0, 9]\) 内的数字，\(?\) 可用任意数字替换。
输出字符串可以代表的数字的总数，其中数字不可以出现前导 \(0\)。
思路
很显然，难点在最后一句话，但这只和第一个字符是不是 \(?\) 有关。
如果不是 \(?\)，那么显然不会出现前导 \(0\)，最后的答案就是 \(10 ^ x\)，其中 \(x\) 是 \(?\) 的个数。
如果是 \(?\)，那么该位不可以出现 \(0\)，而其余位置是否为 \(0\) 我们无需考虑，所以最后的答案是 \(\frac{9}{10} 10 ^ x\)。
不过当然，如果第一位是 \(0\)，那么一个符合条件的数都没有了。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define psi pair<string, int>
#define fs first
#define sc second
const int N = 1e5 + 10;
void solve(){
string s;
cin >> s;
int ans = 1;
int n = s.size();
for(int i=0;i<n;i++){
if(s[i] == '?') ans *= 10;
}
if(s[0] == '?') ans = ans / 10 * 9;
if(s[0] == '0') ans = 0;
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}很快啊，很简单啊（x
B. Sort the Subarray
题意
定义操作为选择一段连续的子区间并将其中的所有元素升序排序。
现在给定操作前后的序列，输出最长的可能操作区间的左右端点。
思路
首先，我们比对两个序列，先找出不相同的起始位置和结束位置，得到区间 \([l_0, r_0]\)。
然后，我们拓展这个区间，其中，左区间向左拓展的条件是 \(a_{l_0 - 1} \leq a_{l_0}\)，右区间同理。
最后得到的区间就是答案。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define psi pair<string, int>
#define fs first
#define sc second
const int N = 1e5 + 10;
void solve(){
int n;
cin >> n;
vector<int> p(n), q(n);
for(int i=0;i<n;i++) cin >> p[i];
int b = -1, e = -1;
for(int i=0;i<n;i++) {
cin >> q[i];
if(p[i] != q[i]){
if(b == -1) b = e = i;
else e = i;
}
}
if(b == -1){
int mx = 1, pre = p[0], cnt = 1, e = 1;
for(int i=1;i<n;i++){
if(p[i] >= pre) cnt ++;
else{
if(mx < cnt){
mx = cnt;
e = i;
}
cnt = 1;
}
pre = p[i];
}
if(mx < cnt){
mx = cnt;
e = n;
}
cout << e - mx + 1 << ' ' << e << '\n';
}else{
while(b - 1 >= 0 && q[b] >= q[b - 1]) b --;
while(e + 1 < n && q[e] <= q[e + 1]) e ++;
cout << b + 1 << ' ' << e + 1 << '\n';
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}怎么老打错变量，罚时吃饱力（悲
C. Tear It Apart
题意
给定一个字符串，定义操作为选择任意数量的不相邻的位置并将对应位置的字符删除。
输出最小操作数，使最后的字符串所有字符相同。
思路
首先，我们可以枚举我们要保留的那个字符，并删去其他的字符。
那么，我们只需考虑如何删的问题了。
显然，我们可以将需要删除的字符分成若干段，在第一次删除时，我们只需对每一段从第一个开始隔一位删就可以让能删的字符数最多，这显然成立（如 \(\color{rgb(124,179,66)}{b}\)\(c\)\(\color{rgb(124,179,66)}{d}\)\(a\)\(\color{rgb(124,179,66)}{b}\)\(c\)\(\color{rgb(124,179,66)}{d}\)\(b\)）。
那么，我们可以重复上面的操作，直到删完为止。
我们可以发现，操作数只和数量最多的那一段有关，而且最后的结果有 \(\log_2\) 的关系。
观察发现，\(\lceil \log_2 cnt_{max} \rceil\) 即为答案。
当然，直接用while循环也不是不可以（
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define psi pair<string, int>
#define fs first
#define sc second
const int N = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
string s;
cin >> s;
int n = s.size();
bool f = true;
for(int i=1;i<n;i++) if(s[i] != s[i - 1]) f = false;
if(f) {
cout << 0 << '\n';
return;
}
int ans = inf;
s = " " + s + " ";
for(int w=0;w<=25;w++){
char now = (char) (w + 'a');
s[0] = s[n + 1] = now;
int mx = 1, cnt = 0;
for(int i=0;i<=n + 1;i++){
if(s[i] == now){
mx = max(mx, cnt);
cnt = 0;
}else cnt ++;
}
int cur = 0;
while(mx > 0){
cur ++;
mx /= 2;
}
ans = min(ans, cur);
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}观察可得，显然易得（x
D. Black Cells
题意
给定一个数轴，对于起点 \(0\)，有下面的三个代价均为 \(1\) 的操作：
向右移动一格
按下shift
松开shift，此时按下到松开这段时间内经过的格子都会被染成黑色。
现在，给定数轴上的 \(n\) 段区间，只能将区间内的格子染上黑色，且需要染 \(k\) 个格子。
输出最小代价和。
思路
首先，不跳过区间的做法绝对不是最优的。
那么，我们会希望跳过区间的代价小于不跳过区间的代价。
但是，显然无论跳不跳过，我们都必须经过这个区间，所以问题归结到按下和松开shift的代价。
假设我们跳过了 \([l_i, r_i]\) 区间，此时代价为 \(a\)；如果我们不跳过，那么我们会多出 \(2\) 次按shift的代价，但是最后就不会多出至少 \(len\) 个需要多染的格子了。
那么最后问题归结于 \(a'=a+2-len\) 和 \(a\) 的大小关系了。
显然，当长度为 \(1\) 时，我们能跳就跳；而长度为 \(2\) 时代价一致，长度大于 \(2\) 时我们能不跳就不跳。
我们可以枚举所有区间，然后进行分类讨论。
我们边枚举边记录算上当前区间的话之前有 \(c\) 个长为 \(1\) 的区间，去掉长为 \(1\) 区间后其他区间的和为 \(s\)。
那么，如果 \(s + c < k\)，在这里停下来是不够的。如果 \(s < k\) 但 \(s + c \geq k\)，那么一部分 \(1\) 是需要保留的，我们可以得到当前的最小代价为 \(end + 2((i - c) + (k - s))\)。如果 \(s \geq k\)，那么我们将所有的 \(1\) 都跳过即可，此时最小代价为 \(end - (s - k) + 2(i - c)\)。
当然，我们也可以使用优先队列解这题。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n, k;
cin >> n >> k;
vector<int> l(n), r(n);
for(int i=0;i<n;i++) cin >> l[i];
for(int i=0;i<n;i++) cin >> r[i];
int s = 0, c = 0, ans = inf;
for(int i=0;i<n;i++){
if(r[i] - l[i] + 1 == 1) c ++;
else s += r[i] - l[i] + 1;
if(s + c < k) continue;
if(s < k && s + c >= k) ans = min(ans, r[i] + 2 * (i + 1 - c + k - s));
else ans = min(ans, r[i] - (s - k) + 2 * (i + 1 - c));
}
cout << (ans == inf ? -1 : ans) << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}有点贪心的感觉