1 条题解

  • 0
    @ 2025-8-24 22:02:37

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Seauy
    I remember your song, sung by centuries of wind.

    搬运于2025-08-24 22:02:37，当前版本为作者最后更新于2020-05-01 16:24:12，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    这题正解当然是数位DP

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

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

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

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

    f0=1,f1=2 f_0=1,f_1=2

    fi=2[i−2−(i mod 2)]÷2+1+fi−1 f_i=2^{ [i-2-(i \bmod 2)] \div 2 + 1}+f_{i-1}

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

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

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

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

    发现它满足如下程序所得 cnt 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 show,n ，表示程序会展示 N∈[1,n] N \in [1,n] 中所有花园的状态，并且展示到 N=show N=show 的时候会暂停

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

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

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

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

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

    2 3 2 2 3 2

    1 0 1 0 1 0

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

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

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

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

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

    然后还有每一层第一个花园的第 choice choice 位是 0 还是 1 的问题。规律是前两层第一个花园的第 choice choice 位是 0，之后一层便是 1，然后 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) O(n)

    最后 BB 两句

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

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

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

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

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

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

    • 1

    [IOI 2008] Linear Garden

    信息

    ID
    3670
    时间
    1500ms
    内存
    63MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 25ms