P6920

__log__ · 2024-02-16 09:02:16 · 题解

本来是校内训练挑的题，结果调了 4h。调着调着玩起了面向数据编程。

不管各位的世界有没有昼夜的概念，总之先祝您早上中午晚上好！……

题目描述

给定若干个连续时刻的电子钟的样子，分析每一个液晶点的运转情况是否正常。

运转情况具体如下：

1. 工作正常：该位置输出 W。
2. 永远亮着：该位置输出 1。
3. 永远不亮：该位置输出 0。
4. 可能有多种情况：输出 ?。

题目分析

你希望直接从这堆坏掉的钟瞅出钟代表的时间可以说是不可能的（不信你自己看样例 1）。但是如果用某种办法得知了钟代表的时间，可以做到事半功倍的效果。

所以我们枚举起始位置代表的分钟数，用 check(h, m) 封装分析起始位置为 h 时 m 分的情况。

for(int i = 0; i <= 23; ++i)
    for(int j = 0; j <= 59; ++j)
        check(i, j);

跑 check(i, j) 时可能会遇到这个时刻与钟表相矛盾的情况。所以若每个时刻都与钟表矛盾，就无解了。

if(!flag) {
    cout << "impossible";
    return 0;
}

这个 check 又要怎么写？？？

check(i, j) 内用 ans1 数组记录起始时刻为 i 时 j 分钟的运转情况。每次计算先把 ans1 初始化，把没有液晶的地方变成 .，剩下的地方变成 A 表示还没分析出来。

int a[5] = {0, 1, 4, 7}, b[5] = {0, 2, 3, 5, 6};
int c[10] = {0, 1, 4, 6, 9, 13, 16, 18, 21}, d[10] = {0, 2, 3, 7, 8, 14, 15, 19, 20}, e[10] = {0, 5, 10, 12, 17};

for(int i = 1; i <= 7; ++i)
    for(int j = 1; j <= 21; ++j)
        ans1[i][j] = 'A';
for(int i = 1; i <= 8; ++i) {
    for(int j = 1; j <= 3; ++j) ans1[a[j]][c[i]] = '.';
    for(int j = 1; j <= 4; ++j) ans1[b[j]][d[i]] = '.';
}
for(int i = 1; i <= 4; ++i) for(int j = 1; j <= 7; ++j) ans1[j][e[i]] = '.';
ans1[1][11] = ans1[2][11] = ans1[4][11] = ans1[6][11] = ans1[7][11] =  '.';

我把它叫做初始化半自动机。

对于每一个钟表，如果四个数字中有一个与钟表矛盾，就直接 return 掉（x 表示现在的小时数，y 表示分钟数）。

cnum(id, num, base, flag1) 表示数字 num 能不能放进钟表对应位置里，flag1 代表数字是否为小时数的十位（要特判）。

for(int i = 1; i <= n; ++i) {
    if(cnum(i, x / 10, 0, 1) || cnum(i, x % 10, 5, 0) || cnum(i, y / 10, 12, 0) || cnum(i, y % 10, 17, 0)) return;
    ++y;
    if(y == 60) x++, y = 0;
    if(x >= 24) x = 0;
}

判断数字是否矛盾

输入的时候记录每一个位置 (x,y) 亮的次数 t_{(x,y)}。

1. 如果钟表中某一个位置 (x,y) 不应该亮：
   • 此时亮了，但是这个位置是一直亮的 (t_{(x,y)}=n)，那么这个位置就直接填 1。
   • 此时亮了，但是这个位置有某个时候关闭了 (t_{(x,y)}\not=n)，说明这个位置产生了矛盾（既不是 W，也不是 0，也不是 1），直接返回矛盾。
   • 此时没亮，直接不管，等待进一步判断（这个东西下面会说）。
2. 如果钟表中某一个位置 (x,y) 应该亮：
   • 此时亮了，同样不管。
   • 此时没亮，且一直不亮 (t_{(x,y)}=0)，那这个位置只能是 0。
   • 此时没亮，且有时候亮 (t_{(x,y)}\not=0)，矛盾！

小时位前导 0 要特判

tips: 你可以用状压记录每种数字有哪些位置应该亮，哪些不应该亮。

int s[10] = {16335, 780, 15423, 3903, 1020, 4083, 16371, 783, 16383, 4095};
// 不是随手敲的

bool cnum(int id, int num, int base, int flag1) {
   if(flag1 && num == 0) {
       for(int i = 1; i <= 14; ++i) {
           int st = s[num] >> (i - 1) & 1, px = ex[i][0], py = base + ex[i][1];
            if(ch[id][px][py] == '.') continue;
            else if(t[px][py] == n) ans1[px][py] = '1';
            else return 1;
       }
        return 0;
    }
    for(int i = 1; i <= 14; ++i) {
        int st = s[num] >> (i - 1) & 1;
        int px = ex[i][0], py = base + ex[i][1];
        if(st == (ch[id][px][py] == 'X')) continue;
        else {
        if(t[px][py] == 0 || t[px][py] == n) ans1[px][py] = ((t[px][py] == n) + 48);
        else return 1;
        }
    }
    return 0;
}

（状压每一位代表的位置，1 代表亮，0 代表不亮）

最后处理答案

收回前面埋的坑：如果这个时候你还有地方没处理出来（没判出 01），那么这些地方肯定是该亮的时候亮了，不该亮的时候关了，就有如下可能：

