题解 P4907 【A换B problem】

引领天下 · 2018-10-23 21:51:35 · 题解

出题人来写一发题解

此题主要就是搜索，为了提升难度，我还搞了一个恶心的读入

接下来就是搜索了。

具体码里说吧。

#include <bits/stdc++.h>
using namespace std;
bool a[5][14];
int ans,p,k,n,i,ant;
char ch;
string st;
bool bb;
bool check() {
    int i,j,t;
    bool b;
    for (j=1; j<=4; j++) {
        t=0;
        b=false;
        for (i=1; i<=k; i++)if (a[j][i])t++;
        i=0;
        if (t==1||t==13)continue;
        while (i<k) {
            i++;
            if (t==0)break;
            if (a[j][i]) {
                t--;
                if (b) continue;
                else b=true;
            } else if (b)return false;
            else continue;
        }
    }
    return true;
}//判断是否连续（即换完后是否可行）
void check2() {
    int i,j,t,y;
    bool b;
    y=0;
    for (j=1; j<=4; j++) {
        t=0;
        for (i=1; i<=k; i++)if (a[j][i])t++;
        i=0;
        if (t==0||t==13||t==1) continue;
        b=false;
        while (i<k) {
            i++;
            if (t==0) break;
            if (a[j][i]) {
                t--;
                if (b) continue;
                else b=true;
            } else if (b)y++;
            else continue;
        }
    }
    if (y<ant) ant=y;
}//同上，另一个判断
void search(int q,int b) {
    int i,j,o,y[5],w[5];
    if (q==k+1) {
        if (check()) {
            bb=true;
            if (ans>b) ans=b;
        }
        if (!bb) check2();
        return ;
    }
    search(q+1,b);
    j=0;
    for (i=1; i<=4; i++)
        if (a[i][q]) {
            j++;
            y[j]=i;
        } else {
            w[i-j]=i;
        }
    if (j==4||j==0)return ;
    if (j==1||j==3) {
        if (j==3) {
            for (o=1; o<=3; o++) {
                if (a[i][j+1]&&a[i][j-1])continue;
                if (!(a[o][j+1]||a[o][j-1]))continue;
                a[w[1]][q]=true;
                a[y[o]][q]=false;
                search(q+1,b+1);
                a[w[1]][q]=false;
                a[y[o]][q]=true;
            }
        }
        if (j==1) {
            for (o=1; o<=3; o++) {
            if (a[i][j+1]&&a[i][j-1])continue;
            //if (!(a[o][j+1]||a[o][j-1]))continue;
                a[w[o]][q]=true;
                a[y[1]][q]=false;
                search(q+1,b+1);
                a[w[o]][q]=false;
                a[y[1]][q]=true;
            }
        }
    } else {
        for (o=1; o<=2; o++) {
            if (a[i][j+1]&&a[i][j-1])continue;
            if (!(a[o][j+1]||a[o][j-1]))continue;
            a[w[o]][q]=true;
            a[y[1]][q]=false;
            search(q+1,b+1);
            a[w[o]][q]=false;
            a[y[1]][q]=true;
            a[w[o]][q]=true;
            if (a[i][j+1]&&a[i][j-1])continue;
            if (!(a[o][j+1]||a[o][j-1]))continue;
            a[y[2]][q]=false;
            search(q+1,b+1);
            a[w[o]][q]=false;
            a[y[2]][q]=true;
        }
        a[w[1]][q]=true;
        a[y[1]][q]=false;
        a[w[2]][q]=true;
        a[y[2]][q]=false;
        search(q+1,b+2);
        a[w[1]][q]=false;
        a[y[1]][q]=true;
        a[w[2]][q]=false;
        a[y[2]][q]=true;
    }
}//搜索，具体过程就是分类讨论，对每个牌的编号+1、-1进行搜索
int main() {
    cin>>n;
    for (i=1; i<=n; i++) {
        cin>>p>>st;
        if (st=="A") {
            a[p][1]=true;
            if (1>k)k=1;
        }
        if (st=="2") {
            a[p][2]=true;
            if (2>k)k=2;
        }
        if (st=="3") {
            a[p][3]=true;
            if (3>k)k=3;
        }
        if (st=="4") {
            a[p][4]=true;
            if (4>k)k=4;
        }
        if (st=="5") {
            a[p][5]=true;
            if (5>k)k=5;
        }
        if (st=="6") {
            a[p][6]=true;
            if (6>k)k=6;
        }
        if (st=="7") {
            a[p][7]=true;
            if (7>k)k=7;
        }
        if (st=="8") {
            a[p][8]=true;
            if (8>k)k=8;
        }
        if (st=="9") {
            a[p][9]=true;
            if (9>k)k=9;
        }
        if (st=="10") {
            a[p][10]=true;
            if (10>k)k=10;
        }
        if (st=="J") {
            a[p][11]=true;
            if (11>k)k=11;
        }
        if (st=="Q") {
            a[p][12]=true;
            if (12>k)k=12;
        }
        if (st=="K") {
            a[p][13]=true;
            if (13>k)k=13;
        }//鬼畜的读入
    }
    ans=255;
    ant=255;
    search(1,0);
    if (bb) {
        puts("Yes");
        printf ("%d\n",ans);
    } else {
        puts("No");
        printf ("%d\n",ant);
    }//输出
}

另：请管理员改一下，这题真是我出的啊QAQ