题目分析

题意简述

本题包含 $t$ 组测试用例。对于每组测试用例，输入整数 $n$ 表示有 $n$ 组数据，每组数据包含三个整数 $a$、$b$、$c$ 和两个字符 $f1$、$f2$。程序需要根据这些数据构建某种逻辑关系，找出其中可能存在的错误（kywh 为 false 的情况），并根据错误的数量判断输出结果。如果错误数量不为 $1$，输出 impossible；如果错误数量为 $1$，输出特定的数值（通过 fanIdx[arg] 得到）。

输入

• 第一行输入测试用例的组数 $t$。
• 对于每组测试用例：
  • 首先输入整数 $n$，表示接下来有 $n$ 组数据。
  • 对于每组数据，依次输入整数 $a$、整数 $b$、字符 $f1$、整数 $c$、字符 $f2$。

输出

对于每组测试用例：

• 如果错误数量（huai）不为 $1$，输出字符串 impossible。
• 如果错误数量（huai）为 $1$，输出通过 fanIdx[arg] 得到的数值。

解题思路

数据处理与编号映射

1. 映射表初始化：使用 map<int, int> idx 来建立输入整数到自定义编号的映射，fanIdx 数组用于反向映射（从自定义编号到输入整数），cnt 用于记录自定义编号的数量，初始化为 $0$。
2. 获取编号函数 getID：定义 getID 函数，用于获取输入整数对应的自定义编号。如果整数已经在映射表中，则直接返回对应的编号；否则，将整数插入映射表，更新 fanIdx 数组，并返回新的编号。

数据存储与初步分析

1. 数据存储：对于每组输入数据，通过 getID 函数获取 $a$、$b$、$c$ 对应的自定义编号 ida、idb、idc。将 idb 和 idc 存储在 test[ida][0] 和 test[ida][1] 中，将 f1 和 f2 转换为布尔值存储在 res[ida][0] 和 res[ida][1] 中。
2. 记录可能错误的编号：如果 res[ida][0] 为 false 且 idb 未被使用过，则将 idb 加入 posN 数组，并标记 idb 已使用；同理，如果 res[ida][1] 为 false 且 idc 未被使用过，则将 idc 加入 posN 数组，并标记 idc 已使用。

错误检查与结果判断

1. 检查错误：遍历 posN 数组中的每个编号 idh。对于每个 idh，检查其他所有编号 j 的数据，判断是否存在逻辑矛盾（即 (res[j][0] && test[j][0]==idh) || (!res[j][0] && test[j][0]!=idh) 或 (res[j][1] && test[j][1]==idh) || (!res[j][1] && test[j][1]!=idh) 成立）。如果存在矛盾，则 kywh 设为 false 并跳出循环。
2. 统计错误数量并输出结果：如果 kywh 为 true，则错误数量 huai 加 $1$，并记录当前编号 arg。如果 huai 达到或超过 $2$，则跳出循环。最后，根据 huai 的值判断输出 impossible 还是 fanIdx[arg] 的值。

代码实现

#include <iostream>
#include <stdio.h>
#include <map>
#include <vector>
using namespace std;
int cnt;
map<int, int> idx;
int fanIdx[233];
int test[233][2];
int res[233][2];
int getID(int yid){
    map<int, int>::iterator it = idx.find(yid);
    if(it != idx.end()){
        return it->second;
    }
    idx.insert(pair<int, int>(yid, cnt));
    fanIdx[cnt] = yid;
    cnt++;
    return cnt-1;
}

int main() {
    int t;
    scanf("%d", &t);
    for(int ii = 0; ii < t; ii++){
        int n;
        scanf("%d", &n);
        idx.clear();
        cnt = 0;
        vector<int> posN;
        int used[233] = {0};
        for(int i = 0; i < n; i++){
            int a,b,c;
            char f1,f2;
            scanf("%d\n%d\n%c\n%d\n%c", &a, &b, &f1, &c, &f2);
            int ida = getID(a), idb = getID(b), idc = getID(c);
            test[ida][0] = idb, test[ida][1] = idc;
            res[ida][0] = (f1=='Y'), res[ida][1] = (f2=='Y');
            if(!res[ida][0]){
                if(!used[idb]) posN.push_back(idb);
                used[idb]++;
            }
            if(!res[ida][1]){
                if(!used[idc]) posN.push_back(idc);
                used[idc]++;
            }
        }
        int huai = 0;
        int arg = -1;
        int sz = posN.size();
        for(int i = 0; i < sz; i++){
            int idh = posN[i];
            bool kywh = 1;
            for(int j = 0; j < cnt; j++){
                if(j==idh) continue;
                if((res[j][0] && test[j][0]==idh) || (!res[j][0] && test[j][0]!=idh)){
                    kywh=0; break;
                }
                if((res[j][1] && test[j][1]==idh) || (!res[j][1] && test[j][1]!=idh)){
                    kywh=0; break;
                }
            }
            if(kywh){
                huai++;
                arg=idh;
                if(huai>=2) break;
            }
        }
        if(huai-1){
            printf("impossible\n");
        }
        else{
            printf("%d\n", fanIdx[arg]);
        }
    }
    return 0;
}

代码说明

1. 全局变量定义：
   • cnt 用于记录自定义编号的数量。
   • idx 是一个 map，用于建立输入整数到自定义编号的映射。
   • fanIdx 数组用于反向映射，从自定义编号到输入整数。
   • test 二维数组用于存储每组数据中后两个数对应的编号。
   • res 二维数组用于存储每组数据中两个字符转换后的布尔值。
2. getID 函数：实现输入整数到自定义编号的映射功能。
3. main 函数：
   • 读取测试用例的组数 $t$。
   • 对于每组测试用例，读取数据数量 $n$，清空 idx 映射表，初始化 cnt 和其他相关数组。
   • 读取每组数据，进行编号映射和数据存储，并记录可能错误的编号。
   • 检查可能错误的编号，统计错误数量，根据错误数量输出相应结果。