目录

A. Matching（签到）

思路：

代码： 

B. Sort the Subarray（签到）

思路：

代码：

C. Tear It Apart（枚举）

思路：

代码：

D. Black Cells（模拟）

思路：

 代码一：

代码二：（模仿自"AG"佬）

A. Matching（签到）

An integer template is a string consisting of digits and/or question marks.

A positive (strictly greater than 0) integer matches the integer template if it is possible to replace every question mark in the template with a digit in such a way that we get the decimal representation of that integer without any leading zeroes.

For example:

• 42 matches 4?;
• 1337 matches ????;
• 1337matches 1?3?;
• 1337 matches 1337;
• 3 does not match ??;
• 8 does not match ???8;
• 1337 does not match 1?7.

You are given an integer template consisting of at most 5 characters. Calculate the number of positive (strictly greater than 0) integers that match it.

Input

The first line contains one integer t (1≤t≤2⋅104) — the number of test cases.

Each test case consists of one line containing the string s (1≤|s|≤5) consisting of digits and/or question marks — the integer template for the corresponding test case.

Output

For each test case, print one integer — the number of positive (strictly greater than 00) integers that match the template.

Example

input

8

??

?

0

9

03

1??7

?5?

9??99

output

90
9
0
1
0
100
90
100

思路：

签到，如果第一位是0，0种填法，？在第一位9种填法，在其它位10种填法

代码： 

#include<bits/stdc++.h>
#define endl '\\n'
using namespace std;
typedef long long ll;void solve(){string s;cin>>s;if(s[0]=='0'){cout<<0<<endl;return;}int cnt=0;for(int i=0;i<s.length();i++){cnt+=(s[i]=='?');}ll ans=1;for(int i=1;i<=cnt;i++)ans*=10;if(s[0]=='?'){ans=ans/10*9;}cout<<ans<<endl;return;
}int main(){int T=1;cin>>T;while(T--){solve();}return 0;
}

B. Sort the Subarray（签到）

