首页 > 代码库 > 二模 06day2
二模 06day2
很长时间没更新有意义的题目了呢,这是一套题撒,于是乎我便开心的边刷题边发题解了撒.
第一题: interval
比较好玩的一题撒, 分分钟过了, 就是模拟贪吃蛇但是没有食物(嗯,只要你判断冲突).
整个数组拿来移当然是不行的撒, 只要在末尾移去一个方格再向头部正对出放一个方格就行了撒.
编程复杂度挺低的, 可以直接修改一下做贪吃蛇游戏的后台.
(最坑的地方就是坐标系.无图无**)
其实也不算很坑啦.
#include <cstdio>#include <cstring>struct point{ int x,y;};point gpos(char ch,point c){ switch(ch){ case ‘E‘: ++c.x; break; case ‘W‘: --c.x; break; case ‘S‘: --c.y; break; case ‘N‘: ++c.y; break; } return c;}struct queue{ point q[2000],t; bool map[100][100]; int s,e,i; int move(char c){ map[q[s].x][q[s].y]=false; ++s; t=gpos(c,q[e-1]); if(t.x>50||t.x<0) return 1; if(t.y>50||t.y<0) return 1; if(map[t.x][t.y]) return 2; map[t.x][t.y]=true; q[e]=t; ++e; return 0; } void reset(){ memset(map,0,sizeof map); memset(q,0,sizeof q); s=e=0; for(i=11;i<=30;++i){ q[e].y=25; q[e].x=i; map[i][25]=true; ++e; } }} q;int i,j,n;char c,str[1000];bool f;int main(){ freopen("interval.in","r",stdin); freopen("interval.out","w",stdout); while(scanf("%d\n",&n),n){ q.reset(); f=false; scanf("%s",str); for(i=0;i<n;++i){ c=str[i]; j=q.move(c); if(j){ if(j==1){ printf("The worm ran off the board on move %d.\n", i+1); }else{ printf("The worm ran into itself on move %d.\n", i+1); } f=true; break; } } if(!f) printf("The worm successfully made all %d moves.\n", n); } return 0;}
第二题 直角三角形
平面上给定 n 个两两不同的整数点,统计以给定的点为顶点,其直角边平行于坐标轴的直角三角形的个数.
嗯横纵轴离散化.(嗯hash似乎比较好,统计x,y的实在不想写啊摔)
为什么离散化呢因为数据范围不小.
30%的数据满足 n≤100;
50%的数据满足 n≤1000;
100%的数据满足 0<n≤100,000,所有坐标不超过 32 位整数范围。
就是这样辣.
#include <cstdio>struct node{ int d,n; long long s;} p[200000];int he[2][103979],pl,temp,temp2;inline int find(int h,bool n){ temp=h; temp2=h=h%103979; h=he[n][h]; while(h && p[h].d!=temp) h=p[h].n; if(h) return h; ++pl; p[pl].n=he[n][temp2]; p[pl].d=temp; p[pl].s=0; he[n][temp2]=pl; return pl;}long long sum;int i,n,a,b;int xs[200000],ys[200000];int main(int argc, char const *argv[]){ freopen("right.in","r",stdin); freopen("right.out","w",stdout); scanf("%d",&n); for(i=0;i<n;++i){ scanf("%d %d",&a,&b); xs[i]=a; ys[i]=b; a=find(a,0),b=find(b,1); ++p[a].s,++p[b].s; } for(i=0;i<n;++i){ a=find(xs[i],0),b=find(ys[i],1); sum+=(p[a].s-1)*(p[b].s-1); } printf("%lld\n", sum); return 0;}
(简直短到奇葩)
二模 06day2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。