loneliness

ShinriiTin posted @ 2015年6月17日 18:03 in 未分类 with tags 某不科学的三千元系列 , 926 阅读

题意:

给出一棵以1为根的有向树，每个节点上有一个字符(只会是小写字母)。

多次询问，给出一个字符集合，要求统计树上合法的串的数量。

合法的串满足4个要求:

1.是树上某个点向根方向的走所形成的串

2.串中所有的字符来自给定的字符集合

3.给定的字符集合中的每一个字符都在串中出现过

4.没有被任意一个满足前三条条件的路径完全包含

树的节点数和询问次数均不超过10⁵

分析:

如果一个路径合法的串，当且仅当该路径向两端延伸1个位置都不能有在路径出现的字符。

我们记录每个节点向根方向的最近的出现某个字符的节点，显然合法的串只可能出现在这条路径上。

再记录每个节点所有儿子的字符集合，对于每个节点按深度枚举要走到的字符，判断是否合法。

My Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113	`#include <stdio.h>` `#include <string.h>` `#include <algorithm>` `using` `namespace` `std;` `#define g() getchar()` `template<class` `Q>inline` `void` `Scan(Q&x){` `char` `c;` `while(c=g(),c<48\|\|c>57);` `for(x=0;c>47&&c<58;c=g())x=10*x+c-48;` `}` `#define rep(i,a,b) for(int i=a;i<b;++i)` `const` `int` `MAXN=50005;` `const` `int` `Alpha=26;` `typedef` `long` `long` `ll;` `struct` `edge{` `int` `t,n;` `edge(int` `t=0,int` `n=0):t(t),n(n){}` `}e[MAXN<<1];` `int` `head[MAXN],tot;` `inline` `void` `AddEdge(int` `s,int` `t){` `e[++tot]=edge(t,head[s]),head[s]=tot;` `e[++tot]=edge(s,head[t]),head[t]=tot;` `}` `char` `a[MAXN],b[MAXN];` `int` `p[MAXN],dep[MAXN];` `int` `last[MAXN][Alpha];` `ll son[MAXN];` `void` `dfs(int` `x){` `rep(i,0,Alpha)` `last[x][i]=last[p[x]][i];` `last[x][a[p[x]]-'a']=p[x];` `for(int` `i=head[x],y;i;i=e[i].n)` `if((y=e[i].t)!=p[x]){` `p[y]=x;` `dep[y]=dep[x]+1;` `son[x]\|=1ll<<(a[y]-'a');` `dfs(y);` `}` `}` `int` `n,m;` `int` `ans[MAXN];` `const` `int` `SIZE=(1<<18)-1;` `struct` `hash{` `ll set[MAXN];` `int` `next[MAXN],id[MAXN];` `int` `head[SIZE+1],tot;` `inline` `void` `insert(ll s,int` `Id){` `int` `p=s&SIZE;` `set[++tot]=s,next[tot]=head[p];` `id[tot]=Id,head[p]=tot;` `}` `inline` `void` `update(ll s){` `int` `p=s&SIZE;` `for(int` `i=head[p];i;i=next[i])` `if(set[i]==s)++ans[id[i]];` `}` `}set;` `inline` `bool` `cmp(int` `a,int` `b){return` `dep[a]>dep[b];}` `inline` `void` `deal(int` `x){` `static` `int` `q[Alpha+1];` `rep(i,0,Alpha)q[i]=last[x][i];` `sort(q,q+Alpha,cmp);` `ll S=1ll<<(a[x]-'a');` `rep(i,0,Alpha){` `if(S&son[x])break;` `if(!q[i])break;` `ll s=1ll<<(a[q[i]]-'a');` `if(!(S&s)){` `set.update(S);` `}` `S\|=s;` `}` `if(S&son[x])return;` `set.update(S);` `}` `int` `main(){` `freopen("loneliness.in","r",stdin);` `freopen("loneliness.out","w",stdout);` `Scan(n),Scan(m);` `scanf("%s",a+1);` `rep(i,1,n){` `int` `u,v;` `Scan(u),Scan(v);` `AddEdge(u,v);` `}` `rep(i,1,m+1){` `ll S=0;` `scanf("%s",b);` `int` `l=strlen(b);` `rep(j,0,l){` `S\|=1ll<<(b[j]-'a');` `}` `set.insert(S,i);` `}` `dep[1]=1,dfs(1);` `rep(i,1,n+1)deal(i);` `rep(i,1,m+1)printf("%d\n",ans[i]);` `return` `0;` `}`

[回复]

Emma 说:
2023年1月24日 01:08

This interesting problem presents a unique challenge in which the user must count the number of legal strings on a directed tree, given a character set. The buy real estate Okatie strings must meet four distinct requirements for them to be considered legal. This task requires the user to have a keen understanding of the tree structure, as well as the character set provided. It's a great mental exercise, and it can be quite rewarding!