歷年NOIP中的搜索題

来源:http://www.cnblogs.com/fenghaoran/archive/2017/07/12/7158038.html
-Advertisement-
Play Games

什麼題目都不會做於是開始做搜索題。 然而我搜索題也不會做了。 鐵定沒戲的蒟蒻。 1.NOIP2004 蟲食算 “對於給定的N進位加法算式，求出N個不同的字母分別代表的數字，使得該加法算式成立。輸入數據保證有且僅有一組解”。 大概就是給你一堆(n個)字母讓你求出n進位下的一個n位數加n位數得到n位數的 ...


什麼題目都不會做於是開始做搜索題。

然而我搜索題也不會做了。

鐵定沒戲的蒟蒻。

 

1.NOIP2004 蟲食算

　　“對於給定的N進位加法算式，求出N個不同的字母分別代表的數字，使得該加法算式成立。輸入數據保證有且僅有一組解”。

　　大概就是給你一堆(n個)字母讓你求出n進位下的一個n位數加n位數得到n位數的唯一解(允許有前導0)。　　

　　千算萬算沒算到最大的優化是從大到小枚舉數字

　　反正頂多26位，個位開始爆搜2333。

　　幾個比較重要的剪枝：

　　當前列不可能滿足立即退出。

　　一列三個數，知二推一。

　　當前答案與之前衝突立即退出。

　　然後枚舉的時候從n枚舉到1。

　　過了。

　　可能寫得稍微那麼醜了一點？

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define rg register
#define ls (x << 1)
#define rs (x << 1 | 1)
#define MID int mid=(l+r)>>1
using namespace std;
 
const int N = 110;
int fac[N],In[N],n,D[N];
char A[N],B[N],C[N];
 
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
 
inline char gc()
{
  char ch=getchar();
  while(ch>'Z' || ch<'A')ch=getchar();
  return ch;
}
 
inline int F(rg char ch){return int(ch-'A'+1);}
 
inline void Congratulations()
{
  for(rg int i=1;i<=n;++i)
    printf("%d ",fac[i]);
  exit(0);
}
 
inline void dfs(rg int dep,rg int line)
{
  if(line==1){
    rg char ch=A[dep];rg int f=F(ch);
    if(fac[f]!=-1)dfs(dep,2);
    else
      for(rg int i=n-1;i>=0;--i)
	if(!In[i]){
	  fac[f]=i;In[i]=1;
	  dfs(dep,2);
	  fac[f]=-1;In[i]=0;
	}
    return;
  }
  else if(line==2){
    rg char ch=B[dep];rg int f=F(ch);
    if(fac[f]!=-1)dfs(dep,3);
    else{
      rg int f1=F(A[dep]),f3=F(C[dep]);
      rg int sum=fac[f1]+D[dep];
      if(fac[f3]!=-1){
	int x=fac[f3]-sum;
	while(x<0)x=x+n;
	if(!In[x]){
	  fac[f]=x;In[x]=1;
	  dfs(dep,3);
	  fac[f]=-1;In[x]=0;
	}
      }
      else
	for(rg int i=n-1;i>=0;--i)
	  if(!In[i]){
	    fac[f]=i;In[i]=1;
	    dfs(dep,3);
	    fac[f]=-1;In[i]=0;
	  }
    }
    return;
  }
  else{
    rg char ch=C[dep];rg int f=F(ch);
    rg int sum=fac[F(A[dep])]+fac[F(B[dep])]+D[dep],ssum=sum-n;
    if(fac[f]!=-1){
      if(fac[f]!=sum && fac[f]!=ssum)return;
      else{
	if(sum>=n && dep==1)return;
	if(dep==1)Congratulations();
	D[dep-1]=sum>=n;dfs(dep-1,1);
      }
    }
    else{
      if(sum>=n){
	if(dep==1)return;
	if(!In[ssum]){
	  D[dep-1]=1;
	  fac[f]=ssum;
	  In[ssum]=1;
	  dfs(dep-1,1);
	  In[ssum]=0;
	  fac[f]=-1;
	}
	else return;
      }
      else{
	if(!In[sum]){
	  if(dep==0)Congratulations();
	  D[dep-1]=0;fac[f]=sum;In[sum]=1;
	  dfs(dep-1,1);
	  In[sum]=0;fac[f]=-1;
	}
	else return;
      }
    }
  }
}
 
