题解 P4907 【A换B problem】
引领天下
2018-10-23 21:51:35
出题人来写一发题解
此题主要就是搜索，为了提升难度，我还搞了一个恶心的读入
接下来就是搜索了。
具体码里说吧。
```cpp
#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