题解 P4685 【[IOI2008] Linear Garden 直线型花园】

· · 题解

这题正解当然是数位DP

但是当初不会，看到这题直接傻眼，则如之何……

被我用找规律硬找出来了，但是过程十分繁琐调了我五小时，眼睛都要看瞎了

这里简单说一下找出来的结果

首先是长度为 N 的公园的个数递推式：

f_0=1,f_1=2 f_i=2^{ [i-2-(i \bmod 2)] \div 2 + 1}+f_{i-1}

然后令 L=0,P=1 （同时保证了字典序），发现如果第一位为 0，那么花园的排名 1 \leq loc \leq \frac{f_i}{2} ，否则 \frac{f_i}{2} < loc\leq f_i 这不废话吗

并且如果把合法花园 G_{loc} 按位取反一下的话，便是 G_{f_i-loc+1}

然后只用考虑 1 \leq loc \leq \frac{f_i}{2} 的情况就行了

最后一个毁天灭地惨无人道（还不是因为你太菜）的规律，如何计算

发现它满足如下程序所得 cnt 的结果

void DFS(int ans,int depth,int thrw,bool com)
{
    if(depth>=n) {cnt=ans;return;}
    if(com)
    {
        if(Garden[depth+1]=='P') DFS((ans+POW2(thrw))%m,depth+2,thrw-1,1);
        else DFS(ans,depth+2,thrw-1,1);
        return;
    }
    if(depth&1)//向右边保留，左边去除 
    {
        if(Garden[depth+1]=='P')
        {
            //printf("+POW %d\n",POW2(thrw));
            DFS((ans+POW2(thrw))%m,depth+1,thrw-(!(n&1)),0);//走右边
        }
        else DFS(ans,depth+2,thrw-1,1);
    }
    else//向左边保留，右边去除 
    {
        if(Garden[depth+1]=='P')
        {
            //printf("+%d\n",f[n-depth-1]+1-POW2(thrw));
            DFS(ans+(f[n-depth-1]+1-POW2(thrw)+m)%m,depth+2,thrw-1,1);
        }
        else DFS(ans,depth+1,thrw-(n&1),0);
    }
}

至于为什么，我先奉上我找规律用的程序

/*
    01 序列 称其为平衡序列时，任何一段的 0 与 1 个数之差小于等于 2
    将长度为 n 的所有平衡 01 序列 按字典序排序，问某个序列在第几个 %m
    L=0 P=1

    已知 Last 是平衡序列，长 a

    n=1
    0 | 1

    n=2
    00 01 | 10 11

    n=3
    001 010 011 | 100 101 110

    n=4
    0010 
*/
#include<bits/stdc++.h>
#define mid ((L+R)>>1)
using namespace std;

const int MAXN=1e6;

int n;
int A[50][MAXN+5],num[50];
int f[50];

void PrintBinary(int ob,int len)
{for(int i=len;i;i--) cout<<((ob&(1<<(i-1)))>0);cout<<' ';}

int sum[3];
bool Check(int a,int len,bool b)
{
    memset(sum,0,sizeof sum);
    sum[b]=1; 
    for(int i=1;i<=len;i++,a>>=1)
    {
        sum[a&1]++;
        if(abs(sum[0]-sum[1])>2) return 0;
    }
    return 1;
}

bool Begin(int depth)
{
    if(depth==1) return 0;
    return depth&1;
}

int Translate(string ob,int len)
{
    int cnt=0;
    for(int i=0;i<len;i++) cnt=(cnt<<1)+(ob[i]=='P');
    return cnt;
}

