文章首页 Web开发 Windows开发 编程语言 数据库技术 移动平台 系统服务 微信 设计 布布扣 其他

Educational Codeforces Round 96 (Rated for Div. 2) de

时间：2020-10-20 21:22:25   收藏：0   阅读：34
D. String Deletion
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a string ss consisting of nn characters. Each character is either 0 or 1.

You can perform operations on the string. Each operation consists of two steps:

  1. select an integer ii from 11 to the length of the string ss, then delete the character sisi (the string length gets reduced by 11, the indices of characters to the right of the deleted one also get reduced by 11);
  2. if the string ss is not empty, delete the maximum length prefix consisting of the same characters (the indices of the remaining characters and the string length get reduced by the length of the deleted prefix).

Note that both steps are mandatory in each operation, and their order cannot be changed.

For example, if you have a string s=s= 111010, the first operation can be one of the following:

  1. select i=1i=1: we‘ll get 111010 →→ 11010 →→ 010;
  2. select i=2i=2: we‘ll get 111010 →→ 11010 →→ 010;
  3. select i=3i=3: we‘ll get 111010 →→ 11010 →→ 010;
  4. select i=4i=4: we‘ll get 111010 →→ 11110 →→ 0;
  5. select i=5i=5: we‘ll get 111010 →→ 11100 →→ 00;
  6. select i=6i=6: we‘ll get 111010 →→ 11101 →→ 01.

You finish performing operations when the string ss becomes empty. What is the maximum number of operations you can perform?

Input

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

The first line of each test case contains a single integer nn (1≤n≤2?1051≤n≤2?105) — the length of the string ss.

The second line contains string ss of nn characters. Each character is either 0 or 1.

It‘s guaranteed that the total sum of nn over test cases doesn‘t exceed 2?1052?105.

Output

For each test case, print a single integer — the maximum number of operations you can perform.

Example
input
Copy
5
6
111010
1
0
1
1
2
11
6
101010
output
Copy
3
1
1
1
3
Note

In the first test case, you can, for example, select i=2i=2 and get string 010 after the first operation. After that, you can select i=3i=3 and get string 1. Finally, you can only select i=1i=1 and get empty string.

题意（魔改=.=）：

给出一个0和1组成的字符串，玩家1先走，玩家2后走，玩家1要删除任意一个字符，玩家2删除头部的一个字符或多个字符（011------11,00011--------11）。问玩家1最多删除多少字符。

思路：暴力模拟，指针运用，思维。有连续先删除连续字符段，没有连续字符段 就从前往后删。

代码：

技术分享图片 
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        string s;
        cin>>s;
        int v[200005]= {0};
        s[n]=‘#‘;
        int k=0,l=1,y=-1;
        for(int i=0; i<n; i++)
        {
            if(s[i]==s[i+1])
            {
                l++;
            }
            else
            {
                if(l>1)
                    y=k;
                v[k]=l;
                k++;
                l=1;
 
            }
        }
       /* for(int i=0; i<k; i++)
            cout<<v[i];
        cout<<endl;
        cout<<"y "<<y<<endl;*/
        long long ans=0;
        int ii=0,jj=1,p=1;
        if(y==-1)
            p=0;
        for(int i=0; i<k; i++)
        {
            /*cout<<i<<" "<<jj<<" "<<ans<<" "<<p<<endl;
            for(int kk=0; kk<k; kk++)
                cout<<v[kk];
            cout<<endl;*/
            if(i>=jj)
                jj=i;
            ans++;
            if(v[i]>1)
            {
                ans++;
            }
            else
            {
                if(p==1)
                {
                    for(int j=jj; j<k; j++)
                    {
                        if(v[j]>1)
                        {
                            ans++;
                            v[j]--;
                            jj=j;
                            break;
                        }
                        if(j==k-1&&v[j]<=1)
                        {
                            if(i+1<k)
                            {
                                ans++;
                                i++;
                            }
                            p=0;
                        }
                    }
                }
                else
                {
                    if(i+1<k)
                    {
                        ans++;
                        i++;
                     //   cout<<"!"<<endl;
                    }
 
                }
 
            }
        }
 
        cout<<(ans+1)/2<<endl;
 
 
    }
 
 
    return 0;
}
View Code
E. String Reversal
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string ss. You have to reverse it — that is, the first letter should become equal to the last letter before the reversal, the second letter should become equal to the second-to-last letter before the reversal — and so on. For example, if your goal is to reverse the string "abddea", you should get the string "aeddba". To accomplish your goal, you can swap the neighboring elements of the string.

Your task is to calculate the minimum number of swaps you have to perform to reverse the given string.

Input

The first line contains one integer nn (2≤n≤2000002≤n≤200000) — the length of ss.

The second line contains ss — a string consisting of nn lowercase Latin letters.

Output

Print one integer — the minimum number of swaps of neighboring elements you have to perform to reverse the string.

Examples
input
Copy
5
aaaza
output
Copy
2
input
Copy
6
cbaabc
output
Copy
0
input
Copy
9
icpcsguru
output
Copy
30
Note

In the first example, you have to swap the third and the fourth elements, so the string becomes "aazaa". Then you have to swap the second and the third elements, so the string becomes "azaaa". So, it is possible to reverse the string in two swaps.

Since the string in the second example is a palindrome, you don‘t have to do anything to reverse it.

题意：一个字符串颠倒过来，最少需要冒泡排序多少次。

思路：树状数组 

（考虑每个位置的贡献，从最后一个字符开始计算。

显然对于相同的字符选取靠前的位置的贡献更小。

所以用队列维护相同字母的位置。

从后往前遍历，然后用树状数组维护到当前位置有多少位置没排好，每排好一个位置就更新树状数组，每个位置的贡献就是query(pos)?1。

此时更新树状数组的正确性是因为：在pos之前的位置整体向右移动一位，然后又因为pos移到他们的前面，抵消了，而p o s pospos后的位置，因为前面少一个位置，所以对应的树状数组减1.）

学习借鉴：https://blog.csdn.net/weixin_45750972/article/details/109024382

代码：

技术分享图片 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define itn int
#define lowbit(x) x&(-x)
const int N=2e5+5;
int n,c[N];
queue<int >q[30];
char s[N];
ll ans=0;
void updata(int i,int v)
{
    while(i<=n)
    {
        c[i]+=v;
        i+=lowbit(i);
    }
}
int getsum(int i)
{
    int s=0;
    while(i)
    {
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}
int main()
{
    scanf("%d%s",&n,s+1);
    for(int i=1; i<=n; i++)
    {
        q[s[i]-‘a‘].push(i);
        updata(i,1);
    }
    for(int i=n; i; i--)
    {
        int p=q[s[i]-‘a‘].front();
        q[s[i]-‘a‘].pop();
        ans+=getsum(p)-1;
        updata(p,-1);
    }
    cout<<ans<<endl;


    return 0;
}
View Code

 

 

 

 

 

原文：https://www.cnblogs.com/love-chili/p/13849000.html

评论（0）
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣，分享程序人生！