Skip to content

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') {
                    // 只有一个数字 无数字读入为0order为空
                    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;
}