2019牛客假日团队赛7 A,B,C,D,E,G,H,I,K

admin 管理员组

文章数量: 887021

2019牛客假日团队赛7 A,B,C,D,E,G,H,I,K

又写了一天的水题，牛客多校第二场还没怎么补...我好咸鱼啊QAQ

A-Oh Those Rollers（简单BFS）

题目链接：

题目大意：n个齿轮，每个齿轮有它的原点，半径，原点在0,0处的是主动轮，问最后一个被动轮是多少号齿轮。

思路：BFS，记录齿轮直接相连的有多少个。如果一组齿轮构成一个环，那么这个环里面的所有齿轮都不是最后一个被动轮，因为任意一个都能带动其他轮。然后找到最后一个只连接一个齿轮的轮子，这个就是最后的被动轮。

ACCode：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand(unsigned)time(NULL));rand();#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;const int MAXN=2e3+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)struct Node{int v,nxt;Node(int _v=0,int _nxt=0){v=_v;nxt=_nxt;}
};
struct Point{int x,y,r;Point(int _x=0,int _y=0,int _r=0){x=_x;y=_y;r=_r;}
};
Node Edge[MAXN<<2];
int Head[MAXN<<2],Ecnt;
Point Dots[MAXN];
int Vis[MAXN];
int n;void Intt(){clean(Head,-1);Ecnt=0;clean(Vis,0);
}
void AddEdge(int u,int v){Edge[Ecnt]=Node(v,Head[u]);Head[u]=Ecnt++;
}
int Distance(int i,int j){return (Dots[i].x-Dots[j].x)*(Dots[i].x-Dots[j].x)+(Dots[i].y-Dots[j].y)*(Dots[i].y-Dots[j].y);
}
int BFS(int S){queue<int> que;que.push(S);Vis[S]=1;while(que.size()){int u=que.front();que.pop();int Cnt=0,flag=1;for(int i=Head[u];i+1;i=Edge[i].nxt){//遍历相连的点 int v=Edge[i].v;Cnt++;if(Vis[v]==0){Vis[v]=1;que.push(v);flag=0;}}if(Cnt==1&&flag) return u;}return 0;
}
int main(){Intt();scanf("%d",&n);int S;for(int i=1;i<=n;++i){scanf("%d%d%d",&Dots[i].x,&Dots[i].y,&Dots[i].r);if(Dots[i].x==0&&Dots[i].y==0) S=i;}for(int i=1;i<=n;++i){for(int j=i+1;j<=n;++j){if(Distance(i,j)==(Dots[i].r+Dots[j].r)*(Dots[i].r+Dots[j].r)){AddEdge(i,j);AddEdge(j,i);}}}int T=BFS(S);printf("%d %d\n",Dots[T].x,Dots[T].y);
}

B-Lake Making（简单暴力）

题目链接：

题目大意：给出一个图，代表高度，给出一个水平面代表水的高度。然后每组牛占领3*3的格子。踩一下降低1个高度。给出n个操作后，问能够储存多少单位的水。每组牛踩的时候，3*3范围内只会踩最高的陆地。

思路：粗略算了一下，暴力模拟就好了

ACCode：

const int MAXN=1e2+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)int H[MAXN][MAXN];
int n,m,h;int main(){int opt;scanf("%d%d%d%d",&n,&m,&h,&opt);for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){scanf("%d",&H[i][j]);}}while(opt--){int i,j,del;scanf("%d%d%d",&i,&j,&del);int MaxH=-INF32;for(int p=i;p<=i+2;++p){for(int q=j;q<=j+2;++q){MaxH=max(MaxH,H[p][q]);}}del=MaxH-del;for(int p=i;p<=i+2;++p){for(int q=j;q<=j+2;++q){H[p][q]=min(H[p][q],del);}}}ll SumH=0;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){SumH+=max(0,h-H[i][j]);}}printf("%lld\n",1ll*SumH*72*72);
}

C-Hotel（线段树区间合并板子）

题目链接：

