首页 > ACM题库 > HDU-杭电 > hdu 3222 Compressed String-分治[解题报告]C++
2014
03-07

hdu 3222 Compressed String-分治[解题报告]C++

Compressed String

问题描述 :

Dealing with super long character strings is Chris’s daily work. Unfortunately, the strings are so long that even the fastest computer in the world cannot work with them.Chris does her work in a smart way by compressing the strings into shorter expressions. She does her compression for each string in the following way:

a) Find a consecutive repeated substring of the original string, e.g. “ab” in “cabababd”.

b) Replace the repeating part with the bracketed repetend, followed by the times the repetend appears in the original string. e.g. Write “cabababd” as “c[ab]3d”. Note she can also write it as “c[ab]1ababd” or “ca[ba]2bd” and so on, although these string are not compressed as well as the first one is.

c) Repeat a) and b) several times until the string is short enough.

Chris does her compression quite well. But as you know, the work is boring and a waste of time. Chris has written a computer program to help her do the boring work. Unfortunately, there is something wrong with the program; it often outputs an incorrect result. To help her debug the program, you are ordered to write a debugger which can compare Chris’s standard compressed string against the string compressed by the program.

输入:

There are multiple test cases.
The first line of the input contains an integer T, meaning the number of the test cases.For each test case, there are two lines of character strings which the first one is Chris’s standard compressed string and the second one is the program’s compressed string. Both string contains only lowercase letters (a-z), square brackets ([]) and numbers (0-9). The brackets must be followed with an integer indicating the times the string in the brackets repeat, note that the repeat time can be zero. The brackets can be nested.
You can assume all the compressed strings in the input are no longer than 20.
See further details in the input sample.

输出:

There are multiple test cases.
The first line of the input contains an integer T, meaning the number of the test cases.For each test case, there are two lines of character strings which the first one is Chris’s standard compressed string and the second one is the program’s compressed string. Both string contains only lowercase letters (a-z), square brackets ([]) and numbers (0-9). The brackets must be followed with an integer indicating the times the string in the brackets repeat, note that the repeat time can be zero. The brackets can be nested.
You can assume all the compressed strings in the input are no longer than 20.
See further details in the input sample.

样例输入:

5
a[a]12
[[a]3]4a
[z]12
zzzzzzzzz
[a[ba]2b]12
[ab]36
[a]123123123[icpc]2
[[a]123]1001001inter
aismoreeasierthanc
gismuchharderthanj

样例输出:

Case #1: YES
Case #2: NO 10
Case #3: YES
Case #4: NO 123123125
Case #5: NO 1
Hint

For sample test case 3, the first string “[a[ba]2b]12” can be written as “[ababab]12”, then “[[ab]3]12”, finally we get “[ab]36”. The numbers in this task may be very large and cannot be stored in a 32 bit integer.


好像是2009 Asia Shanghai Regional Contest Host by DHU的C题
膜拜上交拿了这题的FB
顺便插曲一下
pascal的过了SPOJ和acmicpc,HDU死活不过
cpp过了SPOJ和hdu,acmicpc死活过不了
后来把int都改成了LONG LONG然后过了acmicpc,呵呵
尼玛我调试的时候加了一行yooooooooooooo!然后忘记去掉了,吃了好多WA,艹。。。
SPOJ比较正常,HDU专门卡PAS的字符串读入,我擦,acmicpc大概比较奇葩,我pascal秒过而且rank1
然后cpp不过,改成long long多打了一行。。。后来好不容易过了。
这题大概就是二分答案+字符串的hash,我用的BKDRhash,那么两个字符串的hash值相同那么差不多字符串就是一样的,然后为了防止错误我用了两套MOD和Prime然后再比较,两个都相同才相同。
为毛二分?比较前K项是否相同嘛!然后BKDR可以用等比数列乱搞~~
BKDR是什么?乃们自己看吧,大概就是两个质数乘法,乘方再取模 http://www.byvoid.com/blog/hash-compare/
过了~~
贴个代码:

/*
    Author : zxybazh
    Date   : 2012/10/31
    Soure  : Compressed String hdu_3222
*/
   
   
#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#define LL long long
   
using namespace std;
   
char s[10][1001];
LL kk,tmp,n,m;
LL k,t,ans;
LL mo[10],p[10];
LL num[10][101],sum[10][101],cp[10][101];
LL en[10][101];
   
LL work(LL p,LL x){
    LL tmp=1;
    LL d=0;
    for (;x!=0; x >>= 1){
        if (x & 1) tmp=tmp * cp[p][d]% mo[p];
        d++;
    }
    return tmp;
}
   
void extended_gcd(LL a, LL b,LL &x,LL &y){
    LL tmp;
    if (b==0) {
        x=1;y=0;
    }
    else{
        extended_gcd(b,a % b,x,y);
        tmp=y;y=x-a / b*y;x=tmp;
    }
}
   
LL ny(LL d,LL b){
    LL tmp,tt;
    extended_gcd(b,mo[d],tt,tmp);
    return tt;
    cout << tt <<endl;
}
   
