Problem A Rubbish

https://ac.nowcoder.com/acm/contest/912/A

题意:1e5*1e5的棋盘上有n点,求连通块数量

C++版本一

题解:坐标离散化+坐标数轴化+二分+递推+并查集

1、对所有坐标离散化成数轴;

2、由左上到右下递推;

3、并查集合并;

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const ll INF = 0x3f3f3f3f3f3f3f;
int s,t,n,m,k,p,l,r;
ll u,v,a[N];
int x[N],y[N],b[N];
ll ans,cnt,flag,temp,sum;
int pre[N];
int find(int x){
    if(x==pre[x])return x;
    return pre[x]=find(pre[x]);
}
void marge(int x,int y){
    int tx=find(x);
    int ty=find(y);
    if(tx!=ty){
        pre[tx]=ty;
    }
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //int T=0;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)pre[i]=i;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&x[i],&y[i]);
            a[i]=(x[i]-1)*100000ll+y[i];
        }
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++){
            u=x[i];
            v=y[i];
            ll now=(u-1)*100000ll+v;
            int ii=lower_bound(a+1,a+n+1,now)-a;
            if(u<100000ll&&v<100000ll){
                int jj=lower_bound(a+1,a+n+1,u*100000ll+v+1)-a;
                if(jj<=n&&a[jj]==u*100000ll+v+1)marge(ii,jj);
            }
            if(v<100000ll){
                int ij=lower_bound(a+1,a+n+1,(u-1)*100000ll+v+1)-a;
                if(ij<=n&&a[ij]==(u-1)*100000ll+v+1)marge(ii,ij);
            }
            if(u<100000ll){
                int ji=lower_bound(a+1,a+n+1,u*100000ll+v)-a;
                if(ji<=n&&a[ji]==u*100000ll+v)marge(ii,ji);
            }
            if(u<100000ll&&v>1){
                int jii=lower_bound(a+1,a+n+1,u*100000ll+v-1)-a;
                if(jii<=n&&a[jii]==u*100000ll+v-1)marge(ii,jii);
            }
            if(u>1&&v<100000ll){
                int jji=lower_bound(a+1,a+n+1,(u-2)*100000ll+v+1)-a;
                if(jji<=n&&a[jji]==(u-2)*100000ll+v+1)marge(ii,jji);
            }
        }
        ans=0;
        for(int i=1;i<=n;i++)ans+=(pre[i]==i);
        cout<<ans<<endl;
        //printf("%lld\n",ans);
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}
/*
4
1 2
2 1
2 3
3 2
*/

C++版本二

题解:坐标离散化+并查集

将格点按行先列次排序,遍历过程更新当前列的格点中行数最大格点的下标,判断能否与当前点连通,用并查集维护连通块。 

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PB push_back
#define endl '\n'
const int N=1e6+7;
const int INF=1e8,mod=1e7+7;
int n,m,k;
struct s{
    int x,y;
    int fa;
}a[N];
int f[N];
int F(int x){
    return x==a[x].fa?x:a[x].fa=F(a[x].fa);
}
void u(int x,int y){
    x=F(x),y=F(y);
    if(x==y)return;
    a[x].fa=y;
}
bool cmp(s p,s q){
    if(p.x==q.x)return p.y<q.y;
    return p.x<q.x;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    memset(f,-1,sizeof(f));
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)a[i].fa=i;
    a[0].y=a[0].x=-1;
    for(int i=1;i<=n;i++){
        //如果与前一个格点同行且下标差一说明连通
        if(a[i].y==a[i-1].y+1&&a[i].x==a[i-1].x){
            u(a[i].fa,a[i-1].fa);
        }
        //左上是否有格点
        if(a[f[a[i].y-1]].x==a[i].x-1){
            u(a[i].fa,a[f[a[i].y-1]].fa);
        }
        //上方是否有
        if(a[f[a[i].y]].x==a[i].x-1){
            u(a[i].fa,a[f[a[i].y]].fa);
        }
        //右上是否有
        if(a[f[a[i].y+1]].x==a[i].x-1){
            u(a[i].fa,a[f[a[i].y+1]].fa);
        }
        f[a[i].y]=i;
    }
    memset(f,0,sizeof(f));
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!f[F(a[i].fa)]){
            ans++;
            f[F(a[i].fa)]=1;
        }
        //cout<<i<<' '<<a[i].x<<' '<<a[i].y<<' '<<a[i].fa<<' '<<ans<<endl;
    }
    cout<<ans;
	return 0;
}