inline void work()
{
  for(rg int i=1;i<=n;++i)fac[i]=-1;
  dfs(n,1);
}	
 
int main()
{
  n=gi();
  for(int i=1;i<=n;++i)A[i]=gc();
  for(int i=1;i<=n;++i)B[i]=gc();
  for(int i=1;i<=n;++i)C[i]=gc();
  work();
  return 0;
}

　　

 

2.NOIP2009靶形數獨

　　一個數獨每個方格都有一定的權Ai,j，給你一個不完全的數獨，定義數獨分數為所有方格的(方格內數和該方格權的積)的和，求分數最大的數獨，無解輸出-1。

　　

　　第一次打，直接從(1,1)枚舉到(9,9)，爆搜2333。

　　90分。

　　一筍乾就來了興趣，然後(觀察了一下數據)發現答案集中在其他三個角的時候跑的賊吉八慢。

　　把角落上的點的個數劃分個區域統計一下，從那個點開始爆搜。

　　於是過了。

　　不科學啊，複雜度是應該很高的啊... ...

　　反正大力出奇跡嘛。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
#define MID int mid=(l+r)>>1
using namespace std;
 
int map[21][21],bel[11][21][21],vis[21][21];
int In[21][21],In_1[21][21],In_2[21][21];
int point[]={0,6,7,8,9,10},Ans,f1,f2,f3,f4,fuc[21][21];
 
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
 
inline void TS()
{
  for(int i=1;i<=9;++i){
    for(int j=1;j<=9;++j)
      printf("%d ",vis[i][j]);
    printf("\n");
  }
}
 
inline void dfs(int x,int y,int nf,int tc,int kind)
{
  if(tc>=81){Ans=max(Ans,nf);return;}
  if(x<1 || y<1 || x>9 || y>9)return;
  if(map[x][y]){
    vis[x][y]=map[x][y];
    nf+=point[bel[2][x][y]]*map[x][y];
    if(kind==1){
      if(y==9)dfs(x+1,1,nf,tc+1,kind);
      else dfs(x,y+1,nf,tc+1,kind);
    }
    else if(kind==2){
      if(y==1)dfs(x+1,9,nf,tc+1,kind);
      else dfs(x,y-1,nf,tc+1,kind);
    }
    else if(kind==3){
      if(y==9)dfs(x-1,1,nf,tc+1,kind);
      else dfs(x,y+1,nf,tc+1,kind);
    }
    else if(kind==4){
      if(y==1)dfs(x-1,9,nf,tc+1,kind);
      else dfs(x,y-1,nf,tc+1,kind);
    }
    return;
  }
  int Bel=bel[1][x][y],pt=point[bel[2][x][y]];
  for(int i=9;i;--i){
    if(!In[Bel][i])
      if(!In_1[x][i])
	if(!In_2[y][i]){
	  vis[x][y]=i;
	  In[Bel][i]=1;
	  In_1[x][i]=1;
	  In_2[y][i]=1;
	  int fn=nf+pt*i;
	  if(kind==1){
	    if(y==9)dfs(x+1,1,fn,tc+1,kind);
	    else dfs(x,y+1,fn,tc+1,kind);
	  }
	  else if(kind==2){
	    if(y==1)dfs(x+1,9,fn,tc+1,kind);
	    else dfs(x,y-1,fn,tc+1,kind);
	  }
	  else if(kind==3){
	    if(y==9)dfs(x-1,1,fn,tc+1,kind);
	    else dfs(x,y+1,fn,tc+1,kind);
	  }
	  else if(kind==4){
	    if(y==1)dfs(x-1,9,fn,tc+1,kind);
	    else dfs(x,y-1,fn,tc+1,kind);
	  }
	  vis[x][y]=0;
	  In[Bel][i]=0;
	  In_1[x][i]=0;
	  In_2[y][i]=0;
	}
  }
}
 