题目大意：给出n个房间，每个房间有自己的标号：1,2,3,。。。n。每次来一组人，判断能够分配连续房间的第一个房间号是多少，不能分配输出0.房客也会离开，一起离开[l,r]房间的房客。

思路：线段树合并板子题。

ACCode：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand(unsigned)time(NULL));rand();#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;const int MAXN=5e4+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)struct SegTree{struct Node{int l,r;int ls,rs,ms;int lazy;};Node Tree[MAXN<<2];void PushDown(int rt){if(Tree[rt].lazy!=-1){Tree[rt<<1].lazy=Tree[rt<<1|1].lazy=Tree[rt].lazy;Tree[rt<<1].ls=Tree[rt<<1].rs=Tree[rt<<1].ms=Tree[rt].lazy?0:Tree[rt<<1].r-Tree[rt<<1].l+1;Tree[rt<<1|1].ls=Tree[rt<<1|1].rs=Tree[rt<<1|1].ms=Tree[rt].lazy?0:Tree[rt<<1|1].r-Tree[rt<<1|1].l+1;Tree[rt].lazy=-1;}}void PushUp(int rt){Tree[rt].ls=Tree[rt<<1].ls;Tree[rt].rs=Tree[rt<<1|1].rs;int mid=(Tree[rt].l+Tree[rt].r)>>1;if(Tree[rt].ls==mid-Tree[rt].l+1) Tree[rt].ls+=Tree[rt<<1|1].ls;if(Tree[rt].rs==Tree[rt].r-mid) Tree[rt].rs+=Tree[rt<<1].rs;Tree[rt].ms=max(max(Tree[rt<<1].ms,Tree[rt<<1|1].ms),Tree[rt<<1].rs+Tree[rt<<1|1].ls);}void Build(int l,int r,int rt){Tree[rt].l=l;Tree[rt].r=r;Tree[rt].ls=Tree[rt].rs=Tree[rt].ms=r-l+1;Tree[rt].lazy=-1;if(l==r) return ;int mid=(l+r)>>1;Build(l,mid,rt<<1);Build(mid+1,r,rt<<1|1);}void Update(int l,int r,int val,int rt){if(Tree[rt].l==l&&Tree[rt].r==r){Tree[rt].lazy=val;Tree[rt].ls=Tree[rt].rs=Tree[rt].ms=val?0:r-l+1;return ;}PushDown(rt);int mid=(Tree[rt].l+Tree[rt].r)>>1;if(r<=mid) Update(l,r,val,rt<<1);else if(l>mid) Update(l,r,val,rt<<1|1);else{Update(l,mid,val,rt<<1);Update(mid+1,r,val,rt<<1|1);}PushUp(rt);}int Query(int l,int r,int val,int rt){if(l==r) return l;PushDown(rt);int mid=(l+r)>>1;if(Tree[rt<<1].ms>=val) return Query(l,mid,val,rt<<1);else if(Tree[rt<<1].rs+Tree[rt<<1|1].ls>=val) return mid-Tree[rt<<1].rs+1;return Query(mid+1,r,val,rt<<1|1);}
};
SegTree Seg;
int n,m;int main(){scanf("%d%d",&n,&m);Seg.Build(1,n,1);while(m--){int opt,a,b;scanf("%d%d",&opt,&a);if(opt==1){if(Seg.Tree[1].ms<a) printf("0\n");else{b=Seg.Query(1,n,a,1);printf("%d\n",b);Seg.Update(b,b+a-1,1,1);}}else{scanf("%d",&b);Seg.Update(a,a+b-1,0,1);}}
}

D-家族树（简单LCA）

题目链接：

题目大意：中文题

思路：LCA，加一个map就好了。模拟就好了。