Problem B Bowling Game

https://ac.nowcoder.com/acm/contest/912/B

题意:蓝色面积S1,黄色面积S2,问球的直径多大的时候会按照图中所示卡住。

C++版本一

题解:几何数学

设d为直径,r为半径,S2的边分别为a,b,c,其中c*c=S1;

证明:

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%lld%lld",&n,&m);
    printf("%f\n",4*n/(sqrt(m)+sqrt(m+4*n)));
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解:二分

对于一个斜边确定的等腰三角形,两直角边差越小面积越大,用s1求出斜边,然后二分法求两直角边的长度,内切圆直径就是直角边长和减斜边长。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PB push_back
#define endl '\n'
int main()
{
    double s1,s2;
    cin>>s1>>s2;
    double x=sqrt(s2);
    double l=0,r=sqrt(2.0)/2*x;
    while(r-l>=0.0000001){
        double mid=(l+r)/2;
        if(mid*sqrt(x*x-mid*mid)/2>s1){
            r=mid;
        }
        else l=mid;
    }
    double ans=(l+sqrt(x*x-l*l)-x);
    printf("%.6lf",ans);
	return 0;
}

 

Problem C REN

https://ac.nowcoder.com/acm/contest/912/C

题意:

题解:

C++版本一

 

Problem D Capture The Flag

https://ac.nowcoder.com/acm/contest/912/D

题意:

题解:

C++版本一

 

Problem E Shortest Code

https://ac.nowcoder.com/acm/contest/912/E

题意:去掉没必要的空格、空行和注释。

题解:模拟

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
string a;
string res;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //scanf("%d",&n);
    while(getline(cin,a)){
        int l=a.size();
        res="";
        for(int i=0;i<l;i++)
            if(a[i]==' ')if(i!=0&&i!=l-1&&isalnum(a[i-1])&&isalnum(a[i+1]))res+=' ';else a[i]=a[i-1];//将空格更新为前一个值
            else if(i<l-1&&a[i]=='/'&&a[i+1]=='/')break;
            else res+=a[i];
        if(res.size())cout<<res<<endl;
    }
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem F Successione di Fixoracci

https://ac.nowcoder.com/acm/contest/912/F

题意:

已知a和b的值。现在你只要求出Tn是多少

题解:规律

C++版本一

题解:

1、任意一个数被同一个数异或两次等于本身。即a^b^b=a;

2、此数列为 a,b,a^b循环

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%lld%lld%lld",&n,&m,&k);
    if(k%3==0)ans=n;
    if(k%3==1)ans=m;
    if(k%3==2)ans=n^m;
    cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem G Segment Tree

https://ac.nowcoder.com/acm/contest/912/G

题意:

题解:

C++版本一

 

Problem H Arithmetic Sequence

https://ac.nowcoder.com/acm/contest/912/H

题意:输出一个等差数列,使得数列和等于X

题解:没有要求数列长度,因此直接输出x

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    cout<<1<<endl;
    cout<<n<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem I Fate Grand Order

https://ac.nowcoder.com/acm/contest/912/I

题意:最多n/3个活动,使得期望最大

题解:贪心