int main()
{
  for(int i=1;i<=9;++i)
    for(int j=1;j<=9;++j)
      map[i][j]=gi();
  for(int i=1;i<=9;++i)
    for(int j=1;j<=9;++j){
      bel[1][i][j]=((i-1)/3)*3+((j-1)/3)+1;
      bel[2][i][j]=min(min(i,j),min(9-i+1,9-j+1));
    }
  for(int i=1;i<=9;++i)
    for(int j=1;j<=9;++j)
      if(map[i][j]){
	In[bel[1][i][j]][map[i][j]]=1;
	In_1[i][map[i][j]]=1;
	In_2[j][map[i][j]]=1;
      }
  for(int i=1;i<=9;++i)
    for(int j=1;j<=9;++j)
      if(map[i][j]){
	if(i<=5 && j<=5)f1++;
	if(i<=5 && j>=5)f2++;
	if(i>=5 && j<=5)f3++;
	if(i>=5 && j>=5)f4++;
      }
  if(f1>=f2 && f1>=f3 && f1>=f4)dfs(1,1,0,0,1);
  else if(f2>=f1 && f2>=f3 && f2>=f4)dfs(1,9,0,0,2);
  else if(f3>=f1 && f3>=f2 && f3>=f4)dfs(9,1,0,0,3);
  else dfs(9,9,0,0,4);
  printf("%d\n",Ans?Ans:-1);
  return 0;
}

　　

 

3.NOIP2010引水入城

　　一個矩形地帶，每個格子有高度。

　　最上面一行可以建蓄水廠，中間的可以建輸水站。

　　水只能從高處流向低處(平地不行)，只能從一個點流向有公共邊的點。

　　問最少要幾個蓄水廠才能使最後一行的城市都有水。無解輸出-1。

　　矩形最大是500×500的。

　　

　　首先很容易想到只在第一行的比左右都高的點修就可以了啊。

　　然後把這些點爆搜一遍看它能走到的最左邊和最右邊。

　　容易證明一個點能走到的一定是一條連續的線段，如果不是就可以-1了。

　　然後就是很經典的線段覆蓋區間問題。

　　貪心和DP都可以。我也搞不清是什麼方法。

　　處理這些線段先按左端點排序，然後開一個隊列，從左往右掃一遍。

　　如果當前線段覆蓋了上一條線段的"有用區間"(即相對上上個線段外的區間),就把上一個區間從隊列里去掉。

　　直到去不掉了就把這條線段加在隊列里。

　　如果被上一條覆蓋了，直接跳過算了。

　　如果沒覆蓋，就把這個線段加進隊列，進行下一波計算。

　　把細節卡好就差不多了，也不是什麼很難的題。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define rg register
using namespace std;
 
const int N = 510;
const int Inf = 1e6+7;
int n,m,high[N][N],L[N][N],R[N][N],Left[N],Right[N];
int st,ed=1,que[N],vis[N][N];
int gx[]={0,1,-1,0,0},gy[]={0,0,0,1,-1};
 
