A Rubbish

链接：https://ac.nowcoder.com/acm/contest/912/A
来源：牛客网

题目描述
垃圾小x经常在机房丢垃圾，比如奶茶杯子、用过的湿巾纸、吃完的零食包装等。

可是训练的桌子上放了电脑，实在放不下小x丢的垃圾了。因此，大家搬了一张专门丢垃圾的桌子放在小x边上。为了防止小x丢垃圾的时候溢出，这张桌子很大，可以用一个105×105的网格来表示，桌子的左上角视为格点(1,1)，右下角视为格点(105,105)。

有了这么大的桌子，小x就可以肆意地丢垃圾：小x丢的垃圾既不会堆叠，也不会相邻（若两块垃圾在上下左右及斜对角方向有接触，则为相邻）

看着这么大的桌子被用来丢垃圾，你不禁发出了疑问：已知哪些格点被垃圾覆盖，那么小x一共丢了多少垃圾？

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

#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;
}

B Bowling Game
链接：https://ac.nowcoder.com/acm/contest/912/B
来源：牛客网

题目描述
CUST的队员打完省赛后，小r带着大家去打保龄球。

保龄球是一项难度非常高的游戏，然而这根本难不住校队成员，他们个个都很厉害(炸和)一发10个瓶都倒。尤其是小r，每次都能闭着眼睛一次扔倒10个瓶。他们当中也有一个并不那么厉害的下水道玩家，每次都能把球丢进下水道里，导致一个球瓶都砸不中。

几轮下来，我们发现回来的球越来越少，最后只剩几个9号球了。他们不爱丢9号球，因为太轻了。

在询问工作小姐姐后，得知：咱们松江保龄球俱乐部技术并不那么先进，所以后台是人工操作把球捡回来，现在球没有回来，导致球变少的原因是球卡住了，投进下水道就可能会导致现在这种情况。

校队成员心里都有数，他们每人都至少炸和过一次，只有某下水道玩家。。。

我们得知后台都是方形的盒子，大概这样的时候保龄球会卡住，图中蓝色面积S1，黄色面积S2，问球的直径多大的时候会按照图中所示卡住。

思路：对于一个斜边确定的等腰三角形，两直角边差越小面积越大，用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;
}

E Shortest Code
链接：https://ac.nowcoder.com/acm/contest/912/E
来源：牛客网

