第八届福建省大学生程序设计竞赛 | FZU2280 Magic
第八届福建省大学生程序设计竞赛 | FZU2280 Magic
FZU2280 Magic-字典树+树状数组或Hash+预处理
Problem Description
Kim is a magician, he can use n kinds of magic, number from 1 to n. We use string Si to describe magic i. Magic Si will make Wi points of damage. Note that Wi may change over time.
Kim是魔术师，他可以使用n种魔法，数字从1到n。 我们使用字符串Si来描述魔法i。魔法Si将造成Wi点伤害。 请注意，Wi可能会随时间而变化。
Kim obey the following rules to use magic:
Kim遵守以下规则来使用魔法：
Each turn, he picks out one magic, suppose that is magic Sk, then Kim will use all the magic i satisfying the following condition:
每回合，他挑出一个魔法，假设那是魔法Sk，那么Kim将使用所有魔法我满足以下条件：
1. Wi<=Wk
2. Sk is a suffix of Si.
Sk是Si的后缀。
Now Kim wondering how many magic will he use each turn.
现在Kim想知道他每回合会使用多少魔法。
Note that all the strings are considered as a suffix of itself.
请注意，所有字符串都被视为自身的后缀。
Input
First line the number of test case T. (T<=6)
For each case, first line an integer n (1<=n<=1000) stand for the number of magic.
Next n lines, each line a string Si (Length of Si<=1000) and an integer Wi (1<=Wi<=1000), stand for magic i and it’s damage Wi.
Next line an integer Q (1<=Q<=80000), stand for there are Q operations. There are two kinds of operation.
“1 x y” means Wx is changed to y.
“2 x” means Kim has picked out magic x, and you should tell him how many magic he will use in this turn.
Note that different Si can be the same.
Output
For each query, output the answer.
Sample Input
1 5 abracadabra 2 adbra 1 bra 3 abr 3 br 2 5 2 3 2 5 1 2 5 2 3 2 2
Sample Output
3 1 2 1
题意：
给你n个字符串且有权值wi。两种操作：1. 修改单个字符串的权值，2. 询问有多少个字符串有第k个字符串为后缀且其权值小于等于第k个字符串的权值。
思路
解法一：Hash+预处理
- 首先预处理出每个字符串的hash。然后n个桶，第i个桶装有第i个字符串为后缀的字符串编号。
- (可能有点绕，不过自己思考一下很好理解的)
- 对于第二个操作，每次暴力查询这个第k个桶有多少字符串的权值小于第k个字符串的权值。
- 后缀的话hash的时候倒着hash取值就行了。看代码很好理解的。
解法二：字典树+树状数组
- 维护n个bit数组(其实是对每种字符串维护一个bit数组)，存有此字符串为后缀的字符串的权值位置（权值树状数组？？？
- 然后加入字典树的时候一定一定要从长度短的开始insert，字符串要倒着插入。
- 在插入的时候顺便更新bit数组。
- 操作一看代码比较容易理解。
- 操作二：查询第k个字符串的bit数组小于等于wk的个数。(wk是它的权值)
- 可能会有重复的字符串，对每种字符串统一一个标号，如代码中的End[]数组。
- 感觉挺巧妙的，体会体会把，欢迎提问。
AC代码，2种解法：
Hash解法
#include<cstdio>
#include<cstring>
#include <vector>
#include<algorithm>
#define lowbit(x) (x)&(-(x))
#define lson rt<<1
#define rson rt<<1|1
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int N = 1000+7;
const int MX = 1000+7;
const int MAXM = 3e5+7;
const uLL base = 99959;
const int MOD = 1000000007;
char ar[N][N];
int w[N], n, Len[N];
vector<int> son[N];//n个桶
uLL hs[N][N], pw[N];
void HASH(){//预处理每个字符串的hash值，uLL自然溢出
pw[0]=1;
for(int i=0;i<=1000;++i)pw[i]=pw[i-1]*base;
for(int i=1;i<=n;++i){
hs[i][0]=0;int len = Len[i];
for(int j = 1; j <= len; ++j){
hs[i][j]=(hs[i][j-1]*base+ar[i][len+1-j]-'a');
}
}
}
LL get(int k,int l,int r){//求第k个字符串l到r的hash值
return (hs[k][r] - hs[k][l-1]*pw[r-l+1]);
}
void init(){//预处理每个桶
for(int i = 1; i <= n; ++i){
son[i].push_back(i);
for(int j = i + 1; j <= n; ++j){
if(Len[i] == Len[j]&&hs[i][Len[i]] == hs[j][Len[j]]){
son[i].push_back(j);
son[j].push_back(i);
}else if(Len[i] > Len[j]&&hs[j][Len[j]]==get(i,1,Len[j])){
son[j].push_back(i);
}else if(Len[j]>Len[i]&&hs[i][Len[i]]==get(j,1,Len[i])){
son[i].push_back(j);
}
}
}
}
int main(){
int tim;
scanf("%d", &tim);
while(tim--){
scanf("%d", &n);
for(int i=1, u; i <= n; ++i){
son[i].clear();
scanf("%s%d", ar[i]+1, &u);
w[i] = u;Len[i]=strlen(ar[i]+1);
}
HASH();
init();
int m;scanf("%d", &m);
while(m--){
int op,x,y;
scanf("%d%d",&op, &x);
if(op==1){
scanf("%d",&y);
w[x] = y;
}else{
int cnt=0;
for(int i=0;i<son[x].size();++i){//暴力查询即可
int v = son[x][i];
if(w[v]<=w[x])cnt++;
}
printf("%d\n", cnt);
}
}
}
return 0;
}字典树解法
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) (x)&(-(x))
#define lson rt<<1
#define rson rt<<1|1
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int N = 1000+7;
const int MX = 1000+7;
const int MXM = 3e5+7;
const int MOD = 1000000007;
char ar[N][N];
int w[N], id[N*10], n, bit[N][N];
int Len[N],End[N];
struct lp{
int id, len;
}cw[N];
struct node{
int nex[26];
void init(){
memset(nex,-1,sizeof(nex));
}
}tr[MX*10];
int le, root;
void add(int k,int x,int c){
while(x <= 1000){
bit[k][x] += c;x += lowbit(x);
}
}
int query(int k,int x){
int sum = 0;
while(x){
sum += bit[k][x];x -= lowbit(x);
}
return sum;
}
void insert(int k, char *s,int slen){
int now = root;
for(int i = slen - 1; i >= 0; --i){
int x = s[i] - 'a';
if(tr[now].nex[x] == -1){
tr[le].init();
tr[now].nex[x] = le++;
}
now = tr[now].nex[x];
if(id[now]){//id[now]这个字符串是k的后缀
add(id[now], w[k], 1);
}
}
if(!id[now]){//新字符串？？加！
id[now] = k;
add(k, w[k], 1);
}
End[k]=id[now];//同样的字符串统一一个编号咯
}
void update(int k, char *s, int v,int slen){//操作一修改权值
int now = root;
for(int i = slen - 1;i >= 0; --i){
int x = s[i] - 'a';
now = tr[now].nex[x];
if(id[now]){//相当于换一个权值嘛！！对吧
add(id[now], w[k], -1);
add(id[now], v, 1);
}
}
w[k] = v;
}
bool cmp(const lp &a, const lp &b){
return a.len < b.len;
}
void Trie_dele(){
for(int i = 1; i < N; ++i){
tr[i].init();
}
}
int main(){
int tim;
scanf("%d", &tim);
while(tim--){
scanf("%d", &n);
root = 0;le = 1;tr[0].init();
mme(id, 0);mme(bit, 0);
for(int i=1, u; i <= n; ++i){
scanf("%s%d", ar[i], &u);
cw[i].id = i; cw[i].len = strlen(ar[i]);
w[i] = u;Len[i] = cw[i].len;
}
sort(cw+1,cw+n+1,cmp);
for(int i = 1; i <= n; ++i){//按长度插入
insert(cw[i].id,ar[cw[i].id],cw[i].len);
}
int m;
scanf("%d", &m);
while(m--){
int op, k, v;;scanf("%d", &op);
if(op == 1){
scanf("%d%d", &k, &v);
update(k, ar[k], v, Len[k]);
}else{
scanf("%d", &k);
printf("%d\n", query(End[k], w[k]));
}
}
Trie_dele();
}
return 0;
}谢谢阅读。