https://codeforces.com/contest/1907
A题是一个很简单的模拟，就不说了
B题
赛后看有群u们说拿栈模拟
比赛时我想到的是从后到前遍历字符串，维护两个cnt1，cnt2.分别代表B，b出现的次数，出现一次对应cnt++，遍历每一个字符如果对应cnt不为零，这一位就不加入答案，然后cnt–。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve(){
string s;
cin>>s;
reverse(s.begin(),s.end());
int cnt1=0;
int cnt2=0;
int len=s.size();
string ans="";
for(int i=0;i<len;i++){
if(s[i]=='b'){cnt1++;continue;}
if(s[i]=='B'){cnt2++;continue;}
if(s[i]<='z'&&s[i]>='a'&&cnt1){
cnt1--;
continue;
}
if(s[i]<='Z'&&s[i]>='A'&&cnt2){
cnt2--;
continue;
}
ans+=s[i];
}
reverse(ans.begin(),ans.end());
cout<<ans<<'\n';
}
int main(){
int _;cin>>_;
while(_--)solve();
return 0;
}
|
C题
感觉是见过最简单的C了（？
考虑删完所有相邻且不同的字符之后，剩下的一定是一个只含一个字母的子串
所以找到出现次数最多的字母出现次数记为sum
与其不相等的其他字母数量一定为n-sum。
比较sum和n-sum，sum大就输出n-2`*sum，否则输出n%2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll cnt[26];
void solve(){
memset(cnt,0,sizeof cnt);
ll n;cin>>n;
string s;
cin>>s;
for(int i=0;i<s.size();i++){
cnt[s[i]-'a']++;
}
ll mx=*max_element(cnt,cnt+26);
n-=mx;
if((n+mx)&1){
cout<<((mx-n)<=0?1:(mx-n))<<'\n';
return;
}
cout<<((mx-n)<=0?0:(mx-n))<<'\n';
}
int main(){
int _;cin>>_;
while(_--)solve();
return 0;
}
|
D题
二分即可，重点在于怎么写check函数
我们可以把每个点扩展到的位置看做一个圆和x轴的左右交点，下一次从这一条线段上任意一点做圆，所以最左端和最右端一定是非递减的
需要注意两点：
1.在扩展的时候要维护两个端点，而不是只维护上一次的一个点
2.二分的时候0是可取答案，如果按我的写法二分应当从-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+10;
ll l[N];
ll r[N];
ll ans=0;
ll n;
bool check(ll x){
ll zz=0;
ll yy=0;
for(int i=1;i<=n;i++){
if(l[i]>(yy+x)||r[i]<(zz-x))return false;
else{
zz=max(zz-x,l[i]);
yy=min(yy+x,r[i]);
}
}
return 1;
}
void solve(){
cin>>n;
memset(l,0,sizeof l);
memset(r,0,sizeof r);
for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
ll z=-1;
ll y=1e10;
while((z+1)!=y){
ll mid=(z+y)>>1;
if(check(mid)){
y=mid;
}
else{
z=mid;
}
}
cout<<y<<'\n';
}
int main(){
int _;cin>>_;
while(_--)solve();
return 0;
}
|
E题
三者不进位，转换为隔板法组合数学，和高中求n个小球分为三份有多少种分法是一样的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve(){
string s;
cin>>s;
ll ans=1;
for(auto &c:s){
ans*=(c-'0'+2)*(c-'0'+1)/2;
}
cout<<ans<<'\n';
}
int main(){
int _;cin>>_;
while(_--)solve();
}
|
F题
易知颠倒的操作一定发生在头尾
模拟即可
问我为什么做的这么丑，因为我当时很急急急急急急急急急急急急急急急急急急急
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=4e5+10;
int a[N];
ll n,ans=1e9+7;
void solve(){
int cnt=1;
for(int i=2*n-1;i>=1;i--){
if(a[i]<=a[i+1])cnt++;
else cnt=1;
if(cnt==n){ans=min(ans,n-i+1);break;}
}
cnt=1;
for(int i=2*n-1;i>=1;i--){
if(a[i]>=a[i+1])cnt++;
else cnt=1;
if(cnt==n){ans=min(ans,n-i+2);break;}
}
return ;
}
void solve2(){
int cnt=1;
for(int i=2*n-1;i>=1;i--){
if(a[i]<=a[i+1])cnt++;
else cnt=1;
if(cnt==n){ans=min(ans,n-i+2);break;}
}
cnt=1;
for(int i=2*n-1;i>=1;i--){
if(a[i]>=a[i+1])cnt++;
else cnt=1;
if(cnt==n){ans=min(ans,n-i+3);break;}
}
return ;
}
int main(){
int _;cin>>_;
while(_--){
ans=1e9+7;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
}
solve();
if(n==1){
cout<<"0"<<'\n';
continue;
}
reverse(a+1,a+n+1);
for(int i=1;i<=n;i++){
a[i+n]=a[i];
}
solve2();
cout<<(ans==1e9+7?-1:ans)<<'\n';;
}
}
|
