首页 > ACM题库 > HDU-杭电 > HDU 3856-Palindrome-分治-[解题报告]HOJ
2015
04-13

HDU 3856-Palindrome-分治-[解题报告]HOJ

Palindrome

问题描述 :

Given a string S,you are asked to find the longest palindrome in the substring [l,r].

输入:

The first line is a number T which indicates the number of test cases

then follows a string s(length(s)<200000)
s can consists all ascii characters
Then an integer q,q querys(q<200000)
each query is two integer l,r.
find the longest palindrome in the substring [l,r].

输出:

The first line is a number T which indicates the number of test cases

then follows a string s(length(s)<200000)
s can consists all ascii characters
Then an integer q,q querys(q<200000)
each query is two integer l,r.
find the longest palindrome in the substring [l,r].

样例输入:

1
aaabbcc
5
1 7
1 4
2 3
4 5
2 5

样例输出:

3
3
2
2
2

Hint
1 7 means aaabbcc the longest palindrome substring is aaa,whose length is 3. 4 5 means bb the longest palindrome substring is bb,whose length is 2.

不知道错在哪了,求大神指教!!!

思路:用manacher求出每个以str[i]为中心轴的回文串的长度,RMQ预处理区间最大值,对于每个查询,二分最大回文串长,判定是否可行。

 

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int MAXN = 222222;

char str[ MAXN ];
int data[ MAXN * 2 ];
int p[ MAXN * 2 ];
int d[ MAXN * 2 ][30];
int n, len;

void init()
{
    int id,MaxL,MaxId;
    int i;
    MaxL=MaxId=0;
    len = strlen(&str[1]);
    for (i=1; i <= len; i++)
    {
        data[(i<<1)]=str[i];
        data[(i<<1)+1]=2;
    }
    data[0]=1;
    data[1]=2;
    n=(i<<1)+2;
    data[n]=0;
    MaxId=MaxL=0;
    p[0] = 1;
    for (i=1; i<n; i++)
    {
        if (MaxId>i)
            p[i]=min(p[2*id-i],MaxId-i);
        else
            p[i]=1;
        while (data[i+p[i]] == data[i-p[i]])
            p[i]++;
        if (p[i]+i>MaxId)
            MaxId=p[i]+i,id=i;
        //printf( "p[%d]=%d\n", i, p[i] );
    }
    for ( i = 1; i < n; ++i ) --p[i];

    return;
}

void RMQinit()
{
    for ( int i = 0; i <= n; ++i ) d[i][0] = p[i];
    for ( int j = 1; ( 1 << j ) <= n; ++j )
        for ( int i = 1; i + j - 1 <= n; ++i )
            d[i][j] = max( d[i][j - 1], d[ i + (1<<(j-1))][j - 1] );
    return;
}

int RMQquery( int L, int R )
{
    int k = 0;
    while ( (1 << (k + 1)) <= R - L + 1 ) ++k;
    return max( d[L][k], d[ R - ( 1 << k ) + 1 ][k] );
}

bool check( int L, int R, int mid )
{
    //if ( L + mid > R - mid ) return false;
    int ans = RMQquery( L + mid, R - mid );
    //printf("[%d %d]:%d\n", L + mid, R - mid, ans );
    //printf("ans = %d, mid = %d\n", ans, mid );
    if ( ans >= mid )
    {
        //puts("****");
        return true;
    }
    return false;
}

int BiSearch( int l, int r, int L, int R )
{
    int ans = 1;
    while ( l <= r )
    {
        int mid = ( l + r ) >> 1;
        if ( check( L, R, mid ) )
        {
            l = mid + 1;
            ans = mid;
        }
        else r = mid - 1;
    }
    return ans;
}

int main()
{
    int T;
    scanf( "%d", &T );
    getchar();
    while ( T-- )
    {
        memset( d, 0, sizeof(d) );
        memset( p, 0, sizeof(p) );
        gets( &str[1] );
        init();
        RMQinit();

        int Q;
        scanf( "%d", &Q );
        while ( Q-- )
        {
            int a, b;
            scanf( "%d%d", &a, &b );
            if ( a < 1 ) a = 1;
            if ( b > len ) b = len;
            if ( a > len )
            {
                puts("0");
                continue;
            }
            if ( a > b ) swap( a, b );
            int ans = BiSearch( 1, b - a + 1, a*2 - 1, b*2 + 1 );
            printf( "%d\n", ans );
        }
        getchar();
    }
    return 0;
}

 