每张卡片带来开心值的期望为抽中概率乘开心值,按期望排序贪心即可

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,l,r,u,v;
int ans,cnt,flag,temp,sum;
string str="";
struct node{
    double p,x;
    double q;
    int id;
    bool operator <(const node&S)const{
        return q>S.q;
    }
}e[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%lf",&e[i].p),e[i].id=i,str+='0';
    for(int i=1;i<=m;i++)scanf("%lf",&e[i].x),e[i].q=e[i].x*e[i].p;
    n/=3;
    sort(e+1,e+m+1);
    for(int i=1;i<=min(n,m);i++)str[e[i].id-1]='1';
    cout<<str<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem J Printout

https://ac.nowcoder.com/acm/contest/912/J

题意:

题解:模拟

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
double ans,cnt,flag,temp,sum;
int a[N];
double b[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)scanf("%lf",&b[i]);
    a[0]=1;
    for(int i=1;i<=m;i++){
        if(n<=a[i]){
            ans=n*b[i];
            for(int j=i+1;j<=m;j++){
                ans=min(ans,a[j-1]*b[j]);
            }
            break;
        }
    }
    cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem K Master of Graph

https://ac.nowcoder.com/acm/contest/912/K

题意:区间修改+区间查询

题解:线段树+标记

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v,q;
int ans,cnt,flag,temp,sum;
char str;
struct node{};
ll tree[N<<2];
bool tag[N<<2];
ll f(ll x){//计算f(x)
    ll re=0;
    while(x){
        re+=x%10;
        x/=10;
    }
    return re;
}
void pushup(int rt){
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
    tag[rt]=tag[rt<<1]&&tag[rt<<1|1];
}
void build(int l,int r,int rt){
    if(l==r){
        scanf("%lld",&tree[rt]);
        tag[rt]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);

}
void updata(int l,int r,int rt,int L,int R){
    if(tag[rt])
        return;
    if(l==r){
        tree[rt]=f(tree[rt]);
        if(tree[rt]<10)tag[rt]=1;
        return;
    }

    int mid=(l+r)>>1;
    if(L<=mid)updata(l,mid,rt<<1,L,R);
    if(R>mid)updata(mid+1,r,rt<<1|1,L,R);
    pushup(rt);
}
ll query(int l,int r,int rt,int L,int R){
    if(L<=l&&r<=R){
        return tree[rt];
    }
    int mid=(l+r)>>1;
    if(R<=mid)return query(l,mid,rt<<1,L,R);
    else if(L>mid)return query(mid+1,r,rt<<1|1,L,R);
    else return query(l,mid,rt<<1,L,R)+query(mid+1,r,rt<<1|1,L,R);
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&m);
    memset(tree,0,sizeof(tree));
    build(1,n,1);
    while(m--)scanf("%d%d",&u,&v);
    scanf("%d",&q);
    while(q--){
        scanf("%d%d%d",&t,&l,&r);
        if(t){
            updata(1,n,1,l,r);
        }else{
            cout<<query(1,n,1,l,r)<<endl;
        }
    }
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem L Homework Stream

https://ac.nowcoder.com/acm/contest/912/L

题意:编号为k的作业依赖于哪些作业,以及哪些作业依赖于编号为k的作业。

题解:模拟

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
vector<int>a,b;
void print(vector<int>p){
    for(int i=0;i<p.size();i++){
        printf("%d%c",p[i]," \n"[i==p.size()-1]);
    }
    if(p.size()==0)cout<<endl;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        if(u==k)a.push_back(v);
        if(v==k)b.push_back(u);
    }
    print(a);
    print(b);
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem M Orx Zone

https://ac.nowcoder.com/acm/contest/912/M

题意:

题解:对于1-n为左边界的情况恭喜就是(n+1-当前最近的’x’和’r’的下标的较大值)

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,x[N],r[N],u,v;
ll ans,cnt,flag,temp,sum;
char a[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //scanf("%d",&n);
    scanf("%s",a+1);
    int len=strlen(a+1);
    x[len+1]=r[len+1]=len+1;
    for(int i=len;i>=1;i--){
        x[i]=(a[i]=='x'?i:x[i+1]);//在该点后最近的x
        r[i]=(a[i]=='r'?i:r[i+1]);//在该点后最近的r
    }
    for(int i=1;i<=len;i++)ans+=len-max(x[i],r[i])+1;
    cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}