int main()
{
    int show;scanf("%d",&show);
    f[1]=2;
    A[1][1]=0,A[1][2]=1,num[1]=2;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
        for(int j=1;j<=num[i-1];j++)
        {
            if(Check(A[i-1][j],i-1,0)) A[i][++num[i]]=(A[i-1][j]<<1);
            if(Check(A[i-1][j],i-1,1)) A[i][++num[i]]=(A[i-1][j]<<1|1);
        }
    for(int i=1,choice,temp,val,times;i<=n;i++)
    {
        if(i>1)
        {
            if(i&1) f[i]=pow(2,(i-3)/2+1)+f[i-1];
            else f[i]=pow(2,(i-2)/2+1)+f[i-1];
        }
        printf("n=%d have %d ---------------- formula result: %d\n",i,num[i],f[i]);
        for(int j=1;j<=num[i];j++) PrintBinary(A[i][j],i);
        printf("\n");
        if(show==i)
        {
            while(1)
            {
                scanf("%d",&choice);
                if(choice==-1) break;
                temp=0;
                times=1;
                val=Begin(choice);
                for(int j=1,lst=-1;j<=num[i];j++)
                {
                    if(!temp)
                    {
                        temp=1;
                        lst=((A[i][j]&(1<<(i-choice)))>0);
                        continue;
                    }
                    if(((A[i][j]&(1<<(i-choice)))>0)!=lst)
                    {
                        lst=((A[i][j]&(1<<(i-choice)))>0);
                        printf("%d ",temp);
                        temp=1;
                        times++;
                    }
                    else temp++;
                }
                printf("%d\n",temp);
                for(int j=1;j<=times;j++) printf("%d ",val),val=1-val;
                printf("\n");
            }
            for(string KEY;1;)
            {
                cin>>KEY;
                if(KEY=="-1") break;
                int Code=Translate(KEY,i);
                for(int L=1,R=num[i];L<=R;)
                {
                    if(A[i][mid]==Code) {printf("%d\n",mid);break;}
                    if(A[i][mid]<Code) L=mid+1;
                    else R=mid-1;
                }
            }
        }
    }
    return 0;
}

先输入 show,n ，表示程序会展示 N \in [1,n] 中所有花园的状态，并且展示到 N=show 的时候会暂停

对于暂停的那个 N ，接着输入若干 choice ，表示在长度为 N 的所有花园中，依次输出第 choice 位连续为 0/1 的段的长度

最后输入 -1 结束这一层的研究

比如当 N=5 时，所有段转成 0/1 表示法长这样：

00101 00110 01001 01010 01011 01100 01101 10010 10011 10100 10101 10110 11001 11010

那么你再输入 choice=3 ，那么它会输出

2 3 2 2 3 2

1 0 1 0 1 0

表示前 2 个公园的第 3 位为 1，接下来 3 个公园的第 3 位为 0 ，再接下来 2 个公园的第 3 位为 1……

如果你展示出所有 choice \in [1,N] ，发现去掉 0/1 那行，会形成一个数字金字塔，顶端只有两个 \frac{f}{2} ，而最底层全为 1

从上一层变到下一层的规律大概是：有两个奇数，会选择两个相反的方向，一个把自己的一半向下取整放在左边，另一半放在右边，自己消失（两半的和当然要跟原来一样）；另一个则是向右

其它所有偶数全把自己分成相等的两半，1 就不用动了

至于选哪两个奇数……不是每次奇数把自己分成两半都会有一半是奇数，另一半是偶数嘛，那么下一层所选的奇数就是它们分出来的两奇数

然后还有每一层第一个花园的第 choice 位是 0 还是 1 的问题。规律是前两层第一个花园的第 choice 位是 0，之后一层便是 1，然后 0/1 交替

可能有些细节没有提到（因为过于复杂且已经过去好久了），还需大家自己看程序琢磨一下

最后把 AC 代码奉上：