题目描述
手速场是小r的最爱。小r的手速飞快，当你们看到这道题的时候，小r已经AK了，不信你们可以去看看榜。如果看完榜发现小r还没AK，你们可以去把他(!*&!KaTeX parse error: Expected 'EOF', got '&' at position 1: &̲(!*%&!^$。

为了速度，小r写代码的时候不喜欢缩进。所有的编辑器和IDE看到小r，吓得都不敢缩进了。同时，小r也不喜欢加不需要的空格空行，包括运算符两端、if/for语句后面的空格、函数之间的空行等。至于注释，对小r来说更没必要了。总之，小r的代码永远都是最短的。

不过，小r的队友并没有小r这么快。他的代码夹杂着大量的空格和注释，这使得小r在比赛时经常心态崩了。于是小r觉得他需要一个插件，来帮他把队友的代码变短，去掉这些没必要的空格、空行和注释。

思路：大模拟，唯一的坑点在字母或数字中间同时出现两个空格，因此如果出现了一个需要去掉的空格我们直接将其更新为前一个值方便接下来的判断

#include<bits/stdc++.h>
using namespace std;
#define PB push_back
string a;
vector<char>v;
int check(char x){
    if(x<='z'&&x>='a')return 1;
    if(x<='Z'&&x>='A')return 1;
    if(x<='9'&&x>='0')return 1;
    return 0;
}
int main()
{
    while(getline(cin,a)){
        int l=a.size();
        int flag=0;
        int cnt=0;
        int st=0;
        for(int i=0;i<l;i++){
            if(a[i]==' '){
                if(i!=0&&i!=l-1&&check(a[i-1])&&check(a[i+1])){
                    v.PB(' ');
                    flag=1;
                }
                else a[i]=a[i-1];//将空格更新为前一个值
            }
            else if(i<l-1&&a[i]=='/'&&a[i+1]=='/'){
                break;
            }
            else{v.PB(a[i]);flag=1;}
        }
        if(flag)v.PB('\n');
    }
    for(int i=0;i<v.size();i++)printf("%c",v[i]);
	return 0;
}

F Successione di Fixoracci
链接：https://ac.nowcoder.com/acm/contest/912/F
来源：牛客网

题目描述
动态规划(Dynamic programming，简称dp)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。例如，假设小x一步能爬1层或2层台阶，求小x爬n层台阶共有几种方法，就可以用dp计算：设
F
i
Fi代表小x爬i层台阶共有几种方法，则
F
i

F
i
−
1
+
F
i
−
2
Fi=Fi−1+Fi−2。

小x是练习时长两年半的acm练习生，喜欢口胡、dp、线段树。妙就妙在，不管是什么题目，无论多难，小x都能用他喜欢的三样东西AC。

你可能不相信，但其实他口胡了一个定理：所有题目，都可以转化成在x数列上的操作。只要先dp出题目对应的x数列，再用线段树随便维护一下，就可以过了。以下给出x数列的定义：
T0=a,T1=b。

Tn=Tn−1⊕Tn−2(n≥2)

其中⊕为异或运算。

现在小x已经用dp求出了a和b的值。现在你只要求出Tn是多少，就可以通过这道题目。
规律题，a,b,a^b 循环出现

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL n,a,b;
int main()
{
    cin>>a>>b>>n;
    if(n%3==2){
        cout<<(a^b);
    }
    else if(n%3==0)cout<<a;
    else cout<<b;
	return 0;
}

H Arithmetic Sequence

题意：给你x，让你构造一个等差数列，使其和为x
究极签到题，因为没有要求数列长度，因此直接输出x就ok

#include<bits/stdc++.h>
using namespace std;
#define LL long long
int x;
int main()
{
    cin>>x;
    cout<<1<<endl;
    cout<<x<<endl;
	return 0;
}

I Fate Grand Order
链接：https://ac.nowcoder.com/acm/contest/912/I
来源：牛客网

题目描述
Fate Grand Order是型月社发行的角色扮演类手机游戏，是著名的氪金抽卡"垃圾"手游。

小t是该手游的忠实厨力玩家，为了抽到喜欢的角色他特地氪金买了n颗圣晶石(3颗圣晶石可以抽卡1次)。

已知有m个抽卡活动会按时间顺序在游戏中举办，每个活动都会新推出一个角色，并且告诉你这m个角色的抽取概率，而每当首次成功抽到每个角色之后他会获得一定的开心值。

小t是一个有计划的男人，在第1个活动开始前他就会想好一个抽卡计划，抽卡计划决定哪些角色抽，哪些角色不抽；

小t也是一个贫穷的男人，对于每个选择抽卡的活动，他都只会抽一次，不管是否抽到都不会选择继续再在这个活动抽卡；

小t也是一个纠结的男人，每个角色他都很纠结是否要抽，总之他想让自己尽可能开心，所以小t求助于聪明的你，他想知道什么样的计划可以让开心值的期望最大。

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

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PB push_back
#define endl '\n'
const int N=2e5+7;
const int INF=1e8,mod=1e9+7;
int n,m,k;
struct node{
    double p,x;
    double q;
    int xh;
}a[N];
bool cmp(node x,node y){
    return x.q>y.q;
}
int f[N];
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        scanf("%lf",&a[i].p);
        a[i].xh=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%lf",&a[i].x);
        a[i].q=a[i].x*a[i].p;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=m/3;i++){
        f[a[i].xh]=1;
    }
    for(int i=1;i<=n;i++){
        printf("%d",f[i]);
    }
    return 0;
}

J Printout
链接：https://ac.nowcoder.com/acm/contest/912/J
来源：牛客网

题目描述
小r为了打校赛，他打算去打字社打印一份包含世界上所有算法的模板。

