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:
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:
You finish performing operations when the string ss becomes empty. What is the maximum number of operations you can perform?
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.
For each test case, print a single integer — the maximum number of operations you can perform.
5 6 111010 1 0 1 1 2 11 6 101010
3 1 1 1 3
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; }
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.
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.
Print one integer — the minimum number of swaps of neighboring elements you have to perform to reverse the string.
5 aaaza
2
6 cbaabc
0
9 icpcsguru
30
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; }
Educational Codeforces Round 96 (Rated for Div. 2) de
原文：https://www.cnblogs.com/love-chili/p/13849000.html
