本文主要是介绍CCF CSP 202009-3 点亮数字人生-详细注释版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
CCF CSP 202009-3 点亮数字人生-详细注释版
#include <iostream> // 直接到拉到最下方 主函数
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <map>
#include <set>
#include <cstdio>
#include <ctype.h>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>#define x first
#define y second
#define PB push_back
#define EB emplace_backusing namespace std;
typedef pair<int, int> PII;
typedef pair<string, int> PSI;
typedef long long LL;const int N = 3050, M = 2503, SMAX = 10003; // 由于Nmax为500,再加上最多kmax*Nmax=2500个输入信号,故最多3000个点(N)
// 最多Nmax*Kmax个边(M)
int n, m, T;
int h[N], e[M], ne[M], idx; // 图
int type[N], res[N]; // type：将AND/OR/... 转为对应数字123456, res存答案结果
map<string, int> type_M; // 帮助type查找
vector<int> in[SMAX], out[SMAX]; // 输入信号的值；要求输出信号的值
int indegree[N]; //入度
int Q[N], top; // 模拟队列void init() {type_M["NOT"] = 1;type_M["AND"] = 2;type_M["OR"] = 3;type_M["XOR"] = 4;type_M["NAND"] = 5;type_M["NOR"] = 6;
}int get_number(char s[]) { // 获取数字int res = 0;for (int i = 1; s[i]; ++ i) {res = res * 10 + s[i] - '0';}return res;
}void add(int a, int b) { // 构建图，邻接表型e[++ idx] = b;ne[idx] = h[a];h[a] = idx;
}bool topoSort() { // 拓扑排序，大家都懂for (int i = 1; i <= m + n; ++ i) {if (!indegree[i]) {Q[top ++] = i;}}int l = 0;while (l < top) {int t = Q[l ++];for (int i = h[t]; i; i = ne[i]) {int j = e[i];if (-- indegree[j] == 0) {Q[top ++] = j;}}}return top == n + m;
}int main() {init(); // 初始化type_Mscanf("%d", &T);char str[100];int num, val;while (T --) { // T组数据memset(indegree, 0, sizeof indegree); // 因为有多组数据，因此每次要清空memset(h, 0, sizeof h);idx = 0;top = 0;scanf("%d%d", &m, &n); // m个输入,n个元器件;输入信号：1~m,元器件:m+1~m+nfor (int i = 1 + m; i <= n + m; ++ i) {scanf("%s%d", str, &num);type[i] = type_M[str]; // XOR/OR/... -> 对应种类编号for (int j = 1; j <= num; ++ j) { scanf("%s", str);val = get_number(str); // string转数字if (str[0] == 'O') {val += m; // 元器件则编号+m}add(val, i); //添加边++ indegree[i]; // 记录入度，帮助topoSort}}int S; // 同题中意思scanf("%d", &S);for (int i = 1; i <= S; ++ i) { // 输入信号的值in[i].clear(); in[i].EB(val); // 前边加一个，便于与输入123与下标对应起来for (int j = 0; j < m; ++ j) {scanf("%d", &val);in[i].EB(val);}}for (int i = 1; i <= S; ++ i) { // 需要的输出信号out[i].clear();scanf("%d", &num);for (int j = 1; j <= num; ++ j) {scanf("%d", &val);out[i].EB(val + m);}}if (!topoSort()) { // 如果有环则loopputs("LOOP"); // 如果没环，可见Q队列中已经存储了topoSort的顺序，因此之后不用考虑先后顺序，只需从Q中取出即可}else { // 无环for (int k = 1; k <= S; ++ k) { // 处理S组数据 in[k] 对应 out[k]for (int i = m + 1; i <= m + n; ++ i) { // 如果为AND或NOR初始置为1，否则为0.if (type[i] == 2 || type[i] == 6) {res[i] = 1;} else {res[i] = 0;}}for (int i = 0; i < n + m; ++ i) { // 按拓扑序更新int left = Q[i], val = res[left];if (left <= m) {val = in[k][left];}for (int j = h[left]; j; j = ne[j]) { // 用a的状态 更新a的下一节点的状态int t = e[j];if (type[t] == 1) { // 与或非...大家都懂res[t] = !val;}else if (type[t] == 2) {res[t] &= val;}else if (type[t] == 3) {res[t] |= val;}else if (type[t] == 4) {res[t] ^= val;}else if (type[t] == 5) { // !(a&b) = (!a)|(!b) 数学知识res[t] |= !val;}else {res[t] &= !val; // !(a|b) = (!a)&(!b)}}}for (int x : out[k]) { // 依次输出即可。printf("%d ", res[x]);}printf("\n");}}}return 0;
}
这篇关于CCF CSP 202009-3 点亮数字人生-详细注释版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