inline int gi()
{
  rg int x=0,res=1;rg char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
 
inline bool check(rg int x,rg int y,rg int h)
{
  if(x<1 || y<1 || x>n || y>m)return false;
  return h>high[x][y];
}
 
inline void dfs(rg int bel,rg int x,rg int y)
{
  if(L[x][y]!=m+1 && R[x][y]!=-1){
    Left[bel]=min(Left[bel],L[x][y]);
    Right[bel]=max(Right[bel],R[x][y]);
    return;
  }
  if(vis[x][y])return;vis[x][y]=1;
  for(int i=1;i<=4;++i)
    if(check(x+gx[i],y+gy[i],high[x][y])){
      dfs(bel,x+gx[i],y+gy[i]);
      L[x][y]=min(L[x][y],L[x+gx[i]][y+gy[i]]);
      R[x][y]=max(R[x][y],R[x+gx[i]][y+gy[i]]);
    }
  if(x==n){
    L[x][y]=min(y,L[x][y]!=m+1?L[x][y]:y);
    R[x][y]=max(y,R[x][y]!=0-1?R[x][y]:y);
  }
  Left[bel]=min(Left[bel]?Left[bel]:L[x][y],L[x][y]);
  Right[bel]=max(Right[bel]?Right[bel]:R[x][y],R[x][y]);
  return;
}
 
int main()
{
  n=gi();m=gi();
  for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j){
      L[i][j]=m+1;R[i][j]=-1;
      high[i][j]=gi();
    }
  high[n][0]=high[n][m+1]=-Inf;
  for(int i=1;i<=m;++i)
    Left[i]=m+1,Right[i]=-1,dfs(i,1,i);
  for(int i=1;i<=m;++i)
    if(L[n][i]>R[n][i])st++;
  if(st){printf("0\n%d\n",st);return 0;}
  
  st=1;ed=0;
  for(int i=1,last=1;i<=m;){
    if(high[1][i]<high[1][i+1]){++i;continue;}
    if(high[1][i]<high[1][i-1]){++i;continue;}
    if(Left[i]>Right[i]){++i;continue;}
    if(ed==0){
      que[++ed]=i;
      last=1;
      ++i;
      continue;
    }
    if(Left[i]<=last && Right[i]>=Right[que[ed]]){
      ed--;
      if(ed>1)last=Right[ed-1]+1;
      else last=1;
      continue;
    }
    else if(Left[i]>last){
      if(Right[i]>Right[que[ed]]){
	last=Right[que[ed]]+1;
	que[++ed]=i;
      }
      ++i;
    }
  }
  printf("1\n%d\n",ed);
  return 0;
}

　　

 

4.NOIP2013華容道

　　給你一個華容道圖，裡面的小格子都是1×1的，有些小格子可以移動，有一個空格。

　　每一次移動操作需要的時間為1，問把一個指定塊移到一個指定區域的最小時間。

　　Q次詢問。矩形最大是30*30，Q最大是500

　　大概花了個二十分鐘就寫了個能鬼到65的BFS。有人說優化一下狀態可以搞到80。

　　然後開始想正解，發現完全沒什麼戲。於是去%了一下，經過一番鄙視和提點之後開始了漫長的征途。

　　首先預處理出，從一個點的上下左右到上下左右，不經過這個點的最短路。

　　可以固定住這個點，視為不可移動狀態，然後處理。

　　然後把空格移到起始點，然後把起始點移到終點。

　　用SPFA維護，大概要開三維狀態，(x,y)和方向(上下左右)。

　　OI界的毒瘤一顆。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
#define MID int mid=(l+r)>>1
using namespace std;
 
const int N = 31;
struct Data{int x,y,from;};
struct Dot{int x,y;};
int n,m,Q,map[N][N],Ex,Ey,Sx,Sy,Tx,Ty;
int Gx[]={0,0,1,0,-1},Gy[]={0,1,0,-1,0};
int far[N][N][5][5],vis[N][N][5],dis[N][N][5];
 
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
 
inline bool check(int x,int y)
{
  if(x<1 || y<1 || x>n || y>m)return false;
  return map[x][y];
}
 
inline int fc(int x)
{
  if(x!=2)return (x+2)%4;
  return 4;
}
 