ACCode：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand(unsigned)time(NULL));rand();#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;const int MAXN=3e2+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)struct Node{int v,nxt;Node(int _v=0,int _nxt=0){v=_v;nxt=_nxt;}
};
Node Edge[MAXN<<2];
int Head[MAXN<<2],Ecnt;
int Deg[MAXN<<2];
int Rt[MAXN<<2],tot;
int Fa[MAXN<<2][30],Deep[MAXN];
map<string,int> NI;
map<int,string> IN;
int Mcnt;
string A,B;
int n;void Intt(){clean(Head,-1);Ecnt=0;IN.clear();NI.clear();Mcnt=0;clean(Fa,-1);clean(Deep,0);
}
void AddEdge(int u,int v){Edge[Ecnt]=Node(v,Head[u]);Head[u]=Ecnt++;
}
void DFS(int u){for(int i=Head[u];i+1;i=Edge[i].nxt){int v=Edge[i].v;if(Deep[v]==0){Deep[v]=Deep[u]+1;Fa[v][0]=u;int up=0,pre=u;while(Fa[pre][up]>0){Fa[v][up+1]=Fa[pre][up];pre=Fa[pre][up++];}DFS(v);}}
}
int LCA(int a,int b){if(Deep[a]<Deep[b]) swap(a,b);int lim=log2(Deep[a])+1;for(int i=lim;i>=0;--i){//if(Fa[a][i]==-1) continue;if(Deep[Fa[a][i]]>=Deep[b]) a=Fa[a][i];}if(a==b) return a;for(int i=lim;i>=0;--i){if(Fa[a][i]!=Fa[b][i]){a=Fa[a][i];b=Fa[b][i];}}return Fa[a][0];
}
int main(){Intt();cin>>n>>A>>B;NI[A]=++Mcnt;IN[Mcnt]=A;//1NI[B]=++Mcnt;IN[Mcnt]=B;//2for(int i=1;i<=n;++i){string fa,son;cin>>fa>>son;if(NI[fa]==0){NI[fa]=++Mcnt;IN[Mcnt]=fa;}if(NI[son]==0){NI[son]=++Mcnt;IN[Mcnt]=son;}AddEdge(NI[fa],NI[son]);//AddEdge(NI[son],NI[fa]);Deg[NI[son]]++;}tot=0;for(int i=1;i<=Mcnt;++i){if(Deg[i]==0) Rt[++tot]=i;}for(int i=1;i<=tot;++i){Deep[Rt[i]]=1;DFS(Rt[i]);}int rt=LCA(1,2);if(rt==-1){//无关系 cout<<"NOT RELATED"<<endl;return 0;}
//	cout<<IN[rt]<<" "<<Deep[1]<<" "<<Deep[2]<<endl; if(Deep[1]>=Deep[2]){//B是A的长辈 if(rt==2){//B是A的直接母系 int rela=Deep[1]-Deep[rt];cout<<B<<" is the ";for(int i=2;i<=rela-1;++i) cout<<"great-";if(rela>=2) cout<<"grand-";//for(int i=1;i<=rela-1;++i) cout<<"grand-";cout<<"mother of "<<A<<endl;}else{//int relA=Deep[1]-Deep[rt],relB=Deep[2]-Deep[rt];
//			cout<<relA<<" "<<relB<<endl;if(relB==1){//具有称呼 if(Deep[1]==Deep[2]) cout<<"SIBLINGS"<<endl;//母亲是一头奶牛 else{cout<<B<<" is the ";for(int i=2;i<=relA-1;++i) cout<<"great-";cout<<"aunt of "<<A<<endl;}}else cout<<"COUSINS"<<endl;//cout<<B<<"is the cousin of "<<A<<endl;}}else{//A是B的长辈 if(rt==1){//A是B的直系母亲 int relB=Deep[2]-Deep[rt];cout<<A<<" is the ";for(int i=2;i<=relB-1;++i) cout<<"great-";if(relB>=2) cout<<"grand-";cout<<"mother of "<<B<<endl; }else{int relA=Deep[1]-Deep[rt],relB=Deep[2]-Deep[rt];
//			cout<<relA<<" "<<relB<<endl;if(relA==1){//具有称呼 if(Deep[1]==Deep[2]) cout<<"SIBLINGS"<<endl;//母亲是一头奶牛 else{cout<<A<<" is the ";for(int i=2;i<=relB-1;++i) cout<<"great-";cout<<"aunt of "<<B<<endl;}}else cout<<"COUSINS"<<endl;//cout<<B<<"is the cousin of "<<A<<endl;}}
}
/*
9 A B
9 A C
9 A Y
9 E C
9 Z Y
B A
B C
E F
D E
D B
G H
G D
H I
Z Y
*/

EStatistics（水题）

题目链接：

题目大意：给出一组数，问平均数和中位数。

思路：暴力跑就好了。

ACCode：

const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)double A[MAXN];
int n;int main(){scanf("%d",&n);for(int i=1;i<=n;++i) scanf("%lf",&A[i]);sort(A+1,A+1+n);double Ans=0;for(int i=1;i<=n;++i) Ans+=A[i];printf("%lf\n%lf\n",Ans/(1.0*n),n&1?A[n/2+1]:(A[n/2]+A[n/2+1])/2.0);
}

