设为首页 加入收藏

TOP

hdu 4601 Letter Tree 2013多校1-2
2015-07-20 18:05:02 来源: 作者: 【大 中 小】 浏览:2次
Tags：hdu 4601 Letter Tree 2013 多校 1-2

?

最后是对拍代码找到的错误，发现当步数比较小的时候答案就是对的，比较大的时候就不对了

想到一定是什么地方越界了。。。

power[i] = (i64)(power[i - 1] * 26) % mod;

就是这行。。。

改成 power[i] = ((i64)power[i - 1] * 26) % mod;

就过了。。。

这道题总的来说就是非常综合，什么方面都涉及一点，核心部分还是把树转化成序列之后二分边界+RMQ,用dfn来确定边界的这个方法非常好，很有意思

其实还有一种方法，就是先从u节点往下走一步，然后在trie里面找，这个时候可以直接确定位置，因为在trie中已经是有序的了

两种都可以，第一种相对来说好实现一点

（hdu现在怎么不会爆栈了。。）

?

//#pragma comment(linker, /STACK:102400000,102400000)
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                using namespace std; #ifdef _WIN32 typedef __int64 i64; #define out64 %I64d #define in64 %I64d #else typedef long long i64; #define out64 %lld #define in64 %lld #endif /************ for topcoder by zz1215 *******************/ #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) #define FOR(i,a,b) for( int i = (a) ; i <= (b) ; i ++) #define FF(i,a) for( int i = 0 ; i < (a) ; i ++) #define FFD(i,a,b) for( int i = (a) ; i >= (b) ; i --) #define S64(a) scanf(in64,&a) #define SS(a) scanf(%d,&a) #define LL(a) ((a)<<1) #define RR(a) (((a)<<1)+1) #define pb push_back #define pf push_front #define X first #define Y second #define CL(Q) while(!Q.empty())Q.pop() #define MM(name,what) memset(name,what,sizeof(name)) #define MC(a,b) memcpy(a,b,sizeof(b)) #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)<(b)?(a):(b)) #define read freopen(out.txt,r,stdin) #define write freopen(out1.txt,w,stdout) const int inf = 0x3f3f3f3f; const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL; const double oo = 10e9; const double eps = 10e-9; const double pi = acos(-1.0); const int mod = 1000000007; const int maxn = 100111; struct Node { int now; int to; int c; }; struct Trie { int to[26]; int rank; }zx[maxn]; int head = 0; int use; int get() { use++; MM(zx[use].to, -1); zx[use].rank = 0; return use; } int T; int n, m; vector
               
                g[maxn]; vector
                
                 level[maxn]; int dep[maxn]; int dfn[maxn]; int dfv[maxn]; int df; int power[maxn]; int vis[maxn]; int t[maxn]; int pos[maxn]; int pmod[maxn]; int rankmod[maxn]; int rk; int c[maxn]; int dfnpos[maxn]; int es[maxn][2]; vector
                 
                  ary; int st[maxn][20]; int pow2[20]; int lg2[maxn]; void dfs(int now=1,int step=0) { vis[now] = true; int to; dfn[now] = df; dfv[df] = now; df++; dep[now] = step; for (int i = 0; i <(int) g[now].size(); i++) { to = g[now][i].to; if (!vis[to]) { t[to] = now; c[to] = g[now][i].c; dfs(to,step+1); } } } void make_trie() { use = -1; get(); int trie = head; int now = 1; pos[now] = trie; int to,temp; pmod[0] = 0; for (int i = 2; i < df; i++) { to = dfv[i]; now = t[to]; trie = pos[now]; if (zx[trie].to[c[to]] == -1) { temp = get(); zx[trie].to[c[to]] = temp; pmod[temp] = ((i64)pmod[trie] * 26 + c[to]) % mod; } pos[to] = zx[trie].to[c[to]]; } } void make_rank(int now = head) { zx[now].rank = rk++; for (int i = 0; i < 26; i++) { if (zx[now].to[i] != -1) { make_rank(zx[now].to[i]); } } } void sparsetable() { for (int i = 1; i <= n; i++) { st[i][0] = zx[pos[dfv[ary[i]]]].rank; } for (int j = 1; j <= lg2[n]; j++) { for (int i = 1; i <= n; i++) { if (i + pow2[j - 1] <= n) { st[i][j] = max(st[i][j - 1], st[i + pow2[j - 1]][j - 1]); } else { st[i][j] = st[i][j - 1]; } } } } int rmq(int l,int r) { return max(st[l][lg2[r - l]], st[r - pow2[lg2[r - l]]][lg2[r - l]]); } int find(int x, int step) { int low = dfn[x]; int up; int temp = dfnpos[dfn[x]] + 1; step += dep[x]; int l, r; if (temp < es[dep[x]][1]) { up = ary[temp]; } else { up = inf; } l = upper_bound (ary.begin() + es[step][0], ary.begin() + es[step][1], low ) - ary.begin(); r = upper_bound (ary.begin() + es[step][0], ary.begin() + es[step][1], up ) - ary.begin(); if (l == r) { return -1; } int mrank = rmq(l, r); int xrank = zx[pos[x]].rank; return (((i64)rankmod[mrank] - ((i64)rankmod[xrank] * (i64)power[step - dep[x]])%mod)+mod)%mod; } void start() { for (int i = 0; i <= n; i++) { vis[i] = false; } t[1] = -1; df = 1; dfs(); for (int i = 1; i <= n; i++) { level[dep[i]].push_back(dfn[i]); } for (int i = 1; i <= n; i++) { sort(level[i].begin(), level[i].end()); } ary.clear(); ary.push_back(0); for (int i = 0; i <= n; i++) { es[i][0] = ary.size(); for (int j = 0; j < (int)level[i].size(); j++) { ary.push_back(level[i][j]); } es[i][1] = ary.size(); } for (int i = 1; i <= n; i++) { dfnpos[ary[i]] = i; } make_trie(); rk = 0; make_rank(); for (int i = 0; i <= use; i++) { rankmod[zx[i].rank] = pmod[i]; } sparsetable(); } void destroy() { for (int i = 0; i <= n; i++) { g[i].clear(); level[i].clear(); } } int main() { //read; //write; power[0] = 1; for (int i = 1; i < maxn; i++) { power[i] = ((i64)power[i - 1] * 26) % mod; } pow2[0] = 1; lg2[1] = 0; for (int i = 1; i < 20; i++) { pow2[i] = pow2[i - 1] * 2; if(pow2[i]
                  
                   > T; while (T--) { cin >> n; int x, y; char z; Node node; for (int i = 1; i <= n - 1; i++) { //cin >> x >> y >> z; scanf(%d%d %c, &x, &y, &z); node.now = x; node.to = y; node.c = z - 'a'; g[node.now].push_back(node); swap(node.now, node.to); g[node.now].push_back(node); } start(); cin >> m; for (int i = 1; i <= m; i++) { // cin >> x >> y; scanf(%d%d, &x, &y); if (y == 0) { printf(0 ); continue; } int ans = find(x, y); if (ans == -1) { // cout << IMPOSSIBLE << endl; printf(IMPOSSIBLE ); } else { // cout << ans << endl; printf(%d ,ans); } } destroy(); } return 0; }


?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：汇编入门学习笔记 （十二）―― i.. 下一篇：HDU 4821 String 字符串哈希

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: