正解:$dp$
解题报告:
一年过去了$gql$还是不咋会这题,,,好菜昂我的$NOIp$必将惨败了$kk$
考虑从大到小枚举两个相同的数填哪儿,根据那个限制,十分显然的是这两个数必须紧挨着已填的,只有三种填法.第一种是各填一边.第二种是同填左边,第三种是同填右边.
十分显然的是这么填就可以消除那个先不降后不升的限制了.现在就只有那若干个要求的限制了.就每次枚举位置之后$check$下是否有限制.如果和这个限制相关的另一个数的位置不在中间也不要管,否则判断下是否能转移(即,如果要求大于就不能转移嘛$QwQ$.
最后大概整理下$QwQ$.
考虑区间$dp$,设$f[l,r]$表示已经填了$[l,r]$的方案数.然后从大到小枚举填哪个数,并枚举填入的位置.判断能否转移后转移就好,$over$.
然后细节挺多的我又写得比较丑所以来说下几个容易错的细节,,,
第一个是要开$ll$.
第二个是在判是否合法的时候,不知道是不是我写得丑的原因所以要判很多,,,举个$eg$,假如是要填$pos1,pos2$,在判断$<,>$的时候就要判断不能是$pos,pos2$,判断$leq,geq$的时候要判断可以是$pos1,pos2$.同时我关于$=$的是先提前判了个$size$的.然后就会被两次相同的相等要求卡掉.虽然题目没有这个数据但是我自己造了这个数据卡了自己.所以最好在最开始读入的时候就判掉.
反正就杂七杂八一堆细节,多拍拍总能全找出来的$bushi$
#include<bits/stdc++.h> using namespace std; #define il inline #define gc getchar() #define int long long #define ri register int #define rc register char #define rb register bool #define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i) const int N=200+10; int n,m,f[N][N]; vector<int>opt[N][20]; il int read() { rc ch=gc;ri x=0;rb y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } il int rd() { rc ch=gc; while(ch!='>' && ch!='<' && ch!='=')ch=gc; if(ch=='=')return 1;;if(ch=='>')return 2+(gc=='=');if(ch=='<')return 4+(gc=='='); } /* =:1 >:2 >=:3 <:4 <=:5 */ il bool check(ri pos1,ri pos2,ri l,ri r) { if(opt[pos1][1].size()>1)return 0; if(opt[pos1][1].size())if(opt[pos1][1][0]!=pos2 && opt[pos1][1][0]!=pos1)return 0; ri sz=opt[pos1][2].size(); rp(i,0,sz-1) if((l<=opt[pos1][2][i] && opt[pos1][2][i]<=r) || opt[pos1][2][i]==pos2 || opt[pos1][2][i]==pos1)return 0; sz=opt[pos1][3].size(); rp(i,0,sz-1) if((l<=opt[pos1][3][i] && opt[pos1][3][i]<=r) && opt[pos1][3][i]!=pos1 && opt[pos1][3][i]!=pos2)return 0; sz=opt[pos1][4].size(); rp(i,0,sz-1) if(l>opt[pos1][4][i] || opt[pos1][4][i]>r || opt[pos1][4][i]==pos1 || opt[pos1][4][i]==pos2)return 0; sz=opt[pos1][5].size(); rp(i,0,sz-1) if((l>opt[pos1][5][i] || opt[pos1][5][i]>r) && opt[pos1][5][i]!=pos1 && opt[pos1][5][i]!=pos2)return 0; return 1; } signed main() { freopen("1522.in","r",stdin);freopen("1522.out","w",stdout); n=read();m=read(); rp(i,1,m) { ri x=read(),op=rd(),y=read(); if(op&1 && !(x^y))continue; if(op==1 && opt[x][1].size())if(opt[x][1][0]==y)continue;else return printf("0 "),0; opt[x][op].push_back(y); if(op>3)opt[y][op-2].push_back(x);else if(op>1)opt[y][op+2].push_back(x);else opt[y][op].push_back(x); } rp(i,1,(n<<1)-1)f[i][i+1]=check(i,i+1,i,i+1)*check(i+1,i,i,i+1); rp(i,2,n) { rp(l,1,n<<1) { ri r=l+((i-1)<<1)+1; f[l][r]+=f[l+1][r-1]*check(l,r,l+1,r-1)*check(r,l,l+1,r-1); f[l][r]+=f[l+2][r]*check(l,l+1,l+2,r)*check(l+1,l,l+2,r); f[l][r]+=f[l][r-2]*check(r-1,r,l,r-2)*check(r,r-1,l,r-2); } } printf("%lld ",f[1][n<<1]); return 0; }