/*
    当 n 为 1 时， 奇数编号序列末尾为 0，偶数为 1
    当 n 为奇数时，奇数编号序列末尾为 1，偶数为 0
    当 n 为偶数时，奇数编号序列末尾为 0，偶数为 1

    序列个数为
        当 n 为奇数时 f[n]=(2^((n-3)/2)+f[n-1]/2)*2
        当 n 为偶数时 f[n]=(2^((n-2)/2)+f[n-1]/2)*2 
                      f[1]=2

    当序号 <= f[n]/2 时，开头为 0
    当序号 >  f[n]/2 时，开头为 1

    对于奇数来说 
        当序号 <= 2^((n-3)/2) 时，第二个为 0
        接下来 f[n-1]/2 个      ，第二个为 1
        接下来 f[n-1]/2 个      ，第二个为 0 
        最后      2^((n-3)/2) 个，第二个为 1

                  9

           31          31
        8      23   23     8
        8    15  8 8  15   8
        4 4 4 11 8 8 11 4 4 4
        4 4 4 4 7 4 4 4 4 4 4 7 4 4 4

    对于每个 n，第一个序列总会是 0010101010101... 

    序列个数的一半为
        当 n 为奇数时 f[n]/2=2^((n-3)/2)+f[n-1]/2
        当 n 为偶数时 f[n]/2=2^((n-2)/2)+f[n-1]/2
                      f[1]/2=1
*/
#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e6;

int n,m,cnt;
int f[MAXN+5];
string Garden;

int mem[MAXN+5]={1};
int POW2(int index)
{
    if(mem[index]) return mem[index];
    if(index<0) return 1;
    return mem[index]=(POW2(index-1)<<1)%m;
}

void DFS(int ans,int depth,int thrw,bool com)
{
    if(depth>=n) {cnt=ans;return;}
    if(com)
    {
        if(Garden[depth+1]=='P') DFS((ans+POW2(thrw))%m,depth+2,thrw-1,1);
        else DFS(ans,depth+2,thrw-1,1);
        return;
    }
    if(depth&1)//向右边保留，左边去除 
    {
        if(Garden[depth+1]=='P')
        {
            //printf("+POW %d\n",POW2(thrw));
            DFS((ans+POW2(thrw))%m,depth+1,thrw-(!(n&1)),0);//走右边
        }
        else DFS(ans,depth+2,thrw-1,1);
    }
    else//向左边保留，右边去除 
    {
        if(Garden[depth+1]=='P')
        {
            //printf("+%d\n",f[n-depth-1]+1-POW2(thrw));
            DFS(ans+(f[n-depth-1]+1-POW2(thrw)+m)%m,depth+2,thrw-1,1);
        }
        else DFS(ans,depth+1,thrw-(n&1),0);
    }
}

int main()
{
    f[1]=2,f[0]=1;
    scanf("%d %d",&n,&m);
    cin>>Garden,Garden=" "+Garden;
    //cout<<Garden<<endl;
    //printf("%d\n",Garden.length());
    //printf("Begin prework.\n");
    for(int i=2;i<=n;i++)
    {
        if(i&1) f[i]=(POW2((i-3)/2+1)+f[i-1])%m;
        else f[i]=(POW2((i-2)/2+1)+f[i-1])%m;
    }
    //printf("Prework Complete.\n");
    if(Garden[1]=='P')
    {
        for(int i=1;i<=n;i++)
            if(Garden[i]=='P') Garden[i]='L';
            else Garden[i]='P';
        //printf("Start DFS\n");
        DFS(1,1,n/2-1,0);
        printf("%d\n",(f[n]-cnt+1+m)%m);
    }
    else DFS(1,1,n/2-1,0),printf("%d\n",cnt);
    return 0;
}

时空复杂度 O(n)

最后 BB 两句

这题是窝省集训队入门测题目，当时信心满满地交了上去，第二天去上课路上发现只有 60，T 到飞起

然后让教练帮忙看看哪错了，却没发现

稍加检查，发现是写递归 pow 忘记记忆化了 smg

由于常数比直接数位DP小太多了，所以一时间拿了窝省的效率 rk1

不过随后便被窝省神仙甩掉了，最后一次看到是 rk3

不建议大家用找规律这种不是办法的办法做题，一是经常找不准，二是要找就要花很多的时间，考场上可是不能这么干的，到时候万一只会找规律不就药丸