核心:要求是两数之差,其实简化逻辑,和任意一个数之和存在于之前的数组中

满分2

/**
题意:出数字,出的数字必须是前面的数字之差,而且没有重复

不会超时,直接循环unordered_set即可

核心:set的find的使用
*/
#include <iostream>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <vector>
using namespace std;
unordered_set<int> se;
bool judge(int x)
{
    for(auto t : se)
    {
        if (se.find(t + x) != se.end()) return true;
    }
    return false;
}
int f[20][1010];
int main()
{
    int m, n, a, b;
    cin >> a >> b;
    se.insert(a), se.insert(b);
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++) cin >> f[i][j];
    }
    unordered_map<int, int> out;
    for(int j = 1; j <= n; j++)
    {
        for(int i = 1; i <= m; i++)
        {
            int x = f[i][j];
            if (out[i]) continue;
            // 用ext[x] 来判定是有问题的,因为有的数据可能默认大于0
            if (judge(x) && se.find(x) == se.end())
            {
                se.insert(x);
            }else
            {
                out[i] = true;
                printf("Round #%d: %d is out.\n", j, i);
            }
        }
    }
    vector<int> vc;
    int cnt = 0;
    for(int i = 1; i <= m; i++)
    {
        if (!out[i]) vc.push_back(i), cnt++;
    }
    if (cnt == 0) printf("No winner.");
    else
    {
        printf("Winner(s):");
        for(int i = 0; i < vc.size(); i++) printf(" %d", vc[i]);
    }
}

满分

#include <cstring>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
using namespace std;
const int N = 1010;
int g[N][N];
unordered_map<int, int> st, visit;
unordered_set<int> se;

int main()
{
    int a, b, x, y;
    cin >> a >> b;
    se.insert(a);
    se.insert(b);
    st[a] = 1;
    st[b] = 1;
    cin >> x >> y;
    for(int i = 1; i <= x; i++)
    {
        for(int j = 1; j <= y; j++)
        {
            cin >> g[i][j];
        }
    }
    int cnt = 0;
    for(int j = 1; j <= y; j++)
    {
        for(int i = 1; i <= x; i++)
        {
            int z = g[i][j];
            bool f = false;
            if (visit[i] == 1) continue;
            // 当前数时任意两个数之差,意味着他和一个数之和存在
            if (st[z] == 0) 
            {
                for(auto t : se)
                {
                    int sum = g[i][j] + t;
                    //printf("%d %d %d\n", g[i][j], t, z);
                    if (st[sum] == 1) se.insert(z), st[z] = 1, f = true;
                    if (f) break;
                }
            }

            if (!f)
            {
                visit[i] = 1;
                printf("Round #%d: %d is out.\n", j, i);
                cnt++;
            }
        }
    }
    if (cnt >= x) puts("No winner.");
    else
    {
        printf("Winner(s):");
        for(int i = 1; i <= x; i++)
        {
            if (visit[i] == false) printf(" %d", i);
        }
    }

}

方法二 21分, 一个点运行超时

#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

const int N = 1010;
int g[N][N];
bool visit[N];
unordered_map<int, bool> pos;
int main()
{
    int m, n, x, y;
    cin >> x >> y;
    cin >> m >> n;
    pos[x] = pos[y] = true;
    unordered_set<int> hset; //用unordered_set 会快很多
    hset.insert(x);
    hset.insert(y);
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> g[i][j];
        }
    }
    // 遍历回合
    for(int j = 1; j <= n; j++)
    {
        for(int i = 1; i <= m; i ++)
        {
            bool f1 = false;
            if (!visit[i])
            {
                int z = g[i][j];
                if (pos[z] == 0)
                {
                    //for(int i = 0; i < res.size(); i++)
                    for(auto it : hset)
                    {
                        int k = z + it;
                        if (pos[k]) f1 = true, pos[z] = true, hset.insert(z);
                    }
                }
                if (!f1) printf("Round #%d: %d is out.\n", j, i), visit[i] = true;
            }
        }
    }
    vector<int> vc;
    for(int i = 1; i <= m; i++)
    {
        if (!visit[i]) vc.push_back(i);
    }
    if (!vc.size()) puts("No winner.");
    else {
        printf("Winner(s):");
        for(int i = 0; i < vc.size(); i++)
        {
            printf(" %d", vc[i]);
        }
    }
}

方法一 18分, 一个超时,一个错误

#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>
using namespace std;

int main()
{
    int a, b, m, n, cnt = 0;
    cin >> a >> b;
    cin >> m >> n;
    vector<vector<int>> res(m , vector<int> (n));
    vector<int> in;
    unordered_map<int,int> ext_mp;
    in.push_back(a); ext_mp[a] = 1;
    in.push_back(b); ext_mp[b] = 1;
    int arr[m];
    memset(arr, 0, sizeof arr);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> res[i][j];
        }
    }

    for(int j = 0; j < n; j++)
    {

        for(int i = 0;i < m; i++) // 为啥 arr[i] == 0 && i < m 会直接跳出循环
        {
            if (arr[i] == 1) continue;
            bool flag = false;
            for (int k = 0; k < in.size(); k++)
            {
                int pos = in[k] + res[i][j];
                if (arr[i] == 0 && ext_mp[res[i][j]] == 0 && ext_mp[pos] == 1) {

                    flag = true;
                    break;
                }
            }
            ext_mp[res[i][j]] = 1;
            if (flag)
            {
                in.push_back(res[i][j]);
                ext_mp[res[i][j]] = 1;
            }else {
                cnt++;
                arr[i] = 1;
                printf("Round #%d: %d is out.\n", j + 1, i + 1);
            }
        }
    }
    if (cnt == m)
    {
        printf("No winner.");
    }else{
        printf("Winner(s):");
        for(int i = 0; i < m; i++)
        {
            if (arr[i] == 0) printf(" %d",i + 1);
        }
    }

}