参考:http://www.cnblogs.com/GBRgbr/archive/2013/08/27/3286025.html


  1. Pingback: Lil Wayne

  2. Pingback: singer

  3. Pingback: فروش دوربین های مدار بسته مخفی

  4. Pingback: نصب و اجرای دوربین مداربسته

  5. Pingback: ترمیم مو و کاشت مو

  6. Pingback: http://assoartigiani.brindisi.it/index.php?option=com_k2&view=itemlist&task=user&id=665651

  7. Pingback: sex toys for beginner

  8. Pingback: طراحی سایت فروشگاه

  9. Pingback: penis ring

  10. Pingback: نصب دوربین های مدار بسته

  11. Pingback: double penetration

  12. Pingback: black polythene sheeting

  13. Pingback: Magnetic

  14. Pingback: خرید اپل ایدی با ایمیل شخصی

  15. Pingback: {دوربین مداربسته|دوربین مداربسته سامسونگ|

  16. Pingback: sex gel

  17. Pingback: کفسابی در تهران

  18. Pingback: وکیل

  19. Pingback: eve's strap- on play set

  20. Pingback: vibrator

  21. Pingback: poker sex

  22. Pingback: personal massager

  23. Pingback: penile toy

  24. Pingback: Amber Hawkins

  25. Pingback: Super Heavyweight martial arts jacket

  26. Pingback: driving tips

  27. Pingback: bangal ka jadu

  28. Pingback: bangal ka jadu

  29. Pingback: Nipple Toys

  30. Pingback: Anal toys

  31. Pingback: آموزش نصب دوربین مدار بسته

  32. Pingback: phildot

  33. Pingback: bondage toys

  34. Pingback: vibrator pleasure

  35. Pingback: Butt plugs

  36. Pingback: Dildo

  37. Pingback: accounting

  38. Pingback: rabbit sex toy

  39. Pingback: anal sex toys

  40. Pingback: آموزش نصب دوربین مدار بسته

  41. Pingback: Middleweight uniform separates

  42. Pingback: benefits of watching porn

  43. Pingback: php ecommerce

  44. Pingback: how cholesterol levels predict your health

  45. Pingback: Etoro copytrading

  46. Pingback: auction marketplace

  47. Pingback: authentic serial keys

  48. Pingback: Miami

  49. Pingback: Download Free DJ Stevie J Mixtapes

  50. Pingback: Discover And Download Free Music

  51. Pingback: Blend City 42

  52. Pingback: flexible tile adhesive supplier

  53. Pingback: Hanoi Tam Coc

  54. Pingback: ノロウイルス

  55. Pingback: revize jerabu

  56. Pingback: airfreight

  57. Pingback: Download French Montana Mixtapes

  58. Pingback: download free games for windows

  59. Pingback: http://tarmimemoo.net

  60. Pingback: white or black karate pants separates

  61. Pingback: massage prostate

  62. Pingback: urgent care glendale

  63. Pingback: ترمیم مو بیماران

  64. Pingback: best sex lube

  65. Pingback: dp sex toy

  66. Pingback: rechargeable bullet vibrator

  67. Pingback: toys for couples

  68. Pingback: big vibrator

  69. Pingback: تردمیل

  70. Pingback: the bullet sex toy

  71. Pingback: lgbt sex toys

  72. Pingback: خرید انی apple id

  73. Pingback: اجاره ویلا یک روزه در کردان

  74. Pingback: suction cup dildo

  75. Pingback: best vibrating cock ring

  76. Pingback: kala jadu

  77. Pingback: خرید اپل ایدی با ایمیل شخصی

  78. Pingback: magnetic paper

  79. Pingback: خرید آنلاین تردمیل خانگی

  80. Pingback: worktop protection

  81. Pingback: anti slip tape

  82. Pingback: flame retardant polythene

  83. Pingback: sasha grey pocket pal

  84. Pingback: massager wand

  85. Pingback: how to find out if your partner is cheating

  86. Pingback: bdsm

  87. Pingback: best ben wa balls

  88. Pingback: sex diary

  89. Pingback: bondage handcuffs

  90. Pingback: خرید اپل ایدی

  91. Pingback: php open source

  92. Pingback: How to give a woman oral sex

  93. Pingback: lgbt anal toys

  94. Pingback: bullet sex toy

  95. Pingback: bullet egg vibrator

  96. Pingback: daily trade alerts

  97. Pingback: vpn خرید پرسرعت

  98. Pingback: japanese manga

  99. Pingback: Steel leg stretching machine

  100. Pingback: adam \u0026 eve clit sensitizer

  101. Pingback: gay sex toys

  102. Pingback: ترمیم مو

  103. Pingback: naughty nurse

  104. Pingback: تعمیر لوازم خانگی

  105. Pingback: vibrator for her

  106. Pingback: tratamento de Dependência Química

  107. Pingback: Minikert

  108. Pingback: Masturbator

  109. Pingback: web site

  110. Pingback: adam and eve

  111. Pingback: the bullet vibe

  112. Pingback: Consulting

  113. Pingback: PHIL

  114. Pingback: Best Ben Wa Balls

  115. Pingback: Sex Toy for Men

  116. Pingback: lifelike dildo

  117. Pingback: adamandeve.com

  118. Pingback: g spot

  119. Pingback: womens luxe vibe

  120. Pingback: Adam \u0026 Eve

  121. Pingback: rechargeable sex toy

  122. Pingback: sex toys for beginners

  123. Pingback: probiotic sauerkraut kvass

  124. Pingback: pc games for windows 10

  125. Pingback: free download for windows 7

  126. Pingback: free download for windows pc

  127. Pingback: butt plug beginner

  128. Pingback: lingerie chemise

  129. Pingback: different type of vibrator

  130. Pingback: Macho Stallion Erection Keeper

  131. Pingback: adam \u0026 eve

  132. Pingback: pipedream sex toys

  133. Pingback: philippines womens casual blouse manufacturer

  134. Pingback: A\u0026E beginner's power pump

  135. Pingback: Penis Pump Video

  136. Pingback: Best Vibrating Cock Ring

  137. Pingback: vibrator

  138. Pingback: let's talk about sex

  139. Pingback: oral

  140. Pingback: jbeatz

  141. Pingback: adam and eve sex toy shop

  142. Pingback: best vibrator

  143. Pingback: adult sex toy

  144. Pingback: adam and eve sex toys

  145. Pingback: دوربین مداربسته

  146. Pingback: Fuel injector

  147. Pingback: Google

  148. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  149. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的