inline int BFS(int fx,int fy,int tx,int ty)
{
  int Vis[N][N],dep[N][N];
  memset(Vis,0,sizeof(Vis));
  memset(dep,127,sizeof(dep));
  queue<Dot>Q;Q.push((Dot){fx,fy});
  Vis[fx][fy]=1;dep[fx][fy]=0;
  while(!Q.empty()){
    Dot now=Q.front();Q.pop();
    int x=now.x,y=now.y;Vis[x][y]=0;
    for(int i=1;i<=4;++i)
      if(check(x+Gx[i],y+Gy[i]))
	if(dep[x][y]+1<dep[x+Gx[i]][y+Gy[i]]){
	  int xx=x+Gx[i],yy=y+Gy[i];
	  dep[xx][yy]=dep[x][y]+1;
	  if(!Vis[xx][yy]){
	    Vis[xx][yy]=1;
	    Q.push((Dot){xx,yy});
	  }
	}
  }
  return dep[tx][ty]==dep[0][0]?far[0][0][0][0]:dep[tx][ty];
}
 
inline void prepare()
{
  memset(far,127,sizeof(far));
  for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
      if(map[i][j]){
		map[i][j]=0;
		for(int k=1;k<=4;++k)
	  		if(check(i+Gx[k],j+Gy[k]))
	    		for(int l=1;l<=4;++l)
	      			if(check(i+Gx[l],j+Gy[l]))
						if(k!=l)
						  far[i][j][k][l]=BFS(i+Gx[k],j+Gy[k],i+Gx[l],j+Gy[l]);
						else far[i][j][k][l]=0;
		map[i][j]=1;
      }
}
 
inline void solve()
{
  if(check(Ex,Ey) && check(Sx,Sy) && check(Tx,Ty));
  else{printf("-1\n");return;}
  memset(vis,0,sizeof(vis));
  memset(dis,127,sizeof(dis));
  for(int i=1;i<=4;++i)
  	vis[Sx][Sy][i]=1,dis[Sx][Sy][i]=0;
  queue<Data>Q;map[Sx][Sy]=0;
  for(int i=1;i<=4;++i)
  	if(check(Sx+Gx[i],Sy+Gy[i])){
  		int d=BFS(Ex,Ey,Sx+Gx[i],Sy+Gy[i]);
  		if(d<far[0][0][0][0]){
  			dis[Sx+Gx[i]][Sy+Gy[i]][fc(i)]=d+1;
  			vis[Sx+Gx[i]][Sy+Gy[i]][fc(i)]=1;
  			Q.push((Data){Sx+Gx[i],Sy+Gy[i],fc(i)});
  		}
  	}
  map[Sx][Sy]=1;
  while(!Q.empty()){
  	Data now=Q.front();Q.pop();
  	int x=now.x,y=now.y,from=now.from;
  	vis[x][y][from]=0;
  	for(int i=1;i<=4;++i)
  		if(check(x+Gx[i],y+Gy[i])){
  			int xx=x+Gx[i],yy=y+Gy[i];
  			int dt=far[x][y][from][i];
  			if(dis[x][y][from]+dt+1<dis[xx][yy][fc(i)]){
  				dis[xx][yy][fc(i)]=dis[x][y][from]+dt+1;
  				if(!vis[xx][yy][fc(i)]){
  					Q.push((Data){xx,yy,fc(i)});
  					vis[xx][yy][fc(i)]=1;
  				}
  			}
  		}
  }
  int ans=dis[0][0][0];
  for(int i=1;i<=4;++i)ans=min(ans,dis[Tx][Ty][i]);
  if(ans==dis[0][0][0])printf("-1\n");
  else printf("%d\n",ans);
}
 
int main()
{
  n=gi();m=gi();Q=gi();
  for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
      map[i][j]=gi();
  prepare();
  while(Q--){
    Ex=gi();Ey=gi();
    Sx=gi();Sy=gi();
    Tx=gi();Ty=gi();
    if(Sx==Tx && Sy==Ty){
      printf("0\n");
      continue;
    }
    solve();
  }
  return 0;
}

　　

5.NOIP2015鬥地主

　　給你幾張牌，給你一些規則，問你這些牌最少幾步打完。牌數不超過23張。

 

