一、A - Matching

• 思路:
  有几个问号就是10的几次方,除了第一个字符是问号,如果第一个字符是问号,就是* 9,因为没有前导零

• 代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define fi first
#define se secondusing namespace std;
typedef pair<int, int> PII;
const int N = 25010,M = 150010;
void solve()
{string s; cin >> s;int n = s.size();int sum = 1;if(s[0] == '?') sum = 9;if(s[0] == '0'){cout << "0" << endl;return ;}for(int i = 1;i < s.size();i ++ ){if(s[i] == '?')sum = sum * 10;}cout << sum << endl;}
int main()
{int T; T = 1;cin >> T;   while( T -- ) solve();return 0;
}

二、B - Sort the Subarray

• 思路:

  1: 首先,我们先要确定一下需要修改的最小范围(A[i] != B[i]),遍历一下,知道修改的最小范围是[L,R]

  2: 然后用双指针遍历B中的所有连续非递减的区间,如果[L,R]在某一个遍历的区间内,那就是答案,
  3: 不能不确定修改范围就直接遍历B,因为直接遍历B的话,答案可能是错的,比如
  A = 5 5 5 3 7
  B = 5 5 3 5 7
  修改的长度最大是二,答案应该是[3,4],但是直接遍历的答案是[1,2]

• 代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define fi first
#define se secondusing namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 5,M = 150010;
int a[N],b[N];
void solve()
{int n; cin >> n;int L= 1e9,R = -1;for(int i = 1;i <= n;i ++ ) cin >> a[i];for(int i = 1;i <= n;i ++ ) cin >> b[i];for(int i = 1;i <= n;i ++ ){if(a[i] != b[i]){L = min(i,L);R = max(i,R);}}int l = 1,r = n;int mx = 0;for(int i = 1;i <= n;i ++ ){int j = i + 1;while(j <= n && b[j] >= b[j - 1]){++j;}if(i <= L && j - 1 >= R){l = i;r = j - 1;break;}i = j - 1;}if(L == 1e9){cout << 1 << ' ' << n << endl;} elsecout << l << ' ' << r << endl;}
int main()
{int T; T = 1;cin >> T;   while( T -- ) solve();return 0;
}

三、C - Tear It Apart

• 思路:
  1: 因为是S是小写字母,所以直接枚举你想要最后留下来的是哪一个字母

  2: 假如你想要留下来的是a,那对于 abbcbabb,需要几次呢?,我们可以发现,不是a的连续字符长度有两个一个是4,一个是2,实际上我们求的答案只关乎长度最大的那一个, 所以只要长度最长的被移除,其他长度都可以被移除

  3: 移除一个长度为k的连续字符,需要的操作次数是log(k)(以二为底),算法就是用到了双指针

• 代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define fi first
#define se secondusing namespace std;
const int N = 2e5 + 5,M = 150010;
bool st[28];
int check(int x)
{int d = 0;while(x != 0){d++;x /= 2;}return d;
}
void solve()
{string s; cin >> s;int n = s.size();for(int i = 0;i < n;i ++ )st[int(s[i] - 'a')] = true;int ans = check(n) - 1;for(int i = 0;i <= 25;i ++ ){if(st[i]){int mx = 0;char op = i + 'a';for(int j = 0;j < n;j ++ ){int k = j;int d = 0;while(k < n && s[k] != op){++k;++d; // 有多少个 }int len = check(d);mx = max(mx,len);j = k;}ans = min(ans,mx);}}cout << ans << endl;for(int i = 0;i <= 26;i ++ )st[i] = false;}
int main()
{int T; T = 1;cin >> T;   while( T -- ) solve();return 0;
}

四、D - Black Cells

• 思路:
  1: 长度太长不好分析,我们就分析两段,假设变成k个黑颜色的格子的最后一步是在区间[L2,R2]上面,那如果跳过第一个区间(第一个区间任何一个格子都不变成黑色)需要的步数是 P1 = L2 + 2 + k - 1 (加2是覆盖一个区间的步数)

  2: 如果不跳过第一个区间(把第一个区间的格子都变成黑色),因为我们假设了最后一步一定在第二个区间所以需要的步数是 P2 = L2 + k1 + 2 + 2 - 1(加两个2是因为覆盖两个区间), k1 = k - (R1 - L1 + 1),

  3: 那我们假设不跳过第一个区间更优的话,也就是 P2 <= P1,化简得R1 - L1 >= 1,也就是说对于最后一步到达的区间 W 来说,只要区间长度大于1就操作,也就是说只有区间长度为 1 的才会影响最后的答案

  4: 那我们就枚举k最后一步在哪一个区间,详解看代码吧,对了记得开long long

• 代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define fi first
#define se second
#define int long long
using namespace std;
const int N = 2e5 + 5,M = 150010;int l[N],r[N];void solve()
{int n,k; cin >> n >> k;for(int i = 1;i <= n;i ++ ) cin >> l[i];for(int i = 1;i <= n;i ++ ) cin >> r[i];int sum = 0; int num1 = 0;int ans = 1e18;for(int i = 1;i <= n;i ++ ) // 只要k在最后区间前面不操作区间长度为1的情况下,满足sum + (r[i] - l[i] + 1) >= k,后面就不用再运行了,直接break;{if(sum + (r[i] - l[i] + 1) >= k) // 就是这个区间了 {int p = (i - num1) * 2 + l[i] + (k - sum) - 1;ans = min(p,ans);break;}int pp = k - (sum + (r[i] - l[i] + 1)); // 在这个区间需要几个num1 ,因为这个区间不满足上面的条件,就需要区间长度为1来使用if(pp <= num1) // 可以使得变成k个黑色,操作一下{int ss = (i - num1 + pp) * 2 + r[i];ans = min(ss,ans);}if(l[i] == r[i]) ++num1;else sum += r[i] - l[i] + 1; } if(ans == 1e18) ans = -1;cout << ans << endl; }
signed main()
{int T; T = 1;cin >> T;   while( T -- ) solve();return 0;
}