【FZU2280】Magic
2024-08-29 00:04:49
题意
给出n个字符串,每个字符串有一个权值wi 有q个操作,操作有两种 1 x y 将字符串x的权值变为y 2 x 查询操作,输出以字符串x为后缀,且权值小于等于wx的字符串个数。其中n<=1000 每个字符串长度<=1000 询问q<=80000。
分析
n并不大,但是q太大了。如果暴力的话,每次查询都是o(n*len)的,肯定不行。
等等,谁说不行?我试试 emmm。。。爆过去了????下面是瞎几把爆的代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std;
const int maxn=+;
int len[maxn],w[maxn];
char s[maxn][maxn];
int T,n,q; int main(){
scanf("%d",&T);
for(int t=;t<=T;t++){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s",s[i]);
scanf("%d",&w[i]);
len[i]=strlen(s[i]);
}
scanf("%d",&q);
int opt;
for(int i=;i<=q;i++){
scanf("%d",&opt);
if(opt==){
int x,y;
scanf("%d%d",&x,&y);
w[x]=y;
}else if(opt==){
int x;
scanf("%d",&x);
int ans=;
for(int j=;j<=n;j++){
if(w[j]>w[x])continue;
if(len[j]<len[x])continue;
bool ok=;
for(int k=len[j]-,l=len[x]-;l>=;k--,l--){
if(s[x][l]!=s[j][k]){
ok=;
break;
}
}
if(ok){
ans++;
// cout<<j<<endl;
}
}
printf("%d\n",ans);
}
}
}
return ;
}
好吧好吧,上面那个不算,我们重新来想···
后缀嘛,后缀数组?咳,我就知道名字而已不会。。想点会的。。
字典树行不行?我们只要把字符串倒着插进去就可以用统计前缀的方法来统计后缀了。
w这个限制怎么办?
我们在字典树上每一个字符串结尾维护一个vector···这样··时间复杂度是多少?均摊下应该是···可以的···吧?
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int maxn=+;
int ch[maxn*maxn][],W[maxn];
char s[maxn][maxn];
int val[maxn*maxn];
vector<int>G[maxn*maxn];
int T,n,q,sz;
void insert(char *s,int w){
int len=strlen(s);
int u=;
for(int i=;i<len;i++){
int id=s[i]-'a';
if(!ch[u][id]){
ch[u][id]=++sz;
}
u=ch[u][id];
}
G[u].push_back(w);
return ;
}
void tra(int u){
/* if(G[u].size()!=0){
for(int i=0;i<G[u].size();i++){
printf("%d ",G[u][i]);
}
return;
}*/
for(int i=;i<;i++){
if(ch[u][i]){
printf("%c",i+'a');
tra(ch[u][i]);
}
}
return;
}
int ans;
void check(int u,int k){
if(G[u].size()){
for(int i=;i<G[u].size();i++){
if(W[G[u][i]]<=W[k]){
ans++;
}
}
}
for(int i=;i<;i++){
if(ch[u][i])
check(ch[u][i],k);
}
return;
}
void solve(int k){
int u=;
ans=;
for(int i=strlen(s[k])-;i>=;i--){
int id=s[k][i]-'a';
if(!ch[u][id]){
return ;
}
u=ch[u][id];
}
check(u,k);
return ;
}
int main(){
scanf("%d",&T);
for(int t=;t<=T;t++){
scanf("%d",&n);
for(int i=;i<=*;i++)G[i].clear();
memset(val,,sizeof(val));
memset(ch,,sizeof(ch));
sz=;
char s1[maxn];
int x;
for(int i=;i<=n;i++){
scanf("%s%d",s[i],&W[i]);
for(int j=;j<strlen(s[i]);j++){
s1[j]=s[i][strlen(s[i])--j];
}
s1[strlen(s[i])]='\0';
insert(s1,i);
}
// tra(0); scanf("%d",&q);
for(int i=;i<=q;i++){
int opt;
scanf("%d",&opt);
if(opt==){
int x,y;
scanf("%d%d",&x,&y);
W[x]=y;
}else if(opt==){
int x;
scanf("%d",&x);
solve(x);
printf("%d\n",ans);
}
}
}
return ;
}
最新文章
- 使用cmake自动构建工程
- C# 实现 Excel文件的数据导入
- Excel VBA自动添加证书(二)
- git clone简介
- Android弱网测试中关于网络检测的一些借鉴方法
- lines---hdu5124(离散化+数组模拟)
- UVALive 7456	Least Crucial Node (并查集)
- POJ3026——Borg Maze(BFS+最小生成树)
- Android关机流程源码分析
- Android实现渐显按钮的左右滑动效果
- Flex 各种校验
- win7自动关机方法
- 在IDEA中设置命令行参数
- 关于java前端入门的一些简单的看法
- ant jmeter 优化报告
- vue-router 懒加载优化
- Java——poi读取Excel文件
- cc1: warnings being treated as errors解决办法
- windows上使用clang编译程序
- c# 数据库通用类DbUtility