一個剪枝：先把四帶、三帶等打完，粗略計算答案上界。

我也不知道為什麼要先帶掉單個的。

然後就是很簡單的爆搜2333了。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
#define MID int mid=(l+r)>>1
using namespace std;

int bin[21],Ans,n,T;

int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline bool check_UP()
{
  for(int i=1;i<=14;++i)
    if(bin[i])return false;
  return true;
}

inline void dfs(int step)
{
  if(step>=Ans)return;
  if(check_UP()){Ans=step;return;}
  
  int s1,s2,s3,s4;s1=s2=s3=s4=0;
  for(int i=1;i<=14;++i){
    if(bin[i]==1)++s1;
    if(bin[i]==2)++s2;
  }

  for(int i=1;i<=13;++i)
    if(bin[i]==4){
      s4++;
      if(s1>=2)s1-=2;
      else if(s2>=2)s2-=2;
      else s1--;
    }
  for(int i=1;i<=13;++i)
    if(bin[i]==3){
      s3++;
      if(s1)s1--;
      else if(s2)s2--;
    }
  Ans=min(Ans,step+s1+s2+s3+s4);
  
  //三順子！
  for(int i=1;i<=11;++i)
    if(bin[i]>=3 && bin[i+1]>=3){
      int j=i+2;
      bin[i]-=3;bin[i+1]-=3;
      dfs(step+1);
      while(bin[j]>=3 && j<=12)bin[j]-=3,dfs(step+1),++j;
      for(int k=i;k<j;++k)bin[k]+=3;
    }
  //Congratulations!
  
  //雙順子！
  for(int i=1;i<=10;++i)
    if(bin[i]>=2 && bin[i+1]>=2 && bin[i+2]>=2){
      int j=i+3;
      bin[i]-=2;bin[i+1]-=2;bin[i+2]-=2;
      dfs(step+1);
      while(bin[j]>=2 && j<=12)bin[j]-=2,dfs(step+1),++j;
      for(int k=i;k<j;++k)bin[k]+=2;
    }
  //Congratulations!
  
  //單順子！
  for(int i=1;i<=8;++i)
    if(bin[i]>=1 && bin[i+1]>=1 && bin[i+2]>=1 && bin[i+3]>=1 && bin[i+4]>=1){
      int j=i+5;
      bin[i]--;bin[i+1]--;bin[i+2]--;bin[i+3]--;bin[i+4]--;
      dfs(step+1);
      while(bin[j]>=1 && j<=12)bin[j]--,dfs(step+1),++j;
      for(int k=i;k<j;++k)bin[k]++;
    }
  //Congratulations!
  
  /*
  //四帶一/二！
  for(int i=1;i<=13;++i)
    if(bin[i]==4){
      bin[i]-=4;
      for(int j=1;j<=14;++j)
	if(bin[j]>=2)
	  for(int k=1;k<=14;++k)
	    if(bin[k]>=2){
	      bin[j]-=2;bin[k]-=2;
	      dfs(step+1);
	      bin[j]+=2;bin[k]+=2;
	    }
      for(int j=1;j<=14;++j)
	if(bin[j]>=1)
	  for(int k=1;k<=14;++k)
	    if(bin[k]>=1){
	      bin[j]-=1;bin[k]-=1;
	      dfs(step+1);
	      bin[j]+=1;bin[k]+=1;
	    }
      bin[i]+=4;
    }
  //Congratulations!
  
  //三帶二！
  for(int i=1;i<=13;++i)
    if(bin[i]>=3){
      bin[i]-=3;
      for(int j=1;j<=14;++j)
	if(bin[j]>=2){
	  bin[j]-=2;
	  dfs(step+1);
	  bin[j]+=2;
	}
      bin[i]+=3;
    }
  //Congratulations!
  
  //三帶一！（附炸彈）
  for(int i=1;i<=13;++i)
    if(bin[i]>=3){
      bin[i]-=3;
      for(int j=1;j<=14;++j)
	if(bin[j]>=1){
	  bin[j]-=1;
	  dfs(step+1);
	  bin[j]+=1;
	}
      bin[i]+=3;
    }
  //Congratulations!
  
  //三張牌！
  for(int i=1;i<=13;++i)
    if(bin[i]>=3){bin[i]-=3;dfs(step+1);bin[i]+=3;}
  //Congratulations!
  
  //對子牌！
  for(int i=1;i<=14;++i)
    if(bin[i]>=2){bin[i]-=2;dfs(step+1);bin[i]+=2;}
  //Congratulations!

  //單張！
  for(int i=1;i<=14;++i)
    if(bin[i]==1){bin[i]-=1;dfs(step+1);bin[i]+=1;}
  //Congratulations!
  */
}

