[POI2015]CZA
2024-10-21 12:55:40
p很小，讨论
p=0。。。
p=1。。。
p=2：n-1放左或者放右两种情况，剩下怎么放是固定的，模拟然后判断即可
p=3：
正着做要状压，类似放书和排座位那些题，考虑以某个顺序加入元素，不断扩充出整个环
不妨从n开始往下加，其实只用考虑i,i-1,i-2和要放的i-3的关系。i-3只能放在这三个的两个的中间，
所以这中间不能再有之前的i+1，i+2这种了。
而且区分左右还要记录顺逆
f[i][0/1][2^3]前i个，顺逆，相邻能不能放（是否紧相邻）
然后枚举放哪里转移，之后i会固定，看会不会和i-1,i-2,i-3冲突
转移时候大力分类讨论
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=+;
const int mod=1e9+;
int n,k,p;
int no[N][];//0:-3; 1:-2 ; 2:-1 ; 3:0 ; 4:1 ; 5:2 ; 6:3
int add(int x,int y){
return x+y>=mod?x+y-mod:x+y;
}
void sol0(){
if(n==) puts("");
else puts("");
}
void sol1(){
if(n==||(n==&&k==)) puts("");
else puts("");
}
int a[N];
void sol2(){
if(n<=){
if(n==||(n==&&k==)) puts("");
else puts("");
return;
}
int ans=;
a[]=n;
for(reg x=n-,i=;x>;++i,x-=) a[i]=x;
for(reg x=n-,i=n;x>;--i,x-=) a[i]=x;
bool fl=true;
for(reg i=;i<n;++i){
if(no[a[i]][a[i+]-a[i]+]) fl=false;
}
if(no[a[n]][a[]-a[n]+]) fl=false;
if(fl) ++ans; a[]=n;
for(reg x=n-,i=;x>;++i,x-=) a[i]=x;
for(reg x=n-,i=n;x>;--i,x-=) a[i]=x;
fl=true;
for(reg i=;i<n;++i){
if(no[a[i]][a[i+]-a[i]+]) fl=false;
}
if(no[a[n]][a[]-a[n]+]) fl=false;
if(fl) ++ans;
printf("%d",ans);
}
int f[N][][];
int dis(int x,int y){
return y-x+;
}
int mk(int s1,int s2,int s3){
return s3*+s2*+s1;
}
void calc(int i,int j,int s){//add i-1
int now=f[i][j][s];
int s1=s&,s2=(s>>)&,s3=(s>>)&;
if(i!=){
if(j==){//shun
if(s1){
if(s3){
if(no[i][dis(i,i+)]==&&no[i+][dis(i+,i-)]==) f[i-][j][mk(s2,,)]=add(f[i-][j][mk(s2,,)],now);
}
else{
if(no[i+][dis(i+,i-)]==) f[i-][j][mk(s2,,)]=add(f[i-][j][mk(s2,,)],now);
}
}
if(s2){
if((s1==||no[i+][dis(i+,i+)]==)&&(s3==||no[i][dis(i,i+)]==)) f[i-][j^][mk(,,)]=add(f[i-][j^][mk(,,)],now);
}
if(s3){
if((s1==||no[i+][dis(i+,i+)]==)&&(no[i-][dis(i-,i+)]==)) f[i-][j][mk(s2,,)]=add(f[i-][j][mk(s2,,)],now);
}
}
else{//j==1
if(s1){
if(s3){
if(no[i+][dis(i+,i)]==&&no[i-][dis(i-,i+)]==) f[i-][j][mk(s2,,)]=add(f[i-][j][mk(s2,,)],now);
}
else{
if(no[i-][dis(i-,i+)]==) f[i-][j][mk(s2,,)]=add(f[i-][j][mk(s2,,)],now);
}
}
if(s2){
if((s1==||no[i+][dis(i+,i+)]==)&&(s3==||no[i+][dis(i+,i)]==)) f[i-][j^][mk(,,)]=add(f[i-][j^][mk(,,)],now);
}
if(s3){
if((s1==||no[i+][dis(i+,i+)]==)&&(no[i+][dis(i+,i-)]==)) f[i-][j][mk(s2,,)]=add(f[i-][j][mk(s2,,)],now);
}
}
}else{//las
if(j==){
if(s1){
if((s3==||no[i][dis(i,i+)]==)&&(no[i+][dis(i+,i-)]==)&&(no[i-][dis(i-,i+)]==)&&(s2==||no[i+][dis(i+,i)]==)){
f[i-][j][mk(,,)]=add(f[i-][j][mk(,,)],now);
}
}
if(s2){
if((s3==||no[i][dis(i,i+)]==)&&(s1==||no[i+][dis(i+,i+)]==)&&(no[i+][dis(i+,i-)]==&&no[i-][dis(i-,i)]==)){
f[i-][j^][mk(,,)]=add(f[i-][j^][mk(,,)],now);
}
}
if(s3){
if((s1==||no[i+][dis(i+,i+)]==)&&(s2==||no[i+][dis(i+,i)]==)&&(no[i][dis(i,i-)]==&&no[i-][dis(i-,i+)]==)){
f[i-][j][mk(,,)]=add(f[i-][j][mk(,,)],now);
}
}
}
else{
if(s1){
if((s3==||no[i+][dis(i+,i)]==)&&(no[i-][dis(i-,i+)]==)&&(no[i+][dis(i+,i-)]==)&&(s2==||no[i][dis(i,i+)]==)){
f[i-][j][mk(,,)]=add(f[i-][j][mk(,,)],now);
}
}
if(s2){
if((s3==||no[i+][dis(i+,i)]==)&&(s1==||no[i+][dis(i+,i+)]==)&&(no[i-][dis(i-,i+)]==&&no[i][dis(i,i-)]==)){
f[i-][j^][mk(,,)]=add(f[i-][j^][mk(,,)],now);
}
}
if(s3){
if((s1==||no[i+][dis(i+,i+)]==)&&(s2==||no[i][dis(i,i+)]==)&&(no[i-][dis(i-,i)]==&&no[i+][dis(i+,i-)]==)){
f[i-][j][mk(,,)]=add(f[i-][j][mk(,,)],now);
}
}
}
}
}
void sol3(){
if(n<=){
if(n==||(n==&&k==)) puts("");
else puts("");
return;
}
if(n==){
int ans=;
if(no[n][dis(n,n-)]==&&no[n-][dis(n-,n-)]==&&no[n-][dis(n-,n)]==) ++ans;
if(no[n][dis(n,n-)]==&&no[n-][dis(n-,n-)]==&&no[n-][dis(n-,n)]==) ++ans;
printf("%d",ans);
return ;
}
f[n-][][]=;f[n-][][]=;
for(reg i=n-;i>=;--i){
for(reg s=;s<;++s){
if(f[i][][s]) calc(i,,s);
if(f[i][][s]) calc(i,,s);
}
}
int ans=;
for(reg s=;s<;++s){
ans=add(ans,add(f[][][s],f[][][s]));
}
printf("%d",ans);
}
int main(){
rd(n);rd(k);rd(p);
int x,y;
for(reg i=;i<=k;++i){
rd(x);rd(y);
if(abs(x-y)<=p){
no[x][y-x+]=;
}
}
if(p==) sol0();
else if(p==) sol1();
else if(p==) sol2();
else sol3();
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/3/3 10:02:45
*/
最新文章
- Spark作业调度阶段分析
- 玩转Windows服务系列——无COM接口Windows服务启动失败原因及解决方案
- 【MVC】AJAX+PartialView实现商城首页的楼层加载
- 微信公众平台回复过了怎么不能再次回复？亲们要注意查看"公众平台回复用户消息时限变更通知"的公告啊
- jpeglib使用指南
- HTML5入门5---HTML5控件元素
- Codevs 1217 借教室 2012年NOIP全国联赛提高组
- Successfully installed matplotlib
- Java环境配置出现的问题及解决办法
- Protel99Se使用方法详解
- Swift - 短信发送功能的实现
- linux文件系统命令
- $http post 取不到数据
- 06jQuery-03-选择器查找和过滤
- maven里面pom文件的各标签介绍
- 51Nod 1185 威佐夫游戏 V2
- java-Redis集合
- 代码实战之AdaBoost
- 解剖SQLSERVER 第一篇 数据库恢复软件商的黑幕（有删减版）
- 免费CDN公共库——网站提速 静态资源库