11329: 【原1329】聚餐
题目
题目描述
author: 白志豪 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1329
Description
为了庆祝机考，ACM班的m个同学决定去聚餐。
到了餐厅以后，他们发现一共有n个可供选择的菜（编号为1,2,⋯, n），所以每个同学都向负责点菜的班长大人提出了一些要求。比如，一个同学表示，他一定要吃辣；另一个同学表示，他不能看到维生素C。当然，要满足所有人的所有要求是很难做到的，因此只要有至少一个要求被满足，这个同学就会开心的去吃饭。
现在问题来了：班长是否能选择一些菜，使得所有人都能开心？
Input Format
第一行是一个正整数t，表示数据组数。每一组数据之间有一行空行。
对于一组数据，第一行有两个正整数n, m，用空格隔开。接下来有m行，每行有不超过n个整数，中间用空格隔开。
对于第i行的某个整数，如果是正整数k，表示同学i一定要吃编号为k的菜；如果是负整数-k，表示同学i不能忍受餐桌上有编号为k的菜。
Output Format
如果能够使所有人都开心，则输出”Bingo!”，否则输出”Sigh...”。
每组数据的输出结果占一行。
Sample Input
2
3 5
1 -2 3
-3
-1 3
1 3
-2 -3
3 5
-1 -2
1 -2
1 -2
1
1 2 3
Sample Output
Sigh...
Bingo!
Constraints
1 <= t <= 5;
1 <= n <= 20;
1 <= m <= 60
ligongzzz's solution
#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;
int n, m;
bool visited[25] = { 0 };
int choose[65][25] = { 0 };
int val_num[65] = { 0 };
bool fucked = false;
void fuck(int pos) {
if (pos == n + 1) {
bool flag = true;
for (int i = 0; i < m; ++i) {
int cnt = 0;
for (int j = 0; j < val_num[i]; ++j) {
if (choose[i][j] < 0 && !visited[-choose[i][j]]) {
++cnt;
}
else if (choose[i][j] > 0 && visited[choose[i][j]]) {
++cnt;
}
}
if (cnt == 0) {
flag = false;
break;
}
}
if (flag) {
fucked = true;
}
return;
}
visited[pos] = true;
fuck(pos + 1);
visited[pos] = false;
fuck(pos + 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
cin.get();
for (; t > 0; --t) {
fucked = false;
memset(visited, 0, sizeof(visited));
memset(choose, 0, sizeof(choose));
memset(val_num, 0, sizeof(val_num));
cin >> n >> m;
/*
cin.get();
char buff[1000] = { 0 };
cin.getline(buff, 1000);
int length = strlen(buff);
int cnt = 0;
int cur_num = 0;
for (int i = 0; i < length; ++i) {
if (buff[i] >= '0' && buff[i] <= '9') {
cur_num = cur_num * 10 + buff[i] - '0';
if ()
}
}*/
cin.get();
for (int i = 0; i < m; ++i) {
for (int cnt = 0;; ++cnt) {
cin >> choose[i][cnt];
if (cin.get() == '\n') {
val_num[i] = cnt + 1;
break;
}
}
}
fuck(1);
if (fucked) {
cout << "Bingo!\n";
}
else {
cout << "Sigh...\n";
}
}
return 0;
}
q4x3's solution
/**
* 二进制运算
* 每个人爱吃的菜表示成一个二进制数(转换成十进制存储)
* 不爱吃的菜表示成一个二进制数
* 爱吃的菜与点的菜有交集||不爱吃的菜与没点的菜有交集，则满足
* 遍历所有可能的点菜情况并判断
* interSec用来判断两个数的二进制是否有在同一位置的1
**/
#include <iostream>
#include <cstring>
using namespace std;
long long lik[70], dis[70];
bool interSec(long long a, long long b) {
bool flag = 0;
while(a != 0 && b != 0) {
if((a & 1 & b) == 1) {
flag = 1;
break;
} else {
a >>= 1;
b >>= 1;
}
}
return flag;
}
int main() {
int t, n, m;
char tmp;
cin >> t;
for(int i = 0;i < t;++ i) {
/**
* input
* */
memset(lik, 0, 70 * sizeof(long long));
memset(dis, 0, 70 * sizeof(long long));
cin >> n >> m;
tmp = getchar();
for(int j = 0;j < m;++ j) {
tmp = 0;
while(tmp != '\n') {
tmp = getchar();
if(tmp == ' ') continue;
if(tmp == '-') {
tmp = getchar();
dis[j] += (1 << (tmp - '0' - 1));
continue;
}
if(tmp - '0' > 0) lik[j] += (1 << (tmp - '0' - 1));
}
}
/**
* judge
* */
bool flag = 1, f1, f2;
long long s = (1 << n) - 1;
for(int k = 0;k <= s;++ k) {
flag = 1;
for(int kk = 0;kk < m;++ kk) {
f1 = interSec(lik[kk], k);
f2 = interSec(dis[kk], s - k);
if(f1 == 0 && f2 == 0) {
flag = 0;
break;
}
}
if(flag) break;
else continue;
}
if(flag) cout << "Bingo!" << endl;
else cout << "Sigh..." << endl;
}
}
victrid's solution
#include <iostream>
using namespace std;
struct level {
int* likes;
int* hates;
int maxdishes;
int man;
};
level getinput() {
int dish, man;
cin >> dish >> man;
int* likes = new int[man]();
int* hates = new int[man]();
int tempproc;
cin.get();
for (int i = 0; i < man; ++i) {
for (int cnt = 0;; ++cnt) {
cin >> tempproc;
if (tempproc >= 0)
likes[i] += 1 << (tempproc - 1);
else
hates[i] += 1 << (-tempproc - 1);
if (cin.get() == '\n')
break;
}
}
return level{likes, hates, dish, man};
} //everyman
int main() {
int t;
cin >> t;
bool* ans = new bool[t]();
for (int i = 0; i < t; i++) {
level input = getinput();
int maxn = (1 << (input.maxdishes + 1)) - 1;
//here seems do not cost so much time...
// That's strange.. it's o(2^n)
for (int z = 0; z < maxn; z++) {
for (int i = 0; i < input.man; i++) {
if ((z & input.likes[i]) == 0 && (~z & input.hates[i]) == 0)
goto next;
}
ans[i] = true;
goto nextnext;
next:;
}
ans[i] = false;
nextnext:;
}
for (int i = 0; i < t; i++) {
cout << (ans[i] ? "Bingo!\n" : "Sigh...\n");
}
return 0;
}
yyong119's solution
#include <vector>
#include <cstdio>
#include <algorithm>
#include <iostream>
#define MAX_N 25
#define MAX_M 65
using namespace std;
int main() {
int T; scanf("%d", &T);
while(T--) {
vector<vector<int> > orders;
vector<int> _unused;
orders.push_back(_unused);
int n, m, tmp, sign; scanf("%d%d", &n, &m);
char a = getchar();
for (int i = 0; i < m; ++i) {
// nmdwsm读一行数据都那么累
vector<int> order; tmp = 0; sign = 1;
while(true) {
a = getchar();
if (a == '\n') {
// 只有一个数字， 无数字读入为0，order为空
if (tmp) order.push_back(tmp * sign);
break;
}
else if (a == '-')
sign = -1;
else if(a >= '0' && a <= '9')
tmp = tmp * 10 + a - '0';
else if (a == ' ') {
order.push_back(tmp * sign);
sign = 1;
tmp = 0;
}
}
orders.push_back(order);
}
// Check自己的读入有没有错
// printf("\n");
// for (int i = 1; i < orders.size(); ++i) {
// for (int j = 0; j < orders[i].size(); ++j)
// printf("%d ", orders[i][j]);
// printf("\n");
// }
// return 0;
bool overall_OK = false;
// 遍历各种菜被选择和不选择情况
for (int order_case = 0; order_case < (1 << n); ++order_case) {
int order_each[MAX_N], tmp = order_case;
for (int i = 1; i <= n; ++i) {
order_each[i] = tmp & 1; // 1选择第i个菜，0不选
tmp >>= 1;
}
bool this_order_case_OK = true;
// Check每个同学是否至少一项满足
for (int i = 1; i <= m; ++i) {
bool for_this_user_OK = false;
if (orders[i].size() == 0)
for_this_user_OK = true;
else
for (int j = 0; j < orders[i].size(); ++j) {
int num = orders[i][j];
// num为正即该同学喜欢这个菜， num为负即该同学讨厌这个菜
if (num > 0 && order_each[num] == 1 || num < 0 && order_each[-num] == 0) {
for_this_user_OK = true;
break;
}
}
// 一个同学无法满足，则这种情况不符合
if (for_this_user_OK == false) {
this_order_case_OK = false;
break;
}
}
// 这种情况符合，结束输出Bingo
if (this_order_case_OK) {
overall_OK = true;
break;
}
}
if(overall_OK)
printf("Bingo!\n");
else
printf("Sigh...\n");
}
return 0;
}