int main()
{
  scanf("%d%d",&T,&n);
  while(T--){
    memset(bin,0,sizeof(bin));Ans=n;
    for(int i=1;i<=n;++i){
      int x=gi();gi();
      if(x==0)bin[14]++;
      else if(x==1 || x==2)bin[x+11]++;
      else bin[x-2]++;
    }
    dfs(0);
    printf("%d\n",Ans);
  }
  return 0;
}

　　


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • P1421 小玉買文具
    題目描述 班主任給小玉一個任務，到文具店裡買儘量多的簽字筆。已知一隻簽字筆的價格是1元9角，而班主任給小玉的錢是a元b角，小玉想知道，她最多能買多少只簽字筆呢。 輸入輸出格式 輸入格式： 輸入的數據，在一行內，包括兩個整數，依次表示a和b，a<=10000,b<=9。 輸出格式： 輸出一個整數，表示 ...
  • php獲取'/'傳參的值
    通過輸出$GLOBALS可以看到'/'後的參數都存在於$_SERVER['PATH_INFO']里； 聲明一個數組來獲取我們在'/'後傳遞的參數 $arr = explode('/', $_SERVER['PATH_INFO']); //print_r($arr)查看詳細信息 ...
  • python新手之一環境安裝
    今天開始學習python，首先環境安裝 1.在https://www.python.org/downloads/下載python2.X或者3.X（ps：這裡建議下載32位的python ，因為64位python開發出來的程式，打包成 EXE程式後會不相容32位系統） 2.下載之後安裝，打開安裝包 2 ...
  • JDBC相關知識
    一、連接資料庫 1. 步驟 2. 獲取Driver的方式 通過new新建 ：Driver driver = new com.mysql.jdbc.Driver(); 通過反射創建類的實例 ：Driver driver = (Driver)Class.forName(driverClass).newI ...
  • Python 之 filecmp
    Python 之 filecmp 2017年7月12日 參考書籍:《Python自動化運維 ——技術與最佳實踐》 作者:李天斯 1.什麼是filecmp filecmp作為python的標準庫，無需安裝，作用是對文件，目錄，遍歷子目錄的差異對比功能，它是一個輕量級的工具，在對linux伺服器備份文件 ...
  • Thymeleaf：訪問Spring中的bean
    項目做了動靜分離，即靜態文件全部放在nginx中，動態文件在tomcat中，如何引用靜態文件，我是這麼做的，見下： 運行結果： ...
  • [flask/python/web]學習flask web開發(Miguel著)遇到的一些問題及其解決方案
    今天解決了第11章_不顯示博文表單的問題，時間太晚了，先留個坑，明天寫出詳細的解決方案。 同時也將前11章（當我結束本書學習時會將所有的問題一一列出並給出中文的解決方案）的常見問題給予解答。 ...
  • 01Python內置函數_集合操作類
    basestring basestring() 說明：basestring是str和unicode的超類（父類），也是抽象類， 因此不能被調用和實例化，但可以被用來判斷一個對象是否為str或者unicode的實例， isinstance(obj, basestring) 等價於isinstance( ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類