【问题描述】
吕弗·普自小从英国长大,受到骑士精神的影响,吕弗·普的梦想便是成为一位劫富济贫的骑士。
吕弗·普拿到了一份全国富豪的名单(不在名单上的都是穷人),上面写着所有富豪的名字以及他们的总资产,比如豪特斯·珀去年资产有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");
}
}