LL get(LL sx,LL num, LL d,LL gb){
    return(sx * (( work (d , gb * num) + mo[d] -1) % mo[d]) % mo[d]
        * ((ny(d,work(d,gb) + mo[d] - 1)) % mo[d] + mo[d]) % mo[d]);
}
   
void solve(LL d,LL l,LL r,LL le,LL &t1,LL &t2){
    LL i,k1,k2,t;
    t1=0;t2=0;t=0;i=l;
    while ( le > t && i <= r) {
        if (s[d][i]!='['){
            t++;
            t1=(t1 * p[1] + s[d][i])% mo[1];
            t2=(t2 * p[2] + s[d][i])% mo[2];
            i++;
            continue;
        };
        if (t+sum[d][i]*num[d][i]<=le) {
            solve(d,i+1,en[d][i]-1,le,k1,k2);
            k1=get(k1,num[d][i],1,sum[d][i]);
            k2=get(k2,num[d][i],2,sum[d][i]);//first num which p gongbi
            t1=(t1*work(1,num[d][i]*sum[d][i])+k1 % mo[1]) % mo[1];
            t2=(t2*work(2,num[d][i]*sum[d][i])+k2 % mo[2]) % mo[2];
            t+=sum[d][i]*num[d][i];
            i=en[d][i]+1;
            while (i<=r && s[d][i]>='0' && s[d][i]<='9') i++;
        } else
        if (t+sum[d][i]>=le) {
            solve(d,i+1,en[d][i]-1,le-t,k1,k2);
            t1=(t1*work(1,le-t)+k1 % mo[1]) % mo[1];
            t2=(t2*work(2,le-t)+k2 % mo[2]) % mo[2];
            t=le;
        }
        else{
            solve(d,i+1,en[d][i]-1,le-t,k1,k2);
            k1=get(k1,(le-t) / sum[d][i],1,sum[d][i]);
            k2=get(k2,(le-t) / sum[d][i],2,sum[d][i]);
            t1=(t1*work(1,(le-t) / sum[d][i]*sum[d][i])+k1 % mo[1]) % mo[1];
            t2=(t2*work(2,(le-t) / sum[d][i]*sum[d][i])+k2 % mo[2]) % mo[2];
            t+=((le-t) / sum[d][i] * sum[d][i]);
            solve(d,i+1,en[d][i]-1,le-t,k1,k2);
            t1=(t1*work(1,le-t)+k1 % mo[1]) % mo[1];
            t2=(t2*work(2,le-t)+k2 % mo[2]) % mo[2];
            t=le;
        };
    }
    //cout<< d<<' '<<l<<' '<<r<<' '<<le<<' '<<t1<<' '<<t2<<endl;
}
   
bool check(LL x){
    LL t1,t2,k1,k2;
    solve(1,0,strlen(s[1])-1,x,t1,t2);
    solve(2,0,strlen(s[2])-1,x,k1,k2);
    if (t1==k1 && t2==k2) return true; else return false;
}
   
void tc(LL l,LL r){
    LL mid;
    while (l<=r) {
        mid=(l+r)/2;
        if (not check(mid)){
            if (mid<ans) ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
}
   
LL calc(LL d,LL l,LL r){
    LL k,i,tmp;
    LL kk,t;
    t=0;i=l;
    while (i<=r) {
        if (s[d][i]!='[') {
            t++;i++;continue;
        }
        tmp=0;
        for (k=i+1;k<=r;k++){
            if (s[d][k]==']' && tmp==0) break;
            if (s[d][k]=='[')  tmp++;
            if (s[d][k]==']')  tmp--;
        }
        kk=0;
        tmp=k+1;
        while (tmp<=r && s[d][tmp]>='0' && s[d][tmp]<='9') {
            kk=kk * 10 + s[d][tmp]-'0';
            tmp++;
        }
        en[d][i]=k;
        sum[d][i]=calc(d,i+1,k-1);
        num[d][i]=kk;
        t+=sum[d][i]*num[d][i];
        i=tmp;
    }
    return t;
}
int main(){
    //freopen("compress.in", "r", stdin);
    //freopen("compress.out", "w", stdout);
   
    LL testcase;
    scanf("%I64d\n",&testcase);
   
    p[1]=131;
    p[2]=1313;
    mo[1]=23456789;
    mo[2]=19891229;
    for (LL i=1;i<3;i++){
        cp[i][0]=p[i];
        for (LL j=1;j<101;j++) cp[i][j]=(cp[i][j-1]*cp[i][j-1]) % mo[i];
    }
    //cout<<"yooooooooooo"<<endl;
    for (LL kk=1;kk<=testcase;kk++){
        cout<<"Case #"<<kk<<": ";
        gets(s[1]);gets(s[2]);
        k=calc(1,0,strlen(s[1])-1);
        t=calc(2,0,strlen(s[2])-1);
        if (k!=t){
            if (t<k)k=t;
            ans=k+1;
            tc(1,k);
            cout<<"NO ";
            cout<<ans<<endl;
        }
        else{
            ans=k+1;
            tc(1,k);
            if (ans==k+1) cout<<"YES"<<endl;
                else cout<<"NO "<<ans<<endl;
        }
    }
}

 
参考:http://hi.baidu.com/npc42/item/d536c1ffd7bd001ace9f32a0


  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3