[题解] P3581 [POI2015] CZA
Alex_Eon
·
·
题解
Change log
- 2023.10.25 修改少量 MarkDown 的使用。
\color{blueviolet}\text{POI 套题集合（点我）}
\color{red}\text{博客内食用效果更佳（点我）}
时间复杂度：O(n)
完整思路
观察到 p 的范围很小，我们尝试进行分类讨论。
当 p=0：
显著地，当且仅当 n=1 时答案为 1，剩余情况为 0。
当 p=1：
同样显著地，此时当且仅当 n=1\lor(n=2\land k=0) 时答案为 1，剩余情况为 0。
当 p=2：
考虑先放置 n，它两侧只有可能是 n-1,n-2，n-1 旁边只有可能放 n-3，n-2 旁边只有可能放 n-3，以此类推，这种情况下只有顺时针逆时针两种情况，构造并判断即可。
当 p=3：
我们尝试从 n 至 1 依次放进环内，考虑当前放置到编号为 i 的，显然它只能和 i+1,i+2,i+3,i-1,i-2,i-3 相邻，我们只需要考虑 i+1,i+2,i+3，它们都在环内，而 i-1,i-2,i-3 的情况会在放入它们的时候考虑。
我们现在考虑两个问题：
-
- 当我们放入 i 后，i+3 不能和接下来要放入的点相邻，这就意味着 i+3 一定要紧挨着两边的点，我们需要判断此时 i+3 的状态。（这种情况会产生上一个问题，可以理解为 i+3 与两边合并，使这一段不能放置接下来的东西）。
现在给出以下约定方便表述：
-
- 设 DP 状态 f_{i,j,st} 表示放置完编号 i 的东西，是否是逆时针（j），i+1,i+2,i+3 之间的位置状态为 st（对位置 1,2,3 状态进行状压，分别对应 1,2,4）。
-
-
对于状态 f_{i+1,j,st} 我们尝试向下转移。
若位置 1 可放置（以下讨论均基于顺时针，逆时针只需要将所有状态置反即可）：
$$\left(2\notin st\lor\mathrm{sit}(i+2,i+3)\right)\land\left(3\notin st\lor\mathrm{sit}(i+3,i+1)\right)$$
放置到位置 $1$ 后我们的状态变为 $f_{i,j\oplus1,5}$（首先这种放置显著会改变顺逆状态，其次这种放置状态下使得 $i,i+1$ 以及 $i,i+2$ 之间的空位可用。），可以得到以下转移。
$$f_{i,j\oplus1,\{1,3\}}=f_{i,j\oplus1,\{1,3\}}+f_{i+1,j,st}$$
**若位置 $2$ 可放置**：
得到以下约束以及转移。
$$\mathrm{sit}(i,i+3)\land\left(2\notin st\lor\mathrm{sit}(i+2,i+3)\right)$$
设 $st'$ 表示改变后的状态，若 $1\in st$，则 $st'=\{2,3\}$，否则 $st'=\{3\}$。
$$f_{i,j,st'}=f_{i,j,st'}+f_{i+1,j,st}$$
**若位置 $3$ 可放置**：
得到以下约束以及转移。
$$\mathrm{sit}(i+3,i)\land\left(3\notin st\lor\mathrm{sit}(i+3,i+1)\right)$$
设 $st'$ 表示改变后的状态，若 $1\in st$，则 $st'=\{1,2\}$，否则 $st'=\{1\}$。
$$f_{i,j,st'}=f_{i,j,st'}+f_{i+1,j,st}$$
---
大部分转移已经讨论完毕，最后一层还需约束放置完的左右关系，与上述约束、转移类似，就不进行冗杂的讨论了。
### 代码实现需要注意的地方：
- 别忘记取模。
- 对于初值有 $f_{n-2,0,7}=1,f_{n-2,1,7}=1$。
### 参考代码：
```cpp
#include<bits/stdc++.h>
#define LL long long
#define UN unsigned
using namespace std;
//--------------------//
const int N=1e6+5,Mod=1e9+7;
int n,k,p,f[N][2][8];
bool ht[N][10];
void add(int &x,int y){x+=y,x-=((x>=Mod)?Mod:0);}//优化取模
bool sit(int x,int y){return abs(x-y)<=p&&!ht[y][y-x+3];}//判断是否能坐在右面
bool ck1(int i,int j,int st,int pos)//判断是否合法
{
if(j)
{
if(pos==1)
return ((!(st&4)||sit(i+3,i+1))&&(!(st&2)||sit(i+2,i+3)));
if(pos==2)
return (sit(i,i+3)&&(!(st&4)||sit(i+3,i+1)));
return (sit(i+3,i)&&(!(st&2)||sit(i+2,i+3)));
}
if(pos==1)
return (!(st&4)||sit(i+1,i+3))&&(!(st&2)||sit(i+3,i+2));
if(pos==2)
return (sit(i+3,i)&&(!(st&4)||sit(i+1,i+3)));
return (sit(i,i+3)&&(!(st&2)||sit(i+3,i+2)));
}
bool ck2(int i,int j,int st,int pos)//判断 i=1 时是否合法
{
if(i>1)
return true;
if(j)
{
if(pos==1)
return (sit(1,3)&&sit(2,1));
if(pos==2)
return (sit(3,1)&&(!(st&1)||sit(2,3)));
return (sit(1,2)&&(!(st&1)||sit(2,3)));
}
if(pos==1)
return (sit(3,1)&&sit(1,2));
if(pos==2)
return (sit(1,3)&&(!(st&1)||sit(3,2)));
return (sit(2,1)&&(!(st&1)||sit(3,2)));
}
//--------------------//
int main()
{
scanf("%d%d%d",&n,&k,&p);
for(int x,y,i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
if(abs(x-y)<=p)
ht[x][x-y+3]=true;
}
if(p==0)//分讨
{
if(n==1)
printf("1");
else
printf("0");
return 0;
}
if(p==1)
{
if(n==1||(n==2&&k==0))
printf("1");
else
printf("0");
return 0;
}
if(n==1)
printf("1");
if(n==2)
printf("%d",k?0:1);
if(n<3)
return 0;
if(p==2)
{
int ans=0;
//顺时针
bool flag=((!sit(n-1,n))|((n&1)&&!sit(1,2))|((!(n&1))&&!sit(2,1)));
for(int i=n-1;i>2;i-=2)
flag|=!sit(i-2,i);
for(int i=n-2;i>2;i-=2)
flag|=!sit(i,i-2);
//逆时针
ans+=!flag,flag=((!sit(n,n-1))|((n&1)&&!sit(2,1))|((!(n&1))&&!sit(1,2)));
for(int i=n-1;i>2;i-=2)
flag|=!sit(i,i-2);
for(int i=n-2;i>2;i-=2)
flag|=!sit(i-2,i);
ans+=!flag;
printf("%d",ans);
return 0;
}
f[n-2][0][7]=f[n-2][1][7]=1;
for(int i=n-2;i>=2;i--)//倒序转移
{
for(int j=0;j<=1;j++)
{
for(int st=0;st<=7;st++)
{
if(!f[i][j][st])
continue;
if((st&1)&&ck1(i-1,j,st,1)&&ck2(i-1,j,st,1))
add(f[i-1][j^1][5],f[i][j][st]);
if((st&2)&&ck1(i-1,j,st,2)&&ck2(i-1,j,st,2))
add(f[i-1][j][4|((st&1)<<1)],f[i][j][st]);
if((st&4)&&ck1(i-1,j,st,3)&&ck2(i-1,j,st,3))
add(f[i-1][j][1|((st&1)<<1)],f[i][j][st]);
}
}
}
int ans=0;
for(int i=0;i<=7;i++)//统计答案
add(ans,f[1][0][i]),add(ans,f[1][1][i]);
printf("%d",ans);
return 0;
}
```