题意:衣服的品牌是有字符串表示,ZZ买衣服不喜欢买相同的品牌。(字符串的长度小于20,N,M小于100000)
输入N,M,第一个表示她已经有了N种品牌的衣服,M代表她将要买的品牌衣服。如果以前没有这种品牌的衣服就输出YES,否则就输出NO。
这题真坑了我,我没注意,M输入的品牌要加入她已经买过的品牌,先没注意到这点,直接就想到了二分查找。交上去WA几次了。后来问学长。才知道这回事。
二分查找就行不通了。要用到STL中的map,我开始根本就不知道有这个东西,这是坑我啊。看来还是要多接触的算法啊。
代码如下:(简直水题一个) 我却WA几次了
2013ACM多校联合(4)_NUN -ZZ买衣服
。
time:500ms
#include<cstdio>
#include<cstring>
#include<map>
#include<iterator>
using namespace std;
int main()
{
int n,m;
char t[25];
map<string,int> mp;
map<string,int>::iterator it;
while(~scanf("%d%d",&n,&m))
{
mp.clear();
for(int i=0;i<n;i++)
{
scanf("%s",t);
mp[t]=1;
}
for(int i=0;i<m;i++)
{
scanf("%s",t);
if(mp[t])
printf("NO\n");
else
{
mp[t]=1;
printf("YES\n");
}
}
}
return 0;
}
另外,学长还告诉了我,这题还有另一种方法,并且比上题的效率跟快,就是把字符串转化成十进制数,要体现查的效率高,就必须把大数变小,方法是把所有的数对同一个数取余。
由于,余数存在相同的。但原数不同,我们就必须定义个结构体,一个保存原数,一个保存余数。而要实现插入,效率高的就是链表了,所以,结构体里面还有定义一个
指针(不一定要用指针,它只是可以分配内存),本题开一个链表数组,.处理方法:(hash)把相同的余数存在通一行的链表。所以我们只要找到余数,就找到了行,而且,行很好找,链表表头的对应余数就是该行,对于列,就找原数是否相等就行了。
代码如下:
time:102ms
#include<cstdio>
#include<cstring>
#define mod 200005
using namespace std;
typedef unsigned long long INT;
struct node{
int x,next;
INT m;
}q[200005];
int head[200005];
int idx;
INT count(char *st)
{
int k=strlen(st);
INT sum=0;
for(int i=0;i<k;i++)
{
sum=sum*29+st[i]-'a'+1;
}
return sum;
}
void insert(int x,INT m)
{
q[idx].x=x;q[idx].m=m;
q[idx].next=head[x]; //相同的余数全部放在同一行。
head[x]=idx++; //为链表的表头赋值。
}
void encount(char *st)
{
INT val=count(st);
int x=val%mod;
insert(x,val);
}
bool search(char *st)
{
INT val=count(st);
int k=val%mod;
for(int i=head[k];i!=-1;i=q[i].next)
{
if(q[i].m==val)
return true;
}
return false;
}
int main()
{
char s[25];
int n,m;
while(~scanf("%d%d",&n,&m))
{
idx=0;
memset(head,0xff,sizeof(head));
for(int i=0;i<n;i++)
{
scanf("%s",s);
encount(s);
}
for(int i=0;i<m;i++)
{
scanf("%s",s);
if(search(s))
{
puts("NO");
}
else
{
puts("YES");
encount(s);
}
}
}
return 0;
}