比赛地址:https://ac.nowcoder.com/acm/contest/949#question

官方题解:https://ac.nowcoder.com/discuss/205975

Problem A 小石的签到题

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

题意:

题解:博弈论

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<<(n!=1?"Shi":"Yang")<<endl;
    //}

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

Problem B 小雨的三角形

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

题意:

题解:杨辉三角+前缀和

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=1000+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;
ll a[N][N],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);
    b[1]=a[1][1]=1;
    for(int i=2;i<=n;i++){
        a[i][1]=a[i][i]=i;
        b[i]=(b[i-1]+a[i][1]+a[i][i])%MOD;
        for(int j=2;j<i;j++){
            a[i][j]=(a[i-1][j-1]+a[i-1][j])%MOD;
            b[i]=(b[i]+a[i][j])%MOD;
        }
    }
    while(m--){
        scanf("%d%d",&l,&r);
        cout<<(b[r]-b[l-1]+MOD)%MOD<<endl;
    }
    //}

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

Problem C 小石的海岛之旅

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

题意:

题解:贪心

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 h[N],a;
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<=n;i++)scanf("%d",&h[i]);
    for(int i=1;i<=m;i++){
        scanf("%d",&a);
        ans=0;
        for(int i=1;i<=n;i++)if(h[i-1]<=a&&h[i]>a)ans++;
        cout<<ans<<endl;
    }
    //}

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

Problem D 小阳买水果

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

题意:

题解:前缀和+排序+贪心

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=2000000+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 t,n,m,k,p;
int l,r,u,v;
int ans,cnt,flag,temp,sum;
ll a[N],b[N];
struct node{
    ll b;
    int id;
    bool operator < (const node &S)const{
        if(b==S.b)
            return id>S.id;
        return b<S.b;
    }
}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",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),b[i]=e[i].b=e[i-1].b+a[i],e[i].id=i;
    sort(e,e+n+1);
    int pos=e[0].id;
    for(int i=1;i<=n;i++){//cout<<pos<<" "<<e[i].id<<endl;
        if(pos<e[i].id&&b[e[i].id]-b[pos]>0){
            ans=max(ans,e[i].id-pos);
        }
        pos=min(pos,e[i].id);
    }
    cout<<ans<<endl;
    //}

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

Problem E 小雨的矩阵

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

题意:

题解:DFS

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=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][N];
set<ll>st;
void dfs(int x,int y,ll num){
    if(x==n&&y==n){
        st.insert(num);
    }
    if(x>n||y>n)
        return;
    dfs(x+1,y,num+a[x+1][y]);
    dfs(x,y+1,num+a[x][y+1]);
}
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);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    dfs(1,1,a[1][1]);
    cout<<st.size()<<endl;
    //}

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

Problem F 小石的妹子

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

题意:

题解:

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[N],cnt,flag,temp,sum;
int tree[N],c[N];
struct node{
    int a,b;
    int id;
    bool operator <(const node &S)const{
        return a<S.a;
    }
}e[N];
void add(int p,int o){
    while (p<=n){tree[p]=max(tree[p],o);p+=(p&(-p));}
}
int ask(int p){
    int s=0;
    while (p){s=max(tree[p],s);p-=(p&(-p));}
    return s;
}
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);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&e[i].a,&e[i].b);
        e[i].id=i;
        c[i]=e[i].b;
    }
    sort(c+1,c+n+1);
    for (int i=1;i<=n;i++) e[i].b=n+1-(lower_bound(c+1,c+n+1,e[i].b)-c);
    sort(e+1,e+n+1);
    for (int i=n;i>=1;i--){
        ans[e[i].id]=ask(e[i].b)+1;
        add(e[i].b,ans[e[i].id]);
    }
    for (int i=1;i<=n;i++) printf ("%d\n",ans[i]);
    //}

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

Problem G 小石的图形

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

题意:

题解:

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);
    printf("%.3f\n",n*n/(2*PI));
    //}

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

Problem H 小阳的贝壳

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

题意:

题解:差分数组+数论+线段树

参考文章:差分数组
区间 具有结合律,很容易用线段树维护,考虑如何区间修改。
首先要知道 的一个性质:


所以我们可以在线段树上建立差分数组,维护 区间和区间
显然区间 就是 ,其中 表示差分数组。

至于第 2 个操作完全就是来搞笑的(主要用来引导别人联想到差分),只要维护差分数组的区间 max 和区间 min 就行了。