Monocarp had an array a consisting of n integers. He has decided to choose two integers l and r such that 1≤l≤r≤n1≤, and then sort the subarray a[l..r] (the subarray a[l..r] is the part of the array a containing the elements al,al+1,al+2,…,ar−1,ar in non-descending order. After sorting the subarray, Monocarp has obtained a new array, which we denote as a′.

For example, if a=[6,7,3,4,4,6,5], and Monocarp has chosen l=2,r=5, then a′=[6,3,4,4,7,6,5]

You are given the arrays a and a′. Find the integers l and r that Monocarp could have chosen. If there are multiple pairs of values (l,r), find the one which corresponds to the longest subarray.

Input

The first line contains one integer t (1≤t≤104) — the number of test cases.

Each test case consists of three lines:

• the first line contains one integer n(2≤n≤2⋅105);
• the second line contains ntegers a1,a2,…,an (1≤ai≤n1);
• the third line contains n integers a′1,a′2,…,a′n (1≤a′i≤n).

Additional constraints on the input:

• the sum of n over all test cases does not exceed 2⋅105;
• it is possible to obtain the array by sorting one subarray of a;
• a′≠a (there exists at least one position in which these two arrays are different).

Output

For each test case, print two integers — the values of l and r (1≤l≤r≤n). If there are multiple answers, print the values that correspond to the longest subarray. If there are still multiple answers, print any of them.

Example

input

3

7

6 7 3 4 4 6 5

6 3 4 4 7 6 5

3

1 2 1

1 1 2

3

2 2 1

2 1 2

output

2 5
1 3
2 3

思路：

给两个数组，第二个数组是由第一个数组进行部分排序后得到的，求排序的最长区间的左右界

分别从前后遍历数组，找见第一个不同的位置，中间一定进行了排序，两边的元素如果加入后依然有序，可以加入到排序区间中

代码：

#include<bits/stdc++.h>
#define endl '\\n'
using namespace std;
typedef long long ll;void solve(){int n;cin>>n;vector<int>a1(n+1),a2(n+1);for(int i=1;i<=n;i++)cin>>a1[i];for(int i=1;i<=n;i++)cin>>a2[i];int pos1,pos2;for(int i=1;i<=n;i++){      //左边一个个不同的位置if(a1[i]!=a2[i]){pos1=i;break;}}for(int i=n;i>=1;i--){      //右边一个个不同的位置if(a1[i]!=a2[i]){pos2=i;break;}}for(int i=pos1-1;i>=1;i--){     //若左边元素加入后仍有序，则加入排序区间if(a2[i]<=a2[i+1])pos1=i;else break;}for(int i=pos2+1;i<=n;i++){     //右边同理if(a2[i]>=a2[i-1])pos2=i;else break;}cout<<pos1<<' '<<pos2<<endl;return;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;cin>>T;while(T--){solve();}return 0;
}

C. Tear It Apart（枚举）

You are given a string s, consisting of lowercase Latin letters.

In one operation, you can select several (one or more) positions in it such that no two selected positions are adjacent to each other. Then you remove the letters on the selected positions from the string. The resulting parts are concatenated without changing their order.

What is the smallest number of operations required to make all the letters in s the same?

Input

The first line contains a single integer t (1≤t≤104) — the number of testcases.

The only line of each testcase contains a string s, consisting of lowercase Latin letters. Its length is from 11 to 2⋅105.

The total length of the strings over all testcases doesn't exceed 2⋅105.

Output

For each testcase, print a single integer — the smallest number of operations required to make all the letters in the given string s the same.

Example

input

5

abacaba

codeforces

oooooooo

abcdef

mewheniseearulhiiarul

output

1
3
0
2
4

Note

In the first testcase, you can select positions 2,42,4 and 66 and remove the corresponding letters 'b', 'c' and 'b'.

In the third testcase, the letters in the string are already the same, so you don't have to make any operations.

In the fourth testcase, one of the possible solutions in 22 operations is the following. You can select positions 1,4,61,4,6 first. The string becomes "bce". Then select positions 11 and 33. The string becomes "c". All letters in it are the same, since it's just one letter.

思路：

给一个字符串，每次可以挑任意个不相邻的字母删除，求变成仅有一种字符所需要的最少操作次数

枚举字符串中所有字符，字符把字符串分为若干段，找出最长的一段字符串最短的字符，全部化为这个字符所需要的操作次数最少

找规律发现字段为n的操作次数为logn-1

代码：

#include<bits/stdc++.h>
#define endl '\\n'
using namespace std;
typedef long long ll;
int Log[200005];
void init(){        //预处理log函数Log[0]=-1;for(int i=1;i<=200005;i++){if(i&(i-1))Log[i]=Log[i-1];else Log[i]=Log[i-1]+1;}
}void solve(){string s;cin>>s;int n=s.length();vector<int>pos[30];     //储存当前字符在字符串中的所有位置vector<int>dis(30,-1);      //表示当前字符划分出的最长一段的长度s=" "+s;for(int i=1;i<=n;i++){int x=s[i]-'a';pos[x].push_back(i);if(pos[x].size()==1)dis[x]=i-1;         //找出每个字符划分的最长的长度else dis[x]=max(dis[x],i-pos[x][pos[x].size()-2]-1);}int ans=INT_MAX;for(int i=0;i<28;i++)if(dis[i]!=-1){dis[i]=max(dis[i],n-pos[i][pos[i].size()-1]);ans=min(ans,dis[i]);    //找出最短的最长间距}cout<<Log[ans]+1<<endl;     //求操作次数return;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);init();int T=1;cin>>T;while(T--){solve();}return 0;
}

D. Black Cells（模拟）

You are playing with a really long strip consisting of 1018 white cells, numbered from left to right as 0, 1, 2 and so on. You are controlling a special pointer that is initially in cell 00. Also, you have a "Shift" button you can press and hold.

In one move, you can do one of three actions:

• move the pointer to the right (from cell x to cell x+1);
• press and hold the "Shift" button;
• release the "Shift" button: the moment you release "Shift", all cells that were visited while "Shift" was pressed are colored in black.

(Of course, you can't press Shift if you already hold it. Similarly, you can't release Shift if you haven't pressed it.)

Your goal is to color at least k cells, but there is a restriction: you are given n segments [li,ri] — you can color cells only inside these segments, i. e. you can color the cell x if and only if li≤x≤ri for some i.

What is the minimum number of moves you need to make in order to color at least k cells black?

Input

The first line contains a single integer t (1≤t≤104) — the number of test cases.

The first line of each test case contains two integers n and k (1≤n≤2⋅105; 1≤k≤109) — the number of segments and the desired number of black cells, respectively.

The second line contains n integers l1,l2,…,ln (1≤l1<l2<⋯<ln≤109), where li is the left border of the i-th segment.

The third line contains n integers r1,r2,…,rn (1≤ri≤109 li≤ri<li+1−1), where ri is the right border of the i-th segment.

Additional constraints on the input:

• every cell belongs to at most one segment;
• the sum of n doesn't exceed 2⋅1052⋅105.

Output

For each test case, print the minimum number of moves to color at least k cells black, or −1 if it's impossible.

Example

input

4

2 3

1 3

1 4

4 20

10 13 16 19

11 14 17 20

2 3

1 3

1 10

2 4

99 999999999

100 1000000000

output

8
-1
7
1000000004

Note

In the first test case, one of the optimal sequences of operations is the following:

1. Move right: pointer is moving into cell 1;
2. Press Shift;
3. Release Shift: cell 1 is colored black;
4. Move right: pointer is moving into cell 2;
5. Move right: pointer is moving into cell 3;
6. Press Shift;
7. Move right: pointer is moving into cell 4;
8. Release Shift: cells 3 and 4 are colored in black.

We've colored 3 cells in 8 moves.

In the second test case, we can color at most 8 cells, while we need 20 cell to color.

In the third test case, one of the optimal sequences of operations is the following:

1. Move right: pointer is moving into cell 1;
2. Move right: pointer is moving into cell 2;
3. Move right: pointer is moving into cell 3;
4. Press Shift;
5. Move right: pointer is moving into cell 4;
6. Move right: pointer is moving into cell 5;
7. Release Shift: cells 3, 4 and 5 are colored in black.

We've colored 3 cells in 7 moves.

思路：

有三个操作，按下和松开shift键，和往前走一步，按下shift键时的块会被涂色，给n个区间，只能在给定区间上涂色，求涂k个块需要的最少操作数

我们发现，区间长度为1时，需要进行两次操作来涂一个块，是最麻烦的，这样的区间涂得越少越好；如果涂好了k个块，当前区间还能往后走的话，就往后走一步，删去之前的一个1的区间不涂，这样更优。

如果已经没有长度为1的区间，若已经涂好了k个块，再往后走一定没有当前状态优，直接返回。

 代码一：

#include<bits/stdc++.h>
#define endl '\\n'
using namespace std;
typedef long long ll;
struct node{ll l,r;ll cnt;     //区间内块数
}seg[200005];
void solve(){int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>seg[i].l;}vector<ll>pre(n+1,0);   //区间块数前缀和ll ans=INT_MAX;ll nn=0;       //长度为1的区间个数for(int i=1;i<=n;i++){cin>>seg[i].r;seg[i].cnt=seg[i].r-seg[i].l+1;pre[i]=pre[i-1]+seg[i].cnt;}if(pre[n]<k){       //能涂色的个数不足k个cout<<-1<<endl;return;}ll dstep=0;     //不走的1的个数for(int i=1;i<=n;i++){nn+=(seg[i].cnt==1);pre[i]=pre[i-1]+seg[i].cnt;     //由于修改，前缀和重算if(pre[i]>=k){ll tmp=pre[i]-k;    //空出来的位置ll step=i-dstep;       //shift的次数为总共区间数-不走的1的个数//nn是剩余1的个数if(tmp>=nn){    //有多余的长度，用来补齐没走的1tmp-=nn;step-=nn;   seg[i].r-=tmp;      //所有1都被补起来，后面的区间就不走了ans=min(ans,step*2+seg[i].r);   break;}//tmp<nndstep+=tmp;        //空缺位置全补上1ans=min(ans,(step-tmp)*2+seg[i].r);nn-=tmp;    pre[i]=k;}}cout<<ans<<endl;return;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;cin>>T;while(T--){solve();}return 0;
}

代码二：（模仿自"AG"佬）

枚举每一个可能结束的终点，然后尽可能减去之前的长度为1的区间，更新答案即可（不愧是佬）

#include<bits/stdc++.h>
#define endl '\\n'
using namespace std;
typedef long long ll;
void solve(){int ans=INT_MAX;int n,k;cin>>n>>k;vector<pair<int,int> >a(n);for(auto&[x,y]:a)cin>>x;for(auto&[x,y]:a)cin>>y;int num=0;int nn=0;for(int i=0;i<n;i++){auto [l,r]=a[i];num+=(r-l+1);if(num>=k){int remov=min(nn,num-k);    //能填多少1填多少1int res=num-remov;      //涂色的总块数int pos=max(l,r-(res-k));       //右边减去不必要涂的块数ans=min(ans,pos+2*(i+1-remov));}nn+=(l==r);     //只填前面的1，所有涂完色，再填一}if(ans==INT_MAX)ans=-1;cout<<ans<<endl;return;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;cin>>T;while(T--){solve();}return 0;
}