ZOJ - 3954 Seven-Segment Display 【状态标记】

题目链接

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3954

题意

有一块 LED 灯

然后上面有七块灯管

在显示不同数字的时候 由灯管的开关组合 来表现一个数字

给出一个标准表

然后 输入 一个表

求这个表 的 列 是可以交换的

然后 判断能否有一种经过若干次交换后的情况

这个表能够跟 标准表 相同

如果能 就输出 YES

不能 就输出 NO

思路

我们可以用MAP 存下 标准表的列 和 输入的表 的列

然后判断一下 两个MAP 是否完全相同

然后 输入的时候 要用 scanf 用 int 保存 不然会 超时

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = 3.14159265358979323846264338327;

const double E = exp(1);

const double eps = 1e-30;

const int INF = 0x3f3f3f3f;

const int maxn = 1e4 + 5;

const int MOD = 1e9 + 7;

int G[10][10];

int v[10][10];

struct Node

{

    int n;

    int v[10];

}q[10];

bool comp(Node x, Node y)

{

    return x.n < y.n;

}

void init()

{

    CLR(G);

    G[1][1] = G[1][4] = G[1][5] = G[1][6] = G[1][7] = 1;

    G[2][3] = G[2][6] = 1;

    G[3][5] = G[3][6] = 1;

    G[4][1] = G[4][4] = G[4][5] = 1;

    G[5][2] = G[5][5] = 1;

    G[6][2] = 1;

    G[7][4] = G[7][5] = G[7][6] = G[7][7] = 1;

    G[9][5] = 1;

}

int main()

{

    init();

    int t;

    scanf("%d", &t);

    while (t--)

    {

        CLR(v);

        int n;

        int arr[9];

        scanf("%d", &n);

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

        {

            scanf("%d", &q[i].n);

            for (int j = 0; j < 7; j++)

                scanf("%1d", &q[i].v[j]);

        }

        sort(q, q + n, comp);

        map <int, int> vis[2];

        int num = 0;

        for (int i = 0; i < 7; i++)

        {

            num = 0;

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

            {

                num = num * 2 + q[j].v[i];

            }

            vis[0][num]++;

        }

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

        {

            num = 0;

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

            {

                num = num * 2 + G[q[j].n][i];

            }

            vis[1][num]++;

        }

        map <int, int>::iterator it;

        int flag = 1;

        for (it = vis[0].begin(); it != vis[0].end(); it++)

        {

            if (vis[1][it->first] != it->second)

            {

                flag = 0;

                break;

            }

        }

        if (flag)

            printf("YES\n");

        else

            printf("NO\n");

    }

}