到了打字社，小r一看价格：总打印页数X0页以下(不含X0)x0元每页，X0∼X1页(不含X1)x1元每页，X1∼X2页(不含X2)x2元每页，X2∼X3页(不含X3)x3元每页，X3∼X4页(不含X4)x4元每页……

小r转念一想，他可以多放一些白纸在模板里面，还能花更少的钱。

给出小r要打印的模板页数n以及价格列表X和x，小r想知道他打印的最少花费为多少钱？

注意：小r只能打印一次，不能将一篇文章分多次打印。

遍历判断页数是否可打印或需要补空白页，更新答案

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PB push_back
#define endl '\n'
const int N=2e5+7;
const int INF=1e8,mod=1e9+7;
int n,m,k;
int X[N];
double x[N];
int main()
{
    cin>>n>>m;
    double ans=5201314;
    for(int i=1;i<=m;i++){
        cin>>X[i];
    }
    x[n+1]=INF;
    for(int i=1;i<=m;i++){
        cin>>x[i];
        if(n<X[i]){
            if(n>=X[i-1]){
                ans=min(ans,x[i]*n);
            }
            else{
                ans=min(ans,x[i]*X[i-1]);
            }
        }
    }
    cout<<ans;
    return 0;
}

K Master of Graph
链接：https://ac.nowcoder.com/acm/contest/912/K
来源：牛客网

题目描述
“好像有点感觉哦”–小x(Master of Graph)

每当图论大师小x看到图,他都会说一句"好像有点感觉哦",他以为自己有掌控图的能力,能把某些特定编号的点的权值修改成自己想要的值,所以每次修改后他都会自信回头(不管了),

但是他的队友(咋胡佬)发现小x并没有把那些特定编号的点的权值修改成他想要的值,由于小x给力的操作(给力哦铁汁),假设点原来的权值为x,修改后会变成f(x)(f(x)是统计十进制数字x每一位的和),

咋胡佬发现了这一规律后,自信满满地来到小x面前询问他某些特定编号的点的权值和,

您作为小x的死忠粉iXiang也发现了这一规律,自然不希望自己的idol(偶像)受到质疑,因此您决定帮助小x一一回答咋胡佬的问题

事实证明输入的边毫无卵用，然后我们思考一下就会发现一个数更新几次以后就会小于十也就是无需再更新，因此开线段树暴力修改加区间标记即可

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PB push_back
#define endl '\n'
const int N=1e5+7;
const int INF=1e8,mod=1e9+7;
int n,m,q;
struct dat{
    int l,r;
    LL k;
    int flag;//该区间是否已无需修改
}a[N<<2];
LL s[N];
LL cot(LL x){//计算f(x)
    LL re=0;
    while(x){
        re+=x%10;
        x/=10;
    }
    return re;
}
#define ls x<<1
#define rs x<<1|1
void build(int l,int r,int x){
    a[x].l=l,a[x].r=r;
    if(l==r){
        a[x].k=s[l];
        if(a[x].k<10){
            a[x].flag=1;
        }
        else a[x].flag=0;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    a[x].k=a[ls].k+a[rs].k;
    if(a[ls].flag==1&&a[rs].flag==1){
            a[x].flag=1;
    }
    else a[x].flag=0;
}
#define MX a[x].l+a[x].r>>1
void update(int l,int r,int x){
    if(a[x].flag)return;
    if(a[x].l==a[x].r){
        a[x].k=cot(a[x].k);
        if(a[x].k<10)a[x].flag=1;
        return;
    }
    int mid=MX;
    if(r<=mid)update(l,r,ls);
    else if(l>mid)update(l,r,rs);
    else {
        update(l,mid,ls);
        update(mid+1,r,rs);
    }
    a[x].k=a[ls].k+a[rs].k;
    if(a[ls].flag==1&&a[rs].flag==1){
            a[x].flag=1;
    }
    else a[x].flag=0;
}
LL query(int l,int r,int x){
    if(a[x].l>=l&&a[x].r==r)return a[x].k;
    int mid=MX;
    if(r<=mid){
        return query(l,r,ls);
    }
    else if(l>mid)return query(l,r,rs);
    else return query(l,mid,ls)+query(mid+1,r,rs);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%lld",&s[i]);
    }
    build(1,n,1);
    int l,r;
    for(int i=1;i<=m;i++)scanf("%d%d",&l,&r);
    cin>>q;
    int op;
    while(q--){
        scanf("%d%d%d",&op,&l,&r);
        if(op==1)update(l,r,1);
        else printf("%lld\n",query(l,r,1));
    }
	return 0;
}

