首页 > 其他 > 详细

BZOJ 5000: OI树

时间:2018-05-20 17:51:43      阅读:31      评论:0      收藏:0      [点我收藏+]

标签:记录   bre   style   第一个   print   英文   ID   desc   content   

技术分享图片

这baozha的AC率。

Description

几天之后小跳蚤即将结束自己在lydsy星球上的旅行。这时,lydsy人却发现他们的超空间传送装置的能量早在小跳
蚤通过石板来到lydsy星球时就已经消耗光了。这时,小跳蚤了解到自己很有可能回不到跳蚤国了,于是掉下了伤
心的眼泪……lydsy人见状决定无论如何也要送小跳蚤回地球,于是lydsy人的大祭司lavendir决定拜访lydsy星球
的OI树,用咒语从OI树中取得能量。咒语中有K种字母,我们用前K个大写英文字母来表示它。OI树可以被认为是一
个有着N个节点的带权有向图,所有节点的出度都是K,并且所有的出边都对应于一个咒语中的字母。仪式开始的时
候有一个标记物放在OI树的1号节点上。之后,从咒语的第一个字母开始,每经过一个字母,标记物就沿着该字母
对应的出边进入这条边的终点,并且得到相当于边权大小的能量值。当咒语处理完毕时,就可以得到这个过程中得
到的所有能量了。现在由于lydsy人超群的计算能力,他们已经知道某咒语大概会获得多少能量,只是还想知道会
获得的能量值对一个数M取模的结果。跳蚤国王通过小跳蚤留下的石板也了解到了小跳蚤现在的处境,所以他又找
到了你,希望你帮助他计算出这个问题的答案。
 

 

Input

第一行是两个空格分隔的整数N和K。
之后N行每行2*K个整数A_1,B_1,A_2,B_2,...,A_K,B_K,表示N个节点的K条出边。
第i行表示第 i-1 个节点,这一行的A_S,B_S的值表示第S个大写字母对应的出边的终点为A_S,权值为B_S。
下面一行有一个字符串,表示咒语。
由于咒语的长度会非常长,将采用压缩方式给出,用[SA]表示连续S个字母A,S是一个正整数,A是单个字母。
比如说,字符串[5A]BC[3A][3C]表示的咒语为AAAAABCAAACCC。
之后一个正整数M,表示取模的底数。
字符串长度≤120000,在一个压缩节[SA]中,S≤10^9。K≤26,N≤10000,M≤10^9,所有边的权值小于10^9
 

 

Output

一个整数,表示问题的答案。
 

 

Sample Input

4 2
3 3 2 5
1 7 3 2
4 3 2 5
2 10 3 2
[3A]B[2A][2B]
10000

Sample Output

38
 
 
//emm...
//因为每个点往哪儿走是由咒语确定了的
//所以我们可以用倍增来做 
//数据范围N<=1e4,K<=26
//可以开一个数组energy[10005][27][15]来记录第i个点从第j个字母往下走j步得到的能量
//dest[][][]记录到达的点 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e4+5;
const int M=12e4+5;

inline int read()
{
    char c=getchar();int num=0,f=1;
    for(;!isdigit(c);c=getchar())
        f=c==-?-1:f;
    for(;isdigit(c);c=getchar())
        num=num*10+c-0;
    return num*f;
}

int n,k,mod,ans;
int energy[N][27][31];
int dest[N][27][31];
char s[M];

inline void work(int &pos,int let,int step)
{
    for(int i=30;i>=0;--i)
    {
        if(step&(1<<i))
        {
            ans+=energy[pos][let][i];
            ans%=mod;
            pos=dest[pos][let][i];
        }
    }
}

int main()
{
    n=read(),k=read();
    for(int i=1;i<=n;++i)
        for(int j=0;j<k;++j)
        {
            dest[i][j][0]=read(),
            energy[i][j][0]=read();
        }
    scanf("%s",s);
    mod=read();
    for(int j=1;j<=30;++j)
        for(int a=1;a<=n;++a)
            for(int i=0;i<k;++i)
            {
                dest[a][i][j]=dest[dest[a][i][j-1]][i][j-1];
                if(!dest[a][i][j])
                    break;
                energy[a][i][j]=energy[a][i][j-1]+energy[dest[a][i][j-1]][i][j-1];
                energy[a][i][j]%=mod;
            }
//    printf("%d\n",energy[1][0][2]+energy[1][0][0]);
    int len=strlen(s);
    for(int i=0,cnt=0,pos=1;i<len;++i)
    {
        if(s[i]==[||s[i]==])
            cnt=0;
        else if(isdigit(s[i]))
            cnt=cnt*10+s[i]-0;
        else
            work(pos,s[i]-A,cnt?cnt:1);
    }
    printf("%d",ans);
    return 0;
}
/*
4 2
3 3 2 5
1 7 3 2
4 3 2 5
2 10 3 2
[3A]B[2A][2B]
10000
*/

 

BZOJ 5000: OI树

标签:记录   bre   style   第一个   print   英文   ID   desc   content   

原文:https://www.cnblogs.com/lovewhy/p/9063827.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号