202009 CSP认证 | 点亮数字人生

本文主要是介绍202009 CSP认证 | 点亮数字人生，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

3. 点亮数字人生
60分 | 超时
因为设计到电路门的先后连接，所以涉及到计算的时序问题，自然而然的想到了拓扑排序的问题。关于拓扑排序的理解和代码参考了这个博文：拓扑排序

在编写的时候还遇到了一个问题，就是将类似于“3456”的字符串转化为int类型的数字问题。在转化过程中出现奇数位会转化错误但是检查发现逻辑是正确的问题。查阅后发现是调用pow()后，返回值为double类型而导致的，解决方法参考了链接：转化数字时的错误解决

acwing上通过了7 / 12个答案，但是输入和答案太复杂了根本无法对照着找到逻辑错误…超时说明是优化问题…自写版本感觉60是我的极限了（第三题的难度真的在增加啊我哭了）
下面贴上自己写的60分答案：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 510;  //器件最大数量
const int S = 10010;vector<int> input_signal[S];   //记录各组输入信号的值
int output[N];
string components[N];  //用来记录元器件信息
unordered_map<int, string> fun;  //记录标号为Index的门的功能
unordered_map<int, set<int> >input_I;  //每个门的输入中, 作为输入信号的部分
unordered_map<int, set<int> >input_O;  //每个门的输入中, 作为其他门的输出的部分
vector<int> topo;  //一个可能的拓扑序列int string_to_int(string str)
{int index = 0;int len = str.size() - 1;  //前驱节点的位数for(int j = 1;j < str.size() && len;j ++){len --;int add = ((str[j] - 48) * int(pow(10, len) + 0.5));index += add;}return index;
}//判断电路是否存在环路, 若不存在环路,得到一个可能的计算顺序(拓扑排序)
bool judge(int n)
{int indegree[N];   //记录下标为i的器件有多少个入度vector<int> next_component[N];  //后驱节点for(int index = 1;index <= n;index ++){   //处理每一个器件门信息stringstream ssin(components[index]);vector<string> words; string w;while(ssin >> w)words.push_back(w);fun[index] = words[0];  //记录当前器件门的功能for(int i = 2;i < words.size();i ++){  //处理每一个输入string in = words[i];int pro_index = string_to_int(in);if(in[0] == 'O'){  //收到其他门的输出indegree[index] ++;  //当前节点的入度加一next_component[pro_index].push_back(index);  //前驱节点的后继节点有indexinput_O[index].insert(pro_index);}else{input_I[index].insert(pro_index);}}}stack<int> s;for(int index = 1;index <= n;index ++){//找出初始入度为0的点if(indegree[index] == 0) s.push(index);}while(!s.empty()){int x = s.top();  s.pop();topo.push_back(x);   //取出栈顶元素int cnt = next_component[x].size();  //后继节点数量for(int i = 0;i < cnt;i ++){int to = next_component[x][i];indegree[to] --;if(indegree[to] == 0) s.push(to);}}if(topo.size() == n) return true;else return false;
}//序号为now的或门件在第s组输入下的输出
void OR(int s, int now)
{int ops;//分别处理两个输入源for(auto index : input_I[now]){ops = input_signal[s][index - 1];if(ops){   //存在一个1就是1output[now] = 1;return;}}for(auto index : input_O[now]){ops = output[index];if(ops){   //存在一个1就是1output[now] = 1;return;}}output[now] = 0;
}
//序号为now的与门件在第s组输入下的输出
void AND(int s, int now)
{int ops;//分别处理两个输入源for(auto index : input_I[now]){ops = input_signal[s][index - 1];if(!ops){   //存在一个0就是0output[now] = 0;return;}}for(auto index : input_O[now]){ops = output[index];if(!ops){   //存在一个0就是0output[now] = 0;return;}}output[now] = 1;
}
//序号为now的非门件在第s组输入下的输出
void NOT(int s, int now)
{//非门只会接收一个输入int ops;for(auto index : input_I[now]){ops = input_signal[s][index - 1];output[now] = (!ops);return;}for(auto index : input_O[now]){ops = output[index];output[now] = (!ops);return;}
}
//序号为now的异或门件在第s组输入下的输出
void XOR(int s, int now)
{int ops;int ans = 0;  //第一个数上来希望得到自己本身,1^0 = 1, 0^0 = 0//分别处理两个输入源for(auto index : input_I[now]){ops = input_signal[s][index - 1];ans ^= ops;}for(auto index : input_O[now]){ops = output[index];ans ^= ops;}output[now] = ans;return;
}
//序号为now的与非门件在第s组输入下的输出
void NAND(int s, int now)
{AND(s, now);int and_res = output[now];output[now] = (!and_res);
}
//序号为now的或非门件在第s组输入下的输出
void NOR(int s, int now)
{OR(s, now);int or_res = output[now];output[now] = (!or_res);
}//对第s组输入进行计算
void compute(int s, int n)
{//按照拓扑排序的顺序进行计算for(int i = 0;i < n;i ++){int now = topo[i];  //当前计算的门件string f = fun[now];if(f == "OR")  OR(s, now);else if(f == "AND") AND(s, now);else if(f == "NOT") NOT(s, now);else if(f == "XOR") XOR(s, now);else if(f =="NAND") NAND(s, now);else if(f == "NOR") NOR(s, now);}
}int main()
{int Q; scanf("%d", &Q);int m, n, s, cnt, index;string line;while(Q --){scanf("%d%d", &m, &n);  //m个输入, n个器件getline(cin, line);for(int i = 1;i <= n;i ++){getline(cin, line);components[i] = line;}bool legal = judge(n);  //判断电路是否存在环路if(!legal) cout << "LOOP" << endl;else{scanf("%d", &s);for(int i = 1;i <= s;i ++){for(int j = 1;j <= m;j ++){int x; scanf("%d", &x);input_signal[i].push_back(x);}}for(int i = 1;i <= s;i ++){compute(i, n);scanf("%d", &cnt);while(cnt --){scanf("%d", &index);printf("%d ", output[index]);}cout << endl;}}//一些数据的清空for(int i = 1;i <= s;i ++) input_signal[i].clear();topo.clear();input_I.clear();input_O.clear();fun.clear();//memset(components, "", sizeof components);memset(output, 0, sizeof output);}return 0;
}