F-Making the Grade

题目链接：

题目大意：n个路的高度，填高或降低一单位需要花费一单位。问形成单增或单减最少花费。

思路：

ACCode：

G-Eating Together（简单DP）

题目链接：

题目大意：n个牛，每头牛都有自己的编号(1~3)，问最少多少次操作，能够使牛的编号递减或递增。

思路：DP。给文少之后秒过，他说太简单了就不写博客了....我就把代码偷过来了...。

ACCode：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mx=0x3f3f3f3f;
const int maxn=30030;
int dp[maxn][4];int a[maxn+3];
int main(){int n;memset(dp,0,sizeof(dp));scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){for(int j=1;j<=3;j++){int mn=n;for(int k=1;k<=j;k++){if(mn>dp[i-1][k]){mn=dp[i-1][k];}}mn+=(j!=a[i]);dp[i][j]=mn;}}int bianbianbian=dp[n][3];bianbianbian=min(dp[n][2],bianbianbian);bianbianbian=min(dp[n][1],bianbianbian);// cout<<bianbianbian<<endl;memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){for(int j=1;j<=3;j++){int mn=n;for(int k=j;k<=3;k++){mn=min(dp[i-1][k],mn);}mn+=(j!=a[i]);dp[i][j]=mn;}}bianbianbian=min(bianbianbian,dp[n][1]);bianbianbian=min(bianbianbian,dp[n][2]);bianbianbian=min(bianbianbian,dp[n][3]);printf("%d\n",bianbianbian);
}

H-Cow Multiplication（模拟水题）

题目链接：

题目大意：两个数，根据提上给的运算（按位想乘），输出答案。

思路：暴力模拟即可。

ACCode：