1. 这个位置不是一直亮着 (t_{(x,y)}\not=0 且 t_{(x,y)}\not=n)，这里必是 W。
2. 这个位置一直亮着，它可能是 W 或 1，所以填 ?。
3. 这个位置一直不亮，它可能是 W 或 0，所以填 ?。

for(int i = 1; i <= 7; ++i) {
    for(int j = 1; j <= 21; ++j) {
        if(ans1[i][j] == 'A' && (t[i][j] == 0 || t[i][j] == n)) ans1[i][j] = '?';
        else if(ans1[i][j] == 'A') ans1[i][j] = 'W';
    }
}

以上就是处理 ans1 数组的办法。最后合并答案就收工了。

• 如果这是第一次算出答案，就直接 ans[i][j] = ans1[i][j];
• 如果不是，就要判断 ans_{i,j} 是否等于 ans1_{i,j}，如果不相等，就直接 ans[i][j] = '?'（有多种可能所以判为 ?）。

Code

早就知道你想白嫖代码了，所以我连防抄袭都懒得放了。

// I love Furina forever!
# include <bits/stdc++.h>
using namespace std;

int n, cnt;
int t[8][22];
int a[5] = {0, 1, 4, 7}, b[5] = {0, 2, 3, 5, 6};
int c[10] = {0, 1, 4, 6, 9, 13, 16, 18, 21}, d[10] = {0, 2, 3, 7, 8, 14, 15, 19, 20}, e[10] = {0, 5, 10, 12, 17};
int ex[15][2] = {{0, 0}, {1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 3}, {4, 2}, {3, 1}, {2, 1}, {5, 4}, {6, 4}, {7, 3}, {7, 2}, {6, 1}, {5, 1}};
int s[10] = {16335, 780, 15423, 3903, 1020, 4083, 16371, 783, 16383, 4095};
char ch[105][8][22], ans[8][22], ans1[8][22];
bool flag;

void init() {
    for(int i = 1; i <= 7; ++i)
        for(int j = 1; j <= 21; ++j)
            ans1[i][j] = 'A';
    for(int i = 1; i <= 8; ++i) {
        for(int j = 1; j <= 3; ++j) ans1[a[j]][c[i]] = '.';
        for(int j = 1; j <= 4; ++j) ans1[b[j]][d[i]] = '.';
    }
    for(int i = 1; i <= 4; ++i) for(int j = 1; j <= 7; ++j) ans1[j][e[i]] = '.';
    ans1[1][11] = ans1[2][11] = ans1[4][11] = ans1[6][11] = ans1[7][11] =  '.';
    if(t[3][11] == n) ans1[3][11] = '?';
    else if(t[3][11] == 0) ans1[3][11] = '0';
    else {
        cout << "impossible";
        exit(0);
    }
    if(t[5][11] == n) ans1[5][11] = '?';
    else if(t[5][11] == 0) ans1[5][11] = '0';
    else  {
        cout << "impossible";
        exit(0);
        }
}

bool cnum(int id, int num, int base, int flag1) {
    if(flag1 && num == 0) {
        for(int i = 1; i <= 14; ++i) {
            int st = s[num] >> (i - 1) & 1, px = ex[i][0], py = base + ex[i][1];
            if(ch[id][px][py] == '.') continue;
            else if(t[px][py] == n) ans1[px][py] = '1';
            else return 1;
        }
        return 0;
    }
    for(int i = 1; i <= 14; ++i) {
        int st = s[num] >> (i - 1) & 1;
        int px = ex[i][0], py = base + ex[i][1];
        if(st == (ch[id][px][py] == 'X')) continue;
        else {
            if(t[px][py] == 0 || t[px][py] == n) ans1[px][py] = ((t[px][py] == n) + 48);
            else return 1;
        }
    }
    return 0;
}

void check(int x, int y) {
    init();
    for(int i = 1; i <= n; ++i) {
        if(cnum(i, x / 10, 0, 1) || cnum(i, x % 10, 5, 0) || cnum(i, y / 10, 12, 0) || cnum(i, y % 10, 17, 0)) return;
        ++y;
        if(y == 60) x++, y = 0;
        if(x >= 24) x = 0;
    }
    for(int i = 1; i <= 7; ++i) {
        for(int j = 1; j <= 21; ++j) {
            if(ans1[i][j] == 'A' && (t[i][j] == 0 || t[i][j] == n)) ans1[i][j] = '?';
            else if(ans1[i][j] == 'A') ans1[i][j] = 'W';
        }
    }
    ++cnt;
    if(flag) {
        for(int i = 1; i <= 7; ++i)
            for(int j = 1; j <= 21; ++j)
                if(ans[i][j] != ans1[i][j] || ans[i][j] == '?') ans[i][j] = '?';
    }
        else {
            for(int i = 1; i <= 7; ++i)
                for(int j = 1; j <= 21; ++j) ans[i][j] = ans1[i][j];
    }
    flag = 1;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= 7; ++j)
            for(int k = 1; k <= 21; ++k)
                cin >> ch[i][j][k], t[j][k] += (ch[i][j][k] == 'X');
    for(int i = 1; i <= 7; ++i)
        for(int j = 1; j <= 21; ++j) ans[i][j] = '.';
    for(int i = 0; i <= 23; ++i)
        for(int j = 0; j <= 59; ++j)
            check(i, j);
    if(!flag) {
        cout << "impossible";
        return 0;
    }
    for(int i = 1; i <= 7; ++i) {
        for(int j = 1; j <= 21; ++j)
            cout << ans[i][j];
        cout << '\n';
    }
    return 0;
}

下班收工，原神启动！