蓝桥杯 ALGO-114 算法训练黑白无常

问题描述
某寝室的同学们在学术完之后准备玩一个游戏：游戏是这样的，每个人头上都被贴了一张白色或者黑色的纸，现在每个人都会说一句话“我看到x张白色纸条和y张黑色的纸条”，又已知每个头上贴着白色纸的人说的是真话、每个头上贴着黑色纸的人说的是谎话，现在要求你判断哪些人头上贴着的是白色的纸条，如果无解输出“NoSolution.”；如果有多组解，则把每个答案中贴白条的人的编号按照大小排列后组成一个数（比如第一个人和第三个人头上贴着的是白纸条，那么这个数就是13；如果第6、7、8个人都贴的是白纸条，那么这个数就是678）输出最小的那个数（如果全部都是黑纸条也满足情况的话，那么输出0）
输入格式
第一行为一个整数n，接下来n行中的第i行有两个整数x和y，分别表示第i个人说“我看到x张白色纸条和y张黑色的纸条”。
输出格式
一行。如果无解输出“NoSolution.”。否则输出答案中数值（具体见问题描述）最小的那个，如果全部都是黑纸条也满足情况的话，那么输出0
样例输入
2
1 0
1 0
样例输出
0
样例输入
5
3 1
0 4
1 3
4 0
1 3
样例输出
35
数据规模和约定
n<=8

分析：1.枚举所有人的黑白字条情况，判断当前情况是否可能存在，把所有可能情况收集起来输出最小的
2.注意每人看不到自己头上的字条哦～

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> ansv;
pair<int, int> v[10];
int n, k, cnt, a[10];
void dfs(int num) {
    if (num == 0) {
        int white = 0, black = 0, ans = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] == -1) black++;
            if (a[i] == 1) white++;
        }
        for (int i = 1; i <= n; i++) {
            if (a[i] == 1 && (v[i].first != white-1 || v[i].second != black)) return;
            if (a[i] == -1 && (v[i].first == white && v[i].second == black-1)) return;
        }
        for (int i = 1; i <= n; i++) 
            if (a[i] == 1) ans = ans * 10 + i;
        ansv.push_back(ans);
    } else {
        a[num] = -1;
        dfs(num - 1);

        a[num] = 1;
        dfs(num - 1);
    }
}
int main() {
    scanf("%d", &n);;
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i].first, &v[i].second);
    dfs(n);
    sort(ansv.begin(), ansv.end());
    printf("%d\n", ansv[0]);
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> ansv;

pair<int, int> v[10];

int n, k, cnt, a[10];

void dfs(int num) {

if (num == 0) {

int white = 0, black = 0, ans = 0;

for (int i = 1; i <= n; i++) {

if (a[i] == -1) black++;

if (a[i] == 1) white++;

}

for (int i = 1; i <= n; i++) {

if (a[i] == 1 && (v[i].first != white-1 || v[i].second != black)) return;

if (a[i] == -1 && (v[i].first == white && v[i].second == black-1)) return;

}

for (int i = 1; i <= n; i++)

if (a[i] == 1) ans = ans * 10 + i;

ansv.push_back(ans);

} else {

a[num] = -1;

dfs(num - 1);

a[num] = 1;

dfs(num - 1);

}

int main() {

scanf("%d", &n);;

for (int i = 1; i <= n; i++)

scanf("%d%d", &v[i].first, &v[i].second);

dfs(n);

sort(ansv.begin(), ansv.end());

printf("%d\n", ansv[0]);

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版