Educational Codeforces Round 147 div2题解

这篇具有很好参考价值的文章主要介绍了Educational Codeforces Round 147 div2题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

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){    //有多余的长度,用来补齐没走的1
                tmp-=nn;
                step-=nn;   
                seg[i].r-=tmp;      //所有1都被补起来,后面的区间就不走了
                ans=min(ans,step*2+seg[i].r);   
                break;
            }

            //tmp<nn
            dstep+=tmp;        //空缺位置全补上1
            ans=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的区间,更新答案即可(不愧是佬)文章来源地址https://www.toymoban.com/news/detail-420386.html

#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填多少1
            int 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;
}

到了这里,关于Educational Codeforces Round 147 div2题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Educational Codeforces Round 151 (Rated for Div. 2)

    A. Forbidden Integer 题意 : 你有[1, k]内除了 x x x 的整数,每个数可以拿多次,问 ∑ = n sum = n ∑ = n 是否可行并构造 思路 : 有1必能构造,否则假如没有1,假如有2, 3必定能构造出大于等于2的所有数,否则只有2的话只能构造出偶数。 B. Come Together 题意 : 棋盘上两个点同时从

    2024年02月12日
    浏览(42)
  • Educational Codeforces Round 161 (Rated for Div. 2)

    Educational Codeforces Round 161 (Rated for Div. 2) 题意:开始没看懂。。。给出长度均为n的三个字符串abc,字符串s与模板t匹配的条件为:当模板位置字符为小写时, s i s_i s i ​ 与 t i t_i t i ​ 必须相同,大写时二者必须不同。这里注意,字符匹配过程是不区分大小写的,’C‘与’

    2024年01月19日
    浏览(37)
  • Educational Codeforces Round 62 (Rated for Div. 2) C. Playlist

     一开始肯定要排个序,b相同时t大的在前边,不同时b大的在前面。 然后想最多只能选k个的限制,可以这样想,每次用到的b只能用已选到的最小的值,那可以把每个b都枚举一遍,然后每一次选时长最长的,且b大于等于当前的b的那k个不就好了吗,时间复杂度也才O(n),然

    2024年02月12日
    浏览(39)
  • Educational Codeforces Round 154 (Rated for Div. 2)(A—C)

    从1到9,每个数后面都可以加一个数构成一个含有两个数的质数,只需要从s[1]~s[9]中找到一个数与s[0]构成质数即可 观察样例即可发现两个字符串只要在相同位置都有 01 存在就能成功实现转换后两个字符串相等 可以先假设字符串是可以成立的,那么接下来就判断它什么时间是

    2024年02月10日
    浏览(38)
  • Educational Codeforces Round 154 (Rated for Div. 2)(A—D)

    从1到9,每个数后面都可以加一个数构成一个含有两个数的质数,只需要从s[1]~s[9]中找到一个数与s[0]构成质数即可 观察样例即可发现两个字符串只要在相同位置都有 01 存在就能成功实现转换后两个字符串相等 可以先假设字符串是可以成立的,那么接下来就判断它什么时间是

    2024年02月10日
    浏览(34)
  • Educational Codeforces Round 135 (Rated for Div. 2)C. Digital Logarithm(思维)

    C. Digital Logarithm 给两个长度位 n n n 的数组 a a a 、 b b b ,一个操作 f f f 定义操作 f f f 为, a [ i ] = f ( a [ i ] ) = a [ i ] a[i]=f(a[i])=a[i] a [ i ] = f ( a [ i ]) = a [ i ] 的位数 求最少多少次操作可以使 a 、 b a、b a 、 b 两个数组变得完全相同 性质: 对于任何数,经过两次操作我们一定可以

    2024年02月20日
    浏览(37)
  • 【每日一题】—— B. Ternary String (Educational Codeforces Round 87 (Rated for Div. 2))

    🌏博客主页: PH_modest的博客主页 🚩当前专栏: 每日一题 💌其他专栏: 🔴 每日反刍 🟡 C++跬步积累 🟢 C语言跬步积累 🌈座右铭: 广积粮,缓称王! 题目大意:给你一串由1、2、3组成的数组,让你求一个最短的子串,要求这个子串包含1、2、3 题目链接:B. Ternary String

    2024年02月16日
    浏览(35)
  • Educational Codeforces Round 157 (Rated for Div. 2) F. Fancy Arrays(容斥+组合数学)

    题目 称一个长为n的数列a是fancy的,当且仅当: 1. 数组内至少有一个元素在[x,x+k-1]之间 2. 相邻项的差的绝对值不超过k,即 t(t=50)组样例,每次给定n(1=n=1e9),x(1=x=40), 求fancy的数组的数量,答案对1e9+7取模 思路来源 灵茶山艾府群 官方题解 题解 看到 至少 的字眼,首先想到容斥,

    2024年02月05日
    浏览(38)
  • Codeforces Round 830 (Div. 2)题解

    1A 这个设计到一个常识,如果知道能在三分钟之内解题: 相邻的两个数字的gcd肯定是1::这个没有问题,比如gcd(1,2),比如gcd(3,4) 但是我想要任何两个数字的的最大公约数为1,我们直接让这两个数字等于除以相邻的两个数字的结果就行, 结果必然是两个树的因子,两个相邻的

    2024年02月15日
    浏览(38)
  • Codeforces Round 875 (Div. 1) 题解

    You are given two arrays a and b both of length n. Your task is to count the number of pairs of integers ( i , j ) (i,j) ( i , j ) such that 1 ≤ i j ≤ n 1≤ij≤n 1 ≤ i j ≤ n and a i ⋅ a j = b i + b j a_i⋅a_j=b_i+b_j a i ​ ⋅ a j ​ = b i ​ + b j ​ 。 1 ≤ a i , b i ≤ n 1≤a_i,b_i≤n 1 ≤ a i ​ , b i ​ ≤ n 考虑 m i n ( a i

    2024年02月08日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包