最后的答案就是 区间 max 与 区间 min 相反数 的较大值。

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];
struct node{
    int val;
    int minl;
    int maxl;
    int sum;
}tree[N<<2];
void pushup(int rt){
    tree[rt].val=__gcd(tree[rt<<1].val,tree[rt<<1|1].val);
    tree[rt].minl=min(tree[rt<<1].minl,tree[rt<<1|1].minl);
    tree[rt].maxl=max(tree[rt<<1].maxl,tree[rt<<1|1].maxl);
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void build(int l,int r,int rt){
    if(l==r){
        tree[rt].sum=tree[rt].minl=tree[rt].maxl=tree[rt].val=a[l]-a[l-1];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int l,int r,int rt,int L,int C){
    if(l==r){
        tree[rt].minl=tree[rt].minl+C;
        tree[rt].maxl=tree[rt].maxl+C;
        tree[rt].val=tree[rt].val+C;
        tree[rt].sum=tree[rt].sum+C;
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)update(l,mid,rt<<1,L,C);
    else update(mid+1,r,rt<<1|1,L,C);
    pushup(rt);
}
int querysum(int l,int r,int rt,int L,int R){
    if (L > R)
        return 0;
    if(L<=l&&r<=R){
        return tree[rt].sum;
    }
    int mid=(l+r)>>1;
    if(R<=mid) return querysum(l,mid,rt<<1,L,R);
    else if(mid<L)return querysum(mid+1,r,rt<<1|1,L,R);
    else return querysum(l,mid,rt<<1,L,R)+querysum(mid+1,r,rt<<1|1,L,R);
}
int queryval(int l,int r,int rt,int L,int R){
    if (L > R)
        return 0;
    if(L<=l&&r<=R){
        return tree[rt].val;
    }
    int mid=(l+r)>>1;
    if(R<=mid) return queryval(l,mid,rt<<1,L,R);
    else if(mid<L)return queryval(mid+1,r,rt<<1|1,L,R);
    else return __gcd(queryval(l,mid,rt<<1,L,R),queryval(mid+1,r,rt<<1|1,L,R));
}
int queryminl(int l,int r,int rt,int L,int R){
    if (L > R)
        return 0;
    if(L<=l&&r<=R){
        return tree[rt].minl;
    }
    int mid=(l+r)>>1;
    if(R<=mid) return queryminl(l,mid,rt<<1,L,R);
    else if(mid<L)return queryminl(mid+1,r,rt<<1|1,L,R);
    else return min(queryminl(l,mid,rt<<1,L,R),queryminl(mid+1,r,rt<<1|1,L,R));
}
int querymaxl(int l,int r,int rt,int L,int R){
    if (L > R)
        return 0;
    if(L<=l&&r<=R){
        return tree[rt].maxl;
    }
    int mid=(l+r)>>1;
    if(R<=mid) return querymaxl(l,mid,rt<<1,L,R);
    else if(mid<L)return querymaxl(mid+1,r,rt<<1|1,L,R);
    else return max(querymaxl(l,mid,rt<<1,L,R),querymaxl(mid+1,r,rt<<1|1,L,R));
}
void printtree(int l,int r,int rt){
    if(l==r){
        printf("%lld ",tree[rt].sum);
        return;
    }
    int mid=(l+r)>>1;
    printtree(l,mid,rt<<1);
    printtree(mid+1,r,rt<<1|1);
}
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<=n;i++)scanf("%d",&a[i]);
    build(1,n,1);
    while(m--){
        scanf("%d%d%d",&p,&l,&r);
        //printtree(1,n,1);
        //cout<<endl;
        if(p==1){
            scanf("%d",&k);
            update(1,n,1,l,k);
            if(r+1<=n)update(1,n,1,r+1,-k);
        }else if(p==2){
            cout<<max(abs(querymaxl(1,n,1,l+1,r)),abs(queryminl(1,n,1,l+1,r)))<<endl;
        }else if(p==3){
            cout<<abs(__gcd(querysum(1,n,1,1,l),queryval(1,n,1,l+1,r)))<<endl;
            //cout<<querysum(1,n,1,l,r)<<" "<<queryval(1,n,1,l+1,r)<<endl;
        }
    }
    //}

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

Problem I 石头剪刀布

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

题意:

题解:

C++版本一

 

Problem J 小雨坐地铁

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

题意:

题解:

C++版本一