bjfu---fudq and IME Again

2024-01-21 10:48

文章标签 ime bjfu fudq

本文主要是介绍bjfu---fudq and IME Again，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

fudq and IME Again

时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:6 测试通过:4

描述

fudq发现现代的人越来越离不开两样东西，一样是电脑，一样是手机，尤其是手机，很多人几乎都是机不离身。fudq发现用手机输单词也是件有趣的事情。手机键盘数字键和字母对应关系如下：
2 : a, b, c 3 : d, e, f 4 : g, h, i 5 : j, k, l 6 : m, n, o
7 : p, q, r, s 8 : t, u, v 9 : w, x, y, z
当输入单词“fudq”的时候，我们依次按下数字键3,8,3,7，然后系统就会从自带的字典里筛选出可能的单词，如“dtfp”,"dues","evfr"等等。于是fudq产生了疑问，给出系统字典库，然后给出一串手机按键数字，fudq想知道有多少个符合条件的单词。

输入

输入第一行是一个正整数T(1<=T<=20)，表示接下来有T组测试数据。
接下来有T组数据，每组数据首先包含两个正整数N和M。1<=N<=10000,1<=M<=10000.
接下来有N行，表示输入的N个手机数字串，每行代表一个，长度不超过6.
接下来有M行，表示字典库里的M个单词，每行一个单词，长度不超过6.
保证不会有重复的手机数字串，也不会有重复的单词。

输出

每组数据输出N个整数，每个数对应N个手机数字串，表示有多少个单词符合该手机数字串。

样例输入

1
3 6
49
3837
86
gy
to
fudq
dues
ga
acm

样例输出

1
2
1

//只能说不淡定了..字符串排序搞了N久.. 才发现之前是对的.. 想多了...

//n最大为10000，题目最后提示说数据加强了，最后进行了预处理+二分。该数量级为 nlog(n)。其他就是模拟了..

代码：

#include<stdio.h>
#include<string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
#define N 10010
typedef struct{
char str[11];
int num;
}LNode;
LNode f[N],f1[N],f2[N];
char zhuan(char x){
if(x>='a' && x<='c') return '2';
if(x>='d' && x<='f') return '3';
if(x>='g' && x<='i') return '4';
if(x>='j' && x<='l') return '5';
if(x>='m' && x<='o') return '6';
if(x>='p' && x<='s') return '7';
if(x>='t' && x<='v') return '8';
if(x>='w' && x<='z') return '9';
}
int cmp(const void *a,const void *b){
return strcmp((*(LNode*)a).str,(*(LNode*)b).str);
}
int main()
{
int T,n,m,i,j,k,t;
scanf("%d",&T);
while(T--){
char a[11];
scanf("%d %d",&n,&m);
for(i=0;i<n;i++) scanf("%s",f1[i].str);
k=0;
for(i=0;i<m;i++){
scanf("%s",a);
int len=strlen(a);
for(j=0;j<len;j++)
a[j]=zhuan(a[j]);
strcpy(f2[k++].str,a);
}
int kk=120;
qsort(f2,m,sizeof(f2[0]),cmp);;//排序之后，进行整合预处理；
int num=1;j=0;
for(i=1;i<k;i++){
if(strcmp(f2[i].str,f2[i-1].str)==0) num++;
else{
strcpy(f[j].str,f2[i-1].str);
f[j++].num=num;
num=1;
}
}
if(strcmp(f2[i-1].str,f2[i-2].str)!=0){
strcpy(f[j].str,f2[i-1].str);
f[j++].num=num;
}//加上最后一位。 一共j种情况。
for(i=0;i<n;i++){
int start=0,last=j-1,mid;mid=(start+last)/2;
k=-1;int flag;
while(start<=last){
flag=strcmp(f[mid].str,f1[i].str);
if(flag==0){k=mid;break;}
else{
if(flag>0){last=mid-1;mid=(start+last)/2;}
else{start=mid+1;mid=(start+last)/2;}
}
}
if(k==-1) printf("0\n");
else{printf("%d\n",f[mid].num);}
}
}
//system("pause");
return 0;
}