9502 ARDF
时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0
题型: 编程题 语言: 无限制
Description
ARDF，全称无线电测向。无线电测向运动是竞技体育项目之一，也是无线电活动的主要内容。它类似于众所周知的捉迷藏游戏，但它是寻找能发射无线电波的小型信号源（即发射机）， 是无线电捉迷藏，是现代无线电通讯技术与传统捉迷藏游戏的结合。大致过程是：在旷野、山丘的丛林或近郊、公园等优美的自然环境中，事先隐藏好数部信号源，定时发出规定的电报信号。 参加者手持无线电测向机，测出隐蔽电台的所在方向，采用徒步方式，奔跑一定距离，迅速、准确地逐个寻找出这些信号源。以在规定时间内，找满指定台数、实用时间少者为优胜。 通常， 我们把实现巧妙隐藏起来的信号源比喻成狡猾的狐狸，故此项运动又称无线电“猎狐”或抓“狐狸”。
摩斯密码是一种时通时断的信号代码，这种信号代码通过不同的排列顺序来表达不同的英文字母、数字和标点符号等。摩斯密码中，-表示长，.表示短。 摩斯密码表示两个字元是采用直接相连法，即直接将第二个字元的摩斯密码接到第一个字元摩斯密码的后面。一连串的摩斯密码连成一起，就是要发送的信号。
无线电测向分为2米波段和80米波段，区别在于电波的波长不同，接收用的机器也不同。 而信号源发出的信号为摩斯密码，测向运动两个波段对应的摩斯密码如下：
号码 2米波段 80米波段
0 ----- -----
1 .---- -- ---.
2 ..--- -- ---..
3 ...-- -- ---...
4 ....- -- ---....
5 ..... -- ---.....
6 -.... -....
7 --... --...
8 ---.. ---..
9 ----. ----.
BM是测向新手，对于辨别信号，信号源定位等方法都不太熟悉。现在，又到训练时间了。教练让BM拿了一部测向机在听信号，以训练辨别信号的能力。 不过，变态的教练不仅要BM分辨每个信号源对应是什么数字，还问这两个数字之和对应的摩斯密码是什么！但是，BM却不知道这是哪个波段的信号，又还没有记熟每个号码对应的摩斯密码，咋办？ 答不出可是要罚跑华农一圈啊！！！
Arokenda在训练过程中不忍心看着BM就这样受罚，就帮了BM一把，给了BM一个摩斯密码对应表和破译多位数的方法，说将两个数变成整数再算。 但是听到某一信号时，BM听了很久还没听完。惨了！数位太多，int存不下，这次又咋办？
Arokenda说：“还不简单，用long long不就行了吗？long long可以表示-2^63至2^63-1之间的整数，而且又没有double只保留16位精度的问题。就像这样：
#include<stdio.h>
int main()
{
long long a;
scanf(“%lld”,&a);
printf(“%lld”,a);
return 0;
}
”
就在此时，教练发现他们俩的作弊行为！不解释，罚跑运动场3圈！@#$%^&*
训练还得继续，面对这魔鬼式训练，BM忍不住向大家求救！你能帮一下BM吗？
Input
输入一个整数T(T<=20)，表示教练员有几次测试。
接下来3行，第一行为一个整数W，表示该信号源是属于哪个波段，2或80。第二、三行为一串摩斯密码，长度不超过90，表示BM听到的两个信号源对应的信号。
Output
每组数据输出一行，输出两个信号源对应数字之和在相应波段下的摩斯密码。
Sample Input
3 2 .---- -.... 80 -- ---. -- ---... 80 -- ---.... ---..
Sample Output
--... -- ---.... -- ---.-- ---..
Hint
1、VC下long long的数据类型会编译不通过，此时将数据类型写成__int64，scanf和printf要使用%I64d代替%lld。
2、除了本题之外，其余题目也许也要用到long long，请根据需要自行考虑
Source
BM
Provider
a470086609
#include<stdio.h> #include<string.h> typedef struct { int flag; int len; char chunk[12]; }present[10]; present sale2, sale80; void Traverse() { int i; for(i=0; i<10; ++i) {sale2[i].flag = i; sale2[i].len = 5;} strcpy(sale2[0].chunk , "-----"); strcpy(sale2[1].chunk , ".----"); strcpy(sale2[2].chunk , "..---"); strcpy(sale2[3].chunk , "...--"); strcpy(sale2[4].chunk , "....-"); strcpy(sale2[5].chunk , "....."); strcpy(sale2[6].chunk , "-...."); strcpy(sale2[7].chunk , "--..."); strcpy(sale2[8].chunk , "---.."); strcpy(sale2[9].chunk , "----."); sale80[0].flag = 5; strcpy(sale80[0].chunk , "-- ---....."); sale80[0].len = 11; sale80[1].flag = 4; strcpy(sale80[1].chunk , "-- ---...."); sale80[1].len = 10; sale80[2].flag = 3; strcpy(sale80[2].chunk , "-- ---..."); sale80[2].len = 9; sale80[3].flag = 2; strcpy(sale80[3].chunk , "-- ---.."); sale80[3].len = 8; sale80[4].flag = 1; strcpy(sale80[4].chunk , "-- ---."); sale80[4].len = 7; sale80[5].flag = 0; strcpy(sale80[5].chunk , "-----"); sale80[5].len = 5; sale80[6].flag = 6; strcpy(sale80[6].chunk , "-...."); sale80[6].len = 5; sale80[7].flag = 7; strcpy(sale80[7].chunk , "--..."); sale80[7].len = 5; sale80[8].flag = 8; strcpy(sale80[8].chunk , "---.."); sale80[8].len = 5; sale80[9].flag = 9; strcpy(sale80[9].chunk , "----."); sale80[9].len = 5; return; } int main() { int a[20], b[20], sum[20]; int sel, i, j, T, s1len, s2len, s1cnt, s2cnt, temp, e, len, flag; char s1[100], s2[100], *str; Traverse(); scanf("%d", &T); while(T--) { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); memset(sum, 0, sizeof(sum)); memset(s1, 0, sizeof(s1)); memset(s2, 0, sizeof(s2)); s2len = s1len = s1cnt = s2cnt = flag = 0; scanf("%d", &sel); getchar(); //这里有一个回车，而fgets会吸收回车 //scanf("%s", s1); fgets(s1, 100, stdin); fgets(s2, 100, stdin); //scanf("%s", s2); s1len = strlen(s1)-1, s2len = strlen(s2)-1; if(sel == 2) { for(i=0, str=s1; i<s1len; ) { for(j=0; j<10; ++j) { if(str == strstr(str, sale2[j].chunk)) { i += sale2[j].len; a[s1cnt++] = sale2[j].flag; str = s1+i; break; } } } for(i=0, str=s2; i<s2len; ) { for(j=0; j<10; ++j) { if(str == strstr(str, sale2[j].chunk)) { i += sale2[j].len; b[s2cnt++] = sale2[j].flag; str = s2+i; break; } } } } else { for(i=0, str=s1; i<s1len; ) { for(j=0; j<10; ++j) { if(str == strstr(str, sale80[j].chunk)) { i += sale80[j].len; a[s1cnt++] = sale80[j].flag; str = s1+i; break; } } } for(i=0,str=s2; i<s2len; ) { for(j=0; j<10; ++j) { if(str == strstr(str, sale80[j].chunk)) { i += sale80[j].len; b[s2cnt++] = sale80[j].flag; str = s2+i; break; } } } } for(i=0, j=s1cnt-1; i<j; ++i, --j) {temp = a[i]; a[i] = a[j]; a[j] = temp;} for(i=0, j=s2cnt-1; i<j; ++i, --j) {temp = b[i]; b[i] = b[j]; b[j] = temp;} // for(i=0; i<s1cnt; ++i) {printf("a[%d] = %d\n", i, a[i]);} // for(i=0; i<s2cnt; ++i) {printf("b[%d] = %d\n", i, b[i]);} len = s1cnt<s2cnt ? s1cnt:s2cnt; for(i=0, e=0; i<len; ++i) { temp = (e + a[i] + b[i]); sum[i] = temp%10; e = temp/10; } if(i < s1cnt) while(i != s1cnt) { temp = e + a[i] + sum[i]; sum[i] = temp%10; e = temp/10; i++; } else while(i != s2cnt) { temp = e + b[i] + sum[i]; sum[i] = temp%10; e = temp/10; i++; } for(; i<20 && e; ++i) { temp = e + sum[i]; sum[i] = temp%10; e = temp/10; } for(i=20-1; i>0 && !sum[i]; --i); for(; i>=0; --i) { // printf("%d", sum[i]); if(sel == 2) printf("%s", sale2[sum[i]].chunk); else { if(sum[i]>=6)printf("%s", sale80[sum[i]].chunk); else printf("%s", sale80[5 - sum[i]].chunk); } } printf("\n"); } return 0; }
解题报告：
将摩斯密码中的字元转成数字进行运算，然后再进行转换输出，在80米波段中要注意比较的先后顺序！代码有点长，AC后必须看标程才行。
不知为啥，还是用上了高精度加法，题目明明提示了用long long，再结合strstr函数，结果就出来了。
花了点时间，在考虑当中为什么会出现这种情况，思路清晰，但实现确是另外一回事，！！！！！！！！
===========================================================================
《算法竞赛入门经典》（刘汝佳）里有这样一段话：
在实际编程中，我们经常先编写一个具备主要功能的程序，再加以完善，我们甚至可以先写一个只有输入输出功能的“骨架”，但要确保它
正确，这样，每次只添加一点点小功能，而且写一点就测试一点，和一次写完整个程序相比，更加不容易出错。这种方法称为：迭代式开发！！
一开始在初始化结构体时，曾因直接赋值导致错误，然后不得不进行大篇幅更改，类似的代码更加如此，比如下面的两个if-else，因为一开始
代码复制更改，结构基本一致，但后来DEBUDGE的时候发现出了点差错，同样不得不进行大篇幅更改，这样浪费了不少不必要的时间。这点尤为重要！
还有就是思维必须要再严谨一点，不然到最后还是会一摊BUG，难以收拾！
Classic Code
#include<stdio.h> #include<string.h> int main() { int t,kind,i,q,p,k,an,j,ju,y; long long sum,e; char a[2][100],b[20][15]; scanf("%d",&t); for(i=0;i<t;i++) { sum=0; scanf("%d",&kind); getchar(); gets(a[0]); gets(a[1]); for(q=0;q<2;q++) { e=1; for(p=strlen(a[q])-1;p>=0;) { k=0; if(kind==2) { for(j=p;j>p-5;j--) if(a[q][j]=='.') k++; p=j; if(k&&a[q][j+1]=='-') k=10-k; } else { ju=0; for(j=p;j>p-9&&j>=0;j--) { if(a[q][j]==' ') {ju=1;break;} if(a[q][j]=='.'&&j>p-5)k++; } if(ju)p=j-3; else {p=p-5;if(k)k=10-k;} } sum=sum+k*e; e=e*10; } } for(y=0;sum;y++) { an=sum%10; if(an>5||an==0) switch(an) { case 0:strcpy(b[y],"-----");break; case 6:strcpy(b[y],"-....");break; case 7:strcpy(b[y],"--...");break; case 8:strcpy(b[y],"---..");break; case 9:strcpy(b[y],"----.");break; default:break; } else { if(kind==2) { switch(an) { case 1:strcpy(b[y],".----");break; case 2:strcpy(b[y],"..---");break; case 3:strcpy(b[y],"...--");break; case 4:strcpy(b[y],"....-");break; case 5:strcpy(b[y],".....");break; default:break; } } else { switch(an) { case 1:strcpy(b[y],"-- ---.");break; case 2:strcpy(b[y],"-- ---..");break; case 3:strcpy(b[y],"-- ---...");break; case 4:strcpy(b[y],"-- ---....");break; case 5:strcpy(b[y],"-- ---.....");break; default:break; } } } sum=sum/10; } for(y--;y>=0;y--)printf("%s",b[y]); printf("\n"); } return 0; }
