CF ER147 div.2

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;
}