A
简单计数题，判断前导零。
#include <bits/stdc++.h>
using namespace std;
int T;
int main(){
cin >> T;
while(T --){
char s[10];
cin >> s;
int n = strlen(s);
int ans = 1;
for(int i = 0; i < n; i++){
if(s[i] == '?' && i == 0) ans = 9;
else if(s[i] == '?') ans *= 10;
}
if(s[0] == '0') ans = 0;
cout << ans << endl;
}
return 0;
}
B
这题还比较有意思，这里从逻辑上进行讲解。
首先，对于 \(l\sim r\) 是答案的充分条件： \(a[l] \ne b[l]\) \(and\) \(a[1\sim l-1] = b[1 \sim l-1]\)，对于 \(r\) 同理。
再考虑 \(l\sim r\) 是答案的必要条件： \(a[l\sim r]\) 单调递增。
于是我们先通过充分找出差值最小的 \(l,r\) 的取值，再通过必要条件找出其差值最大的取值，即为答案。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int T, n;
int a[N], b[N];
int main(){
cin >> T;
while(T --){
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 1; i <= n; i++)
scanf("%d", &b[i]);
int l = 1, r = n;
while(l < r){
if(a[l] == b[l]) l ++;
else if(a[r] == b[r] && r > l) r --;
else break;
}
while(l > 1 && b[l - 1] <= b[l])
l --;
while(r < n && b[r + 1] >= b[r])
r ++;
printf("%d %d\n", l, r);
}
return 0;
}
C
对于一段长为 \(n\) 的序列，我们想消除需要用 \(log_2 n\) 次，于是对于每个字母进行考虑，暴力即可完成。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int T, n, a[N];
int cnt[30];
int main(){
cin >> T;
while(T --){
memset(cnt, 0, sizeof cnt);
char ch[N]; cin >> ch;
n = strlen(ch);
for(int i = 1; i <= n; i++){
a[i] = ch[i - 1] - 'a', cnt[a[i]] ++;
}
int ans = N;
for(int aim = 0; aim < 26; aim++){
if(!cnt[aim]) continue;
int maxn = 0, lst = 0;
for(int i = 1; i <= n; i++)
if(a[i] == aim)
maxn = max(maxn, i - lst - 1), lst = i;
maxn = max(maxn, n - lst);
int res = 0;
while(maxn){
res ++;
maxn >>= 1;
}
ans = min(ans, res);
}
cout << ans << endl;
}
return 0;
}
D
通过手玩样例不难发现，对于长度为 \(1\) 的区间，我们可以不取它用以减少答案 \(2\) 次，那么可以多往前走一步。
同理，长度大于 \(1\) 的区间必须要取，因为不能优化答案。我们通过顺序遍历判断是否可以通过减少长度为 \(1\) 的区间优化答案即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int T, n, k;
int l[N], r[N];
int main(){
int T;
cin >> T;
while(T--){
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++)
scanf("%d", &l[i]);
for(int i = 1; i <= n; i++)
scanf("%d", &r[i]);
int sum = 0;
for(int i = 1; i <= n; i++)
sum += r[i] - l[i] + 1;
if(sum < k){
puts("-1");
continue;
}
int ans = 0x3f3f3f3f, cnt = 0, less = 0;
for(int i = 1; i <= n; i++){
if(r[i] == l[i]) less ++;
cnt += r[i] - l[i] + 1;
if(cnt >= k){
int more = cnt - k;
int res = r[i] - more + 2 * i - min(more, less);
ans = min(ans, res);
}
}
printf("%d\n", ans);
}
return 0;
}