Google APAC 2016 University Graduates Test Round D

网友投稿 270 2022-09-14

Google APAC 2016 University Graduates Test Round D

之前的Round A晋级了...但是HR说今年7月因为Codejam的原因面过一次了不给再面了..所以Round C和Round B都没怎么做..这次最后一场Round D还是水了一发...虽然太弱了..水了两题...但还是拿了个通过笔试的邮件...估计还是不会给面...

A - Dynamic Grid

题解:

100*100*1000可以接受...所以暴力求解.

Code:

#include #include #include #include #include #include #include #include using namespace std; int a[105][105],n,m,f[4][2]={{0,1},{1,0},{0,-1},{-1,0}};char s[10],str[105][105];bool used[105][105];void dfs(int x,int y){ if (x==0 || y==0 || x>n || y>m) return; if (!a[x][y]) return; if (used[x][y]) return; used[x][y]=true; for (int k=0;k<4;k++) dfs(x+f[k][0],y+f[k][1]);}int main(){ int T,cases; freopen("A-large.in.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%d",&T); for (int cases=1;cases<=T;cases++){ printf("Case #%d:\n",cases); scanf("%d%d",&n,&m); for (int x=1;x<=n;x++) scanf("%s",str[x]+1); for (int x=1;x<=n;x++) for (int y=1;y<=m;y++) a[x][y]=str[x][y]-'0'; int num; scanf("%d",&num); while (num--){ scanf("%s",s); if (s[0]=='Q'){ int ans=0; memset(used,false,sizeof(used)); for (int x=1;x<=n;x++) for (int y=1;y<=m;y++) if (a[x][y] && !used[x][y]){ ans++; dfs(x,y); } printf("%d\n",ans); }else{ int x,y,z; scanf("%d%d%d",&x,&y,&z); x++,y++; a[x][y]=z; } } } return 0;}

B - gBalloon

题意:

Code:

#include #include #include #include #include #include #include #include using namespace std; const int oo=10005;int V[1005],H[105],P[105]; bool judge(int n,int m,int q,int t){ int sum=0,k; for (int i=1;i<=n;i++){ int x,x0,temp=oo; if (P[i]==0) continue; for (int h=0;h0 && V[h]>0) continue; if (P[i]<0 && V[h]<0) continue; x0=abs(P[i]),x=abs(V[h]); if ((x0+x-1)/x>t) continue; temp=min(temp,abs(h-H[i])); } sum+=temp; } return sum<=q;}int main(){ int T,cases; freopen("B-large.in.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%d",&T); for (int cases=1;cases<=T;cases++){ printf("Case #%d: ",cases); int n,m,q; scanf("%d%d%d",&n,&m,&q); for (int i=0;i1){ int mid=(L+R)>>1; if (judge(n,m,q,mid)) R=mid; else L=mid; } if (R==oo) puts("IMPOSSIBLE"); else printf("%d\n",R); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

上一篇:Google APAC 2016 University Graduates Test Round A
下一篇:对决策树，随机森林的初步认识
相关文章

 发表评论

暂时没有评论，来抢沙发吧~