求卡常,TLE两个点
#include <cstdio>
#include <cstdlib>
#include <cctype>
#define N 21
#define rnt register int
using namespace std;
int T,n,ans=1<<30,x,y,sum[N];
inline char my_getchar(){
static char buf[2048];
static int size=0,pos=0;
if(size==pos){
pos=0;
size=fread(buf,1,2048,stdin);
if(!size) return EOF;
else return buf[pos++];
}
else return buf[pos++];
}
inline int FR(){//fast_read
int ans=0,fh=0;
char c=my_getchar();
while(!isdigit(c)){
fh|=c=='-';
c=my_getchar();
}
while(isdigit(c)) ans=(ans<<1)+(ans<<3)+(c^48),c=my_getchar();
return fh?-ans:ans;
}
void dfs(int x);
inline bool check1();//判断牌打完没
inline bool check2(int l,int r);//判断能不能出单顺
inline void do2(int l,int r);//出单顺
inline void undo2(int l,int r);//收回单顺
inline bool check3(int l,int r);//判断能不能出双顺
inline void do3(int l,int r);//出双顺
inline void undo3(int l,int r);//收回双顺
inline bool check4(int l,int r);//判断能不能出三顺
inline void do4(int l,int r);//出三顺
inline void undo4(int l,int r);//收回三顺
inline bool check5(int x);//判断能不能出三张
inline void do5(int x);//出三张
inline void undo5(int x);//收回三张
inline bool check6(int x,int y);//判断能不能打三带一
inline void do6(int x,int y);//出三带一
inline void undo6(int x,int y);//收回三带一
inline bool check7(int x,int y);//判断能不能打三带二
inline void do7(int x,int y);//出三带二
inline void undo7(int x,int y);//收回三带二
inline bool check8(int x);//我开天王炸
inline void do8(int x);//我开天王炸
inline void undo8(int x);//我开天王炸
inline bool check9(int x,int y,int z);//判断能否出四带一
inline void do9(int x,int y,int z);//出四带一
inline void undo9(int x,int y,int z);//收回四带一
inline bool check10(int x,int y,int z);//判断能否出四带二
inline void do10(int x,int y,int z);//四带二
inline void undo10(int x,int y,int z);//四带二
inline bool check11(int x);//能否出对子
inline void do11(int x);//出对子
inline void undo11(int x);//收回对子
inline bool check12();//王炸出来见我
inline void do12();//王炸出来见我
inline void undo12();//王炸出来见我
inline bool check13(int x);//单走一个x,萨比
inline void do13(int x);//单走一个x,萨比
inline void undo13(int x);//单走一个x,萨比
int main(){
T=FR(),n=FR();
for(rnt tt=1;tt<=T;tt=-~tt){
ans=1<<30;
for(rnt i=3;i<=17;i=-~i) sum[i]=0;
for(rnt i=1;i<=n;i=-~i){
x=FR(),y=FR();
if(x>=3) sum[x]=-~sum[x];
else if(x==1) sum[14]=-~sum[14];
else if(x==2) sum[15]=-~sum[15];
else sum[15+y]=-~sum[15+y];
}
dfs(0);
printf("%d\n",ans);
}
}
void dfs(int x){
if(x>=ans) return ;
if(check1()) ans=x;
for(rnt i=3;i<=10;i=-~i) for(rnt j=i+4;j<=14;j=-~j)
if(check2(i,j)){do2(i,j);dfs(x+1);undo2(i,j);}
else break;
for(rnt i=3;i<=12;i=-~i) for(rnt j=i+2;j<=14;j=-~j)
if(check3(i,j)){do3(i,j);dfs(x+1);undo3(i,j);}
else break;
for(rnt i=3;i<=13;i=-~i) for(rnt j=i+1;j<=14;j=-~j)
if(check4(i,j)){do4(i,j);dfs(x+1);undo4(i,j);}
else break;
for(rnt i=3;i<=15;i=-~i) if(check5(i)){do5(i);dfs(x+1);undo5(i);}
for(rnt i=3;i<=15;i=-~i) if(check5(i)){
for(rnt j=3;j<=17;j=-~j) if(check6(i,j)){
do6(i,j);dfs(x+1);undo6(i,j);
if(check7(i,j)){do7(i,j);dfs(x+1);undo7(i,j);}
}
}
for(rnt i=3;i<=15;i=-~i) if(check8(i)){
for(rnt p=3;p<=17;p=-~p) for(rnt q=p;q<=17;q=-~q) if(check9(i,p,q)){
do9(i,p,q);dfs(x+1);undo9(i,p,q);
if(check10(i,p,q)){do10(i,p,q);dfs(x+1);undo10(i,p,q);}
}
do8(i);dfs(x+1);undo8(i);
}
for(rnt i=3;i<=15;i=-~i) if(check11(i)){do11(i);dfs(x+1);undo11(i);}
if(check12()){do12();dfs(x+1);undo12();}
int res=0;
for(rnt i=3;i<=17;i=-~i) res+=sum[i];
if(res+x<ans) ans=x+res;
}
inline bool check1(){
for(rnt i=3;i<=17;i=-~i) if(sum[i]) return false;
return true;
}
inline bool check2(int l,int r){
for(rnt i=l;i<=r;i=-~i) if(!sum[i]) return false;
return true;
}
inline void do2(int l,int r){
for(rnt i=l;i<=r;i=-~i) --sum[i];
}
inline void undo2(int l,int r){
for(rnt i=l;i<=r;i=-~i) sum[i]=-~sum[i];
}
inline bool check3(int l,int r){
for(rnt i=l;i<=r;i=-~i) if(sum[i]<2) return false;
return true;
}
inline void do3(int l,int r){
for(rnt i=l;i<=r;i=-~i) sum[i]-=2;
}
inline void undo3(int l,int r){
for(rnt i=l;i<=r;i=-~i) sum[i]+=2;
}
inline bool check4(int l,int r){
for(rnt i=l;i<=r;i=-~i) if(sum[i]<3) return false;
return true;
}
inline void do4(int l,int r){
for(rnt i=l;i<=r;i=-~i) sum[i]-=3;
}
inline void undo4(int l,int r){
for(rnt i=l;i<=r;i=-~i) sum[i]+=3;
}
inline bool check5(int x){return sum[x]>=3;}
inline void do5(int x){sum[x]-=3;}
inline void undo5(int x){sum[x]+=3;}
inline bool check6(int x,int y){
if(x==y) return false;
return sum[y];
}
inline void do6(int x,int y){sum[x]-=3;--sum[y];}
inline void undo6(int x,int y){sum[x]+=3;sum[y]=-~sum[y];}
inline bool check7(int x,int y){
if(x==y) return false;
return sum[y]>=2;
}
inline void do7(int x,int y){sum[x]-=3;sum[y]-=2;}
inline void undo7(int x,int y){sum[x]+=3;sum[y]+=2;}
inline bool check8(int x){return sum[x]==4;}
inline void do8(int x){sum[x]=0;}
inline void undo8(int x){sum[x]=4;}
inline bool check9(int x,int y,int z){
if(x==y || x==z) return false;
if(y==z) return sum[y]>=2;
return sum[y] && sum[z];
}
inline void do9(int x,int y,int z){sum[x]=0;--sum[y];--sum[z];}
inline void undo9(int x,int y,int z){sum[x]=4;sum[y]=-~sum[y];sum[z]=-~sum[z];}
inline bool check10(int x,int y,int z){
if(x==y || x==z) return false;
if(y==z) return sum[y]==4;
return sum[y]>=2 && sum[z]>=2;
}
inline void do10(int x,int y,int z){sum[x]=0;sum[y]-=2;sum[z]-=2;}
inline void undo10(int x,int y,int z){sum[x]=4;sum[y]+=2;sum[z]+=2;}
inline bool check11(int x){return sum[x]>=2;}
inline void do11(int x){sum[x]-=2;}
inline void undo11(int x){sum[x]+=2;}
inline bool check12(){return sum[16] && sum[17];}
inline void do12(){sum[16]=0;sum[17]=0;}
inline void undo12(){sum[16]=1;sum[17]=1;}
inline bool check13(int x){return sum[x];};
inline void do13(int x){--sum[x];}
inline void undo13(int x){sum[x]=-~sum[x];}