很长时间没更新有意义的题目了呢,这是一套题撒,于是乎我便开心的边刷题边发题解了撒.
第一题: 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;
}
(简直短到奇葩)