萌新刚学OI一秒
查看原帖
萌新刚学OI一秒
118382
torque楼主2019/11/3 20:26

求卡常,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];}
2019/11/3 20:26
加载中...