牛客小白月赛16
比赛地址：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++版本一