L Homework Stream
链接：https://ac.nowcoder.com/acm/contest/912/L
来源：牛客网

题目描述
作为大珩班尖子生，小r每天有很多作业要完成，例如工图、工图和工图。

很显然，做作业是要有顺序的。作业之间存在依赖关系，某一个作业没做完，就不能开始做另一个作业。例如，汇编作业依赖于C语言作业，因为小r可以用C语言的编译结果反编译出他想要的汇编程序。

现在已知有n种作业(编号为1~n)和m对作业之间的依赖关系，小r想知道编号为k的作业依赖于哪些作业，以及哪些作业依赖于编号为k的作业。

输入加判断~~~

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PB push_back
#define endl '\n'
const int N=2e5+7;
const int INF=1e8,mod=1e9+7;
int n,m,k;
vector<int>a,b;
int main()
{
    cin>>n>>m>>k;
    int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        if(x==k)a.PB(y);
        if(y==k)b.PB(x);
    }
    for(int i=0;i<a.size();i++){
        if(i!=0)printf(" ");
        printf("%d",a[i]);
    }
    cout<<endl;
    for(int i=0;i<b.size();i++){
        if(i!=0)printf(" ");
        printf("%d",b[i]);
    }
    cout<<endl;
	return 0;
}

M Orx Zone

链接：https://ac.nowcoder.com/acm/contest/912/M
来源：牛客网

题目描述
Daenerys Stormborn, 风暴中出生的丹尼莉丝，the Unburnt, 烧不死的，Queen of Meereen, 弥林女王，Queen of the Andals and the Rhoynar and the First Men, 安达尔人，罗伊那人，和先民的女王，Lord of the Seven Kingdoms, 七国之主，Protector of the Realm, 疆域保护者，Khaleesi of the Great Grass Sea, 多斯拉克海的女主，Breaker of Shackles, 打破铐镣者，Mother of Dragons, 龙母. 强如龙母也只有这么点名号

垃圾rx,保龄球下水道选手rx,***方块大师rx,🏆选手xr,手速狗xr,练习时长两年半的acm练习生rx,线段树大师rx,数竞选手rx,手游忠实厨力玩家xr,下水道英语老师rx,图论大师rx,大珩班尖子生xr…txr的名号存在于千千万万的iXiang心中,无穷无尽

您作为iXiang,十分热衷于统计txr的名号数,现在有一个全部由小写字母组成的字符串S,字符串中同时包含’r’,‘x’(无序)的非空子串数为txr的名号数

一个字符串s被称作另一个字符串S的非空子串,表示为S=XsY(X,Y可为空串,s不可为空串)

思路：对于1-n为左边界的情况恭喜就是(n+1-当前最近的’x’和’r’的下标的较大值）

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PB push_back
#define endl '\n'
const int N=2e6+7;
const int INF=1e8,mod=1e9+7;
int n,m,k;
char a[N];
int x[N],r[N];
int main()
{
    scanf("%s",a+1);
    int l=strlen(a+1);
    int ed=l+1;
    for(int i=l;i>=1;i--){//在该点后最近的x
            if(a[i]=='x'){
                ed=i;
            }
            x[i]=ed;
    }
    ed=l+1;
    for(int i=l;i>=1;i--){//在该点后最近的r
            if(a[i]=='r'){
                ed=i;
            }
            r[i]=ed;
    }
    LL ans=0;
    for(int i=1;i<=l;i++){
        int k=max(x[i],r[i]);
        ans+=l-k+1;
    }
    cout<<ans;
	return 0;
}