注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

3.5模拟赛(学到hash挂链+贪心AK)  

2014-03-05 21:06:29|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

                    图书管理

图书管理是一件十分繁杂的工作,在一个图书馆中每天都会有许多新书加入。为了更方便的管理图书(以便于帮助想要借书的客人快速查找他们是否有他们所需要的书),我们需要设计一个图书查找系统。

该系统需要支持2种操作

1add(s)  表示新加入一本书名为s的图书。

2find(s)  表示查询是否存在一本书名为s的图书。

 

输入格式

第一行包括一个正整数n(n<=10000),表示操作数。

以下n行,每行给出2种操作中的某一个指令条

指令格式为:

      add s

      find s

在书名s与指令(add,find)之间有一个隔开,我们保证所有书名的长度都不超过200。可以假设读入数据是准确无误的。

 

输出格式

对于每个find(s)指令,我们必须对应的输出一行yesno,表示当前所查询的书是否存在于图书馆内。注意:一开始时图书馆内是没有一本图书的。并且,对于相同字母不同大小写的书名,我们认为它们是不同的。

 

输入样例

4

add Inside C#

find Effective Java

add Effective Java

find Effective Java

 

输出样例

no

yes


此题由于N超大,而比较字符串也要200次,所以暴力时间是:O(N^2*200),必超无疑。于是我们采用了hash,因为总共最多只有10000种不同的情况,于是hash能拿到很可观的分数:我一开始就拿了90分。然后对于如何判重,我们采用了一种挂链的方式:遇到相同hash值的则和它判断是否是相同一个,若不相同则在它的后面接另一个解,用NEXT[K]表示第K个字符串它下面接的是哪一个。

具体代码:inline bool find(int i,int t)

{

int k=Hash[t];

while (k)

{

if (a[k].length()==a[i].length())

{

bool found=1;

for (int j=0;j<a[i].length();j++)

if (a[i][j]!=a[k][j]) {found=0;break;}

if (found) return 1;

}

k=next[k];

}

return 0;

}


inline void Add(int i,int t)

{

if (!Hash[t])

{

Hash[t]=i; return;

} else

{

if (find(i,t)) return;

int k=Hash[t];

while (next[k]) k=next[k];

next[k]=i;

}

}

今天最后一题是贪心算法,本来以为可以骗分的,竟然AK了。其实这就是正解。

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

#define maxn 1005

using namespace std;


int n,m,B;

struct node{int x;int y;}a[maxn];


bool cmp(node a,node b) {return a.x<b.x;}


void init()

{

scanf("%d%d%d",&n,&m,&B);

for (int i=1;i<=n;i++)

{

scanf("%d%d",&a[i].x,&a[i].y);

if (a[i].y) a[i].x=2*m-a[i].x;//一开始将所有在楼道中的邻居到赶到0层。

}

sort(a+1,a+n+1,cmp);//从小到大排序,等会要用到;

}

void work()

{

for (int i=1;i<=n;i++)

a[i].x+=(B/n)*2*m-m;//某个邻居花费的时间:初始+剩余的箱子一个一个运上顶层。

for (int i=1;i<=B%n;i++)

a[i].x+=2*m;//由于还有剩余的,一定让时间用的最小的邻居运送。

int Ans=0;

for (int i=1;i<=n;i++)

if (a[i].x>Ans) Ans=a[i].x;//时间最大的花费便是总用时间。

printf("%d\n",Ans);

}

int main()

{

freopen("stairs.in","r",stdin);

freopen("stairs.out","w",stdout);

int Test;

scanf("%d",&Test);

while (Test)//(x)表示Test>=1;

{

init(); work(); Test--;

}

return 0;

}


  评论这张
 
阅读(44)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018