写了 114514s 的斗地主,WA 82,我的输出比正解大,看了114514s 没看出问题,求调玄关。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pint pair<int,int>
#define f first
#define s second
#define mp make_pair
#define aF(begin,end,step,name) for(int name=begin;name<=end;name+=step)
#define oF(B,E,N) aF(B,E,1,N)
#define af(B,E,S) aF(B,E,S,i)
#define of(B,E) af(B,E,1)
#define tF(E,N) oF(1,E,N)
#define tf(E) of(1,E)
#define nF(N) tF(n,N)
#define nf() tf(n)
#define mF(N) tF(m,N)
#define mf() tf(m)
#define GF(x,ep) for(int ep=h[x];ep;ep=nxt[ep])
#define Gf(x) GF(x,ep)
#define gF(ep) GF(x,ep)
#define gf() Gf(x)
//#define X 2147483647
#define file(x) (freopen(#x".in","r",stdin),freopen(#x".out","w",stdout))
#define READ(x) (file(x),read())
#define Read(x) (freopen(#x".in","r",stdin),read())
inline ll read(){
ll x=0;
short f=1;
char c=getchar();
while(c>57||c<48){
if(c==45) f=-1;
c=getchar();
}
while(c<58&&c>47){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline ll readf(int T){
ll x=0;
short f=1;
char c=getchar();
while(c>57||c<48){
if(c==45) f=-1;
c=getchar();
}
while(c<58&&c>47){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
x*=T;
if(c^'.') return x*f;
c=getchar();
while(c<58&&c>47){
x+=(c^48)*(T/=10);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0ll) putchar(45),x=~x+1;
if(x>9ll) write(x/10);
putchar(x%10|48);
}
inline void writen(ll x,int w){
if(w>1) writen(x/10,w-1);
putchar(x%10|48);
}
inline void writeb(ll x,int base=10){
if(x<0ll) putchar(45),x=~x+1;
if(x>=base) writeb(x/base,base);
putchar(x%base|48);
}
inline void writebn(ll x,int w,int base=10){
if(w>1) writebn(x/base,w-1,base);
putchar(x%base|48);
}
inline char gtch(){
char c=getchar();
while(c<33) c=getchar();
return c;
}
int T=read(),n=read();
int c[20];
int C[5];
int A[24][13][8][6];
int count(){
tf(4)C[i]=0;
tf(15)if(c[i])C[c[i]]++;
// tf(15)write(c[i]),putchar(32);printf("-->");tf(4)write(C[i]),putchar(32);printf("-->");write(A[C[1]][C[2]][C[3]][C[4]]);putchar(10);
return c[14]&&c[15]?min(A[C[1]][C[2]][C[3]][C[4]],A[C[1]-2][C[2]][C[3]][C[4]]+1):A[C[1]][C[2]][C[3]][C[4]];
}
int getdfs(){
int ans=count();
for(int i=1,nxt;i<=8;i=nxt+1){
nxt=i;
if(!c[i])continue;
c[i]--;
while(c[nxt+1]&&nxt<12){
c[++nxt]--;
if(nxt-i>=4)ans=min(ans,getdfs()+1);
}
oF(i,nxt,j)c[j]++;
}
for(int i=1,nxt;i<=10;i=nxt+1){
nxt=i;
if(c[i]<2)continue;
c[i]-=2;
while(c[nxt+1]>=2&&nxt<12){
c[++nxt]-=2;
if(nxt-i>=2)ans=min(ans,getdfs()+1);
}
oF(i,nxt,j)c[j]+=2;
}
for(int i=1,nxt;i<=11;i=nxt+1){
nxt=i;
if(c[i]<3)continue;
c[i]-=3;
while(c[nxt+1]>=3&&nxt<12){
c[++nxt]-=3;
if(nxt-i>=1)ans=min(ans,getdfs()+1);
}
oF(i,nxt,j)c[j]+=3;
}
return ans;
}
void solve(){
tf(15)c[i]=0;
nf(){
int x=read();
if(x>=3) x-=(read(),2);
else if(!x) x=(13+read());
else x+=(read(),11);
c[x]++;
}
write(getdfs());putchar(10);
}
signed main(){
tf(23) A[i][0][0][0]=i;
for(int sum=1;sum<=23;sum++){
for(int i=0;i*4<=sum;i++){
for(int j=0;j*3+i*4<=sum;j++){
for(int k=!(i|j);k*2+j*3+i*4<=sum;k++){
int l=sum-(k*2+j*3+i*4);
// if(l>15) continue;
A[l][k][j][i]=l+k+j+i;
if(l) A[l][k][j][i]=min(A[l][k][j][i],A[l-1][k][j][i]+1);//1
if(k) A[l][k][j][i]=min(A[l][k][j][i],A[l+1][k-1][j][i]+1);//1
if(j) A[l][k][j][i]=min(A[l][k][j][i],A[l][k+1][j-1][i]+1);//1
if(i) A[l][k][j][i]=min(A[l][k][j][i],A[l][k][j+1][i-1]+1);//1
if(k) A[l][k][j][i]=min(A[l][k][j][i],A[l][k-1][j][i]+1);//2
if(j) A[l][k][j][i]=min(A[l][k][j][i],A[l+1][k][j-1][i]+1);//2
if(i) A[l][k][j][i]=min(A[l][k][j][i],A[l][k+1][j][i-1]+1);//2
if(j) A[l][k][j][i]=min(A[l][k][j][i],A[l][k][j-1][i]+1);//3
if(i) A[l][k][j][i]=min(A[l][k][j][i],A[l+1][k][j][i-1]+1);//3
if(i) A[l][k][j][i]=min(A[l][k][j][i],A[l][k][j][i-1]+1);//4
if(i&&k>=2) A[l][k][j][i]=min(A[l][k][j][i],A[l][k-2][j][i-1]+1);//4-2-2
if(i&&k&&j) A[l][k][j][i]=min(A[l][k][j][i],A[l+1][k-1][j-1][i-1]+1);//4-2-2
if(i&&j>=2) A[l][k][j][i]=min(A[l][k][j][i],A[l+2][k][j-2][i-1]+1);//4-2-2
if(i>=2) A[l][k][j][i]=min(A[l][k][j][i],A[l][k][j][i-2]+1);//4-2-2
if(i>=2&&j) A[l][k][j][i]=min(A[l][k][j][i],A[l+1][k+1][j-1][i-2]+1);//4-2-2
if(i&&l>=2) A[l][k][j][i]=min(A[l][k][j][i],A[l-2][k][j][i-1]+1);//4-1-1
if(i&&k) A[l][k][j][i]=min(A[l][k][j][i],A[l][k-1][j][i-1]+1);//4-1-1
if(i&&j) A[l][k][j][i]=min(A[l][k][j][i],A[l+1][k][j-1][i-1]+1);//4-1-1
if(i>=2) A[l][k][j][i]=min(A[l][k][j][i],A[l][k+1][j][i-2]+1);//4-1-1
if(i>=2&&l) A[l][k][j][i]=min(A[l][k][j][i],A[l-1][k][j+1][i-2]+1);//4-1-1
if(i>=2&&k) A[l][k][j][i]=min(A[l][k][j][i],A[l+1][k-1][j+1][i-2]+1);//4-1-1
if(i&&j&&l) A[l][k][j][i]=min(A[l][k][j][i],A[l-1][k+1][j-1][i-1]+1);//4-1-1
if(j&&k) A[l][k][j][i]=min(A[l][k][j][i],A[l][k-1][j-1][i]+1);//3-2
if(i&&k) A[l][k][j][i]=min(A[l][k][j][i],A[l+1][k-1][j][i-1]+1);//3-2
if(j>=2) A[l][k][j][i]=min(A[l][k][j][i],A[l+1][k][j-2][i]+1);//3-2
if(i&&j) A[l][k][j][i]=min(A[l][k][j][i],A[l][k+1][j-1][i-1]+1);//3-2
if(i>=2) A[l][k][j][i]=min(A[l][k][j][i],A[l+1][k+1][j][i-2]+1);//3-2
if(j&&l) A[l][k][j][i]=min(A[l][k][j][i],A[l-1][k][j-1][i]+1);//3-1
if(j&&k) A[l][k][j][i]=min(A[l][k][j][i],A[l+1][k-1][j-1][i]+1);//3-1
if(j>=2) A[l][k][j][i]=min(A[l][k][j][i],A[l][k+1][j-2][i]+1);//3-1
// printf("%d: %d %d %d %d:%d\n",sum,l,k,j,i,A[l][k][j][i]);
}
}
}
}
tf(T)solve();
}
代码解释:
A[x][y][z][w]:将 x 种只有一个相同的牌,y 种只有两个相同的牌,z 种只有三个相同的牌,w 种只有四个相同的牌在不用顺子/双顺子(连对)/三顺子(飞机)/王炸要多少次。
count:计算当前在不用顺子/双顺子(连对)/三顺子(飞机)要多少次。
c[x]:编号为 x 的牌有几张,其中 3~13(K)为1~11,1(A):12,2:13,小王:14,大王:15。