计蒜客NOIP模拟赛(2) D2T1 劫富济贫

【问题描述】

吕弗·普自小从英国长大,受到骑士精神的影响,吕弗·普的梦想便是成为一位劫富济贫的骑士。

吕弗·普拿到了一份全国富豪的名单(不在名单上的都是穷人),上面写着所有富豪的名字以及他们的总资产,比如豪特斯·珀去年资产有86E,吕弗·普就会准备抢来资助贫困的伯恩兄弟……

现在吕弗·普做了M次打劫计划,每次要打劫若干个人,他想知道每次能打劫到的总资产是多少

【输入格式】

第一行一个正整数N,代表富豪的个数

接下来N行,每行一个由小写字母组成的字符串Si和一个非负整数Wi,分别代表第i个富豪的名字和第i个富豪的资产数量

然后一个正整数M,代表吕弗·普的打劫次数

接下来M行,每行第一个数为正整数Xi,代表这次要打劫Xi个人,接下来有X个字符串,说明了这Xi个人是谁

【输出格式】

对于每次打劫任务,输出一行一个整数表示打劫到的总资产

如果这次打劫任务中打劫了一个穷人,那就输出-1

【样例输入】

2

a 10

b 20

3

2 a b

1 b

2 a c

【样例输出】

30

20

-1

【数据范围与约定】

对于30%
的数据,输入中每个名字的长度均为1

对于60%
的数据,N,∑Xi<=
100,输入中每个名字的长度<=10

对于100%的数据,N,∑Xi<=
10^5,输入中所有名字的总长度<=2*10^6,Wi<=10^9,保证任意两个富豪名字不同,但不保证打劫计划中会不会有重复的人

字典树裸题

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long lol;
int tot=;
char s[];
int ch[][],n,m;
lol w[],ans;
void add(lol d)
{int i;
int l=strlen(s);
int now=;
for (i=;i<l;i++)
{
int x=s[i]-'a';
if (!ch[now][x])
{
ch[now][x]=++tot;
w[tot]=-;
}
now=ch[now][x];
}
w[now]=d;
}
lol find()
{int i;
int l=strlen(s);
int now=;
for (i=;i<l;i++)
{
int x=s[i]-'a';
now=ch[now][x];
}
return w[now];
}
int main()
{lol d,k,x;
int i,j;
cin>>n;
w[]=-;
for (i=;i<=n;i++)
{
scanf("%s%lld",s,&d);
add(d);
}
cin>>m;
for (i=;i<=m;i++)
{
scanf("%lld",&k);
bool flag=;
ans=;
for (j=;j<=k;j++)
{
scanf("%s",s);
x=find();
if (x==-)
{
flag=;
break;
}
else ans+=x;
}
if (flag) printf("%lld\n",ans);
else printf("-1\n");
}
}
上一篇:Entity Framework技巧系列之十二 - Tip 46 - 50


下一篇:【NOIP2014模拟赛No.1】我要的幸福