char S1[20],S2[20];
int A[20],B[20];int main(){cin>>S1>>S2;int l1=strlen(S1),l2=strlen(S2);
//	printf("%d%d\n",len1,len2);for(int i=0;i<l1;++i) A[i+1]=S1[i]-'0';for(int i=0;i<l2;++i) B[i+1]=S2[i]-'0';ll Ans=0;for(int i=1;i<=l1;++i){for(int j=1;j<=l2;++j){Ans+=1ll*A[i]*B[j];}}printf("%lld\n",Ans);}

I-Meteor Shower（简单搜索）

题目链接：

题目大意：给出一张图，一开始在0,0点。不同的时间会有陨石砸下来，毁灭范围是十字。毁灭之后就不能再走了。陨石是先落下来的。问最快走到的安全点（不会被陨石砸到）是哪一点，走不到输出-1。

思路：搜索就好了，数据范围很小，暴力出所有的路线，然后判断哪些被陨石砸死了，等所有陨石砸完后，输出最小的那个时间就好了。

ACCode：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand(unsigned)time(NULL));rand();#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;const int MAXN=3e2+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)struct Point{int x,y,t;Point(int _x=0,int _y=0,int _t=0){x=_x;y=_y;t=_t;}friend int operator < (Point a,Point b){return a.t<b.t;}
};
Point Dots[MAXN*MAXN];
int MP[MAXN][MAXN];
int Fx[5]={0,1,-1,0,0},Fy[5]={0,0,0,-1,1};
int m;void Debug(){for(int i=0;i<=10;++i){for(int j=0;j<=10;++j){printf(" %d",MP[i][j]);}printf("\n");}printf("\n");
}
void BFS(){queue<Point> que;que.push(Point(0,0,0));MP[0][0]=0;int T=0,str=1;while(que.size()){//if(que.front().t>Dots[m].t+1) return ;Point u=que.front();que.pop();T=max(T,u.t);for(int i=str;Dots[i].t<=T&&i<=m;str=++i){//陨石先砸 for(int j=0;j<=4;++j){Point v=Point(Dots[i].x+Fx[j],Dots[i].y+Fy[j],0);if(v.x>=0&&v.y>=0&&v.x<MAXN&&v.y<MAXN) MP[v.y][v.x]=-1;}}if(MP[u.y][u.x]==-1) continue;for(int i=1;i<=4;++i){//遍历四个方向，看能向那边走 Point v=Point(u.x+Fx[i],u.y+Fy[i],u.t+1);if(v.x>=0&&v.y>=0&&v.x<MAXN&&v.y<MAXN&&MP[v.y][v.x]>v.t){//可以走 MP[v.y][v.x]=v.t;que.push(v);}}//Debug();}for(int i=str;i<=m;++i){for(int j=0;j<=4;++j){Point v=Point(Dots[i].x+Fx[j],Dots[i].y+Fy[j],0);if(v.x>=0&&v.y>=0&&v.x<MAXN&&v.y<MAXN) MP[v.y][v.x]=-1;}}
}
int main(){clean(MP,INF32);scanf("%d",&m);for(int i=1;i<=m;++i){scanf("%d%d%d",&Dots[i].x,&Dots[i].y,&Dots[i].t);}sort(Dots+1,Dots+1+m);BFS();int Ans=INF32;for(int i=0;i<MAXN;++i){for(int j=0;j<MAXN;++j){if(MP[i][j]==-1) continue;else Ans=min(Ans,MP[i][j]);}}if(Ans==INF32) printf("-1\n");else printf("%d\n",Ans);
}

J-雪地靴

题目链接：

题目大意：中文题。

思路：

ACCode：

K-Game of Lines（简单计算几何）

题目链接：

题目大意：给出n个点，求出这些点所连成所有不平行的线有多少条。

思路：首先将所有线转化成向量，使向量分布在一四象限。排序极角排序判重即可。

ACCode：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand(unsigned)time(NULL));rand();#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;const int MAXN=200+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)struct Point{int x,y;Point(int _x=0,int _y=0){x=_x;y=_y;}friend Point operator - (Point a,Point b){return Point(a.x-b.x,a.y-b.y);}friend int operator ^ (Point a,Point b){return a.x*b.y-a.y*b.x;}friend int operator < (Point a,Point b){return (a^b)>0;}void Reduc(){if((x<=0&&y<=0)||(x<=0&&y>=0)){x=-x;y=-y;}}
};
Point Dots[MAXN],V[MAXN*MAXN];
map<Pair,int> Vis;
int n;int main(){scanf("%d",&n);for(int i=1;i<=n;++i) scanf("%d%d",&Dots[i].x,&Dots[i].y);int Vcnt=0;for(int i=1;i<=n;++i){for(int j=i+1;j<=n;++j){V[++Vcnt]=Dots[j]-Dots[i];V[Vcnt].Reduc();}}sort(V+1,V+1+Vcnt);int Ans=0;for(int i=1;i<=Vcnt;++i){if((V[i]^V[i%Vcnt+1])==0) continue;Ans++;
//		printf("%d\n",Ans);}printf("%d\n",Ans);
}

本文标签： 2019牛客假日团队赛7 A b c D e