P4907 A换B problem

· · 题解

题意：

给定一副扑克牌，其中部分牌已经被移除。现在需要从剩下的牌中选出四个区间，每个区间内的牌都是同一花色且点数连续。

如果可以选出这样四个区间，则输出 Yes，否则输出 No。

如果输出 No，再输出最少需要添加多少张牌才能满足要求。

思路：

先考虑一下暴力，即记录一下每一张牌，枚举它换成另外三副牌的情况（同时可以不换），搜完之后回溯一下。

想一下怎么判断是连续的一副牌，可以对于一种类型的牌，找一下点数最小的牌和点数最大的牌，因为要连续，所以两者之间所有点数的牌都需要有，没有的话就不是顺子。

如果是 No 的话我们考虑怎么才可以得到顺子的最少需要牌数，其实可以在判断这个是否是顺子的时候，记录一下一种类型的牌最大点数与最小点数之间差的牌，这样找差的牌就可以了。

这样，我们就愉快的可以得到六十分了。

于是，我就想试试卡常，一卡，直接就过了，将程序的运行时间强制放在一秒以内，直接输出现在的当前累积的答案……（就相当于当前时间内计算的答案可能就是最终的答案）

数据加强了踢一下我，我改一个剪枝的……

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=60,M=20;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
struct Node{
    ll x,y;
}a[N];
ll n,x,y,K,ans=INT_MAX,vum=INT_MAX;
char k[2];
bool f[5][M];
bool check(){
    register ll h=0;
    register bool k=1;
    for(register int i=1;i<=4;i++){
        register ll Min=15,Max=0;
        for(register ll j=1;j<=13;j++){
            if(f[i][j]){
                Min=j;
                break;
            }
        }
        for(register ll j=13;j>=1;j--){
            if(f[i][j]){
                Max=j;
                break;
            }
        }
        for(register int j=Min;j<=Max;j++)
          if(!f[i][j]) 
            k=0,h++;
    }
    vum=min(vum,h);
    return k;
}
void dfs(register ll pos,register ll sum){
    if(sum>=ans)
      return ;
    if(check()){
        ans=min(ans,sum);
        return ;
    }
    if(pos>n)
      return ;
    if((clock()-K)*1000>=200*CLOCKS_PER_SEC){
        if(ans<=52){
            puts("Yes");
            write(ans);
        }
        else{
            puts("No");
            write(vum);
        }
        exit(0);
    }
    for(register int i=1;i<=4;i++){
        if(f[i][a[pos].y]&&i!=a[pos].x)
          continue;
        f[a[pos].x][a[pos].y]=0;
        f[i][a[pos].y]=1;
        if(i!=a[pos].x)
          dfs(pos+1,sum+1);
        else
          dfs(pos+1,sum);
        f[i][a[pos].y]=0;
        f[a[pos].x][a[pos].y]=1;
    }
}
int main(){
    n=read();
    for(register int i=1;i<=n;i++){
        x=read();
        scanf("%s",&k);
        if(k[0]=='A')
          y=1;
        else if(k[0]=='J')
          y=11;
        else if(k[0]=='Q')
          y=12;
        else if(k[0]=='K')
          y=13;
        else if(k[0]=='1'&&k[1]=='0')
          y=10;
        else
          y=k[0]-'0';
        a[i].x=x,a[i].y=y;
    }
    for(register int i=1;i<=n;i++)
      f[a[i].x][a[i].y]=1;
    K=clock();
    dfs(1,0);
    if(ans<=52){
        puts("Yes");
        write(ans);
    }
    else{
        puts("No");
        write(vum);
    }
    return 0;
}