CCF CSP202009-3点亮数字人生（c++100）

CCF CSP202009-3点亮数字人生

1、利用入度计算拓扑序列，不能拓扑序列就是有环，存储的点为输入为n，元器件为n+m
2、根据拓扑序列计算每个元器件所需的输入的值
3、输出相应元器件的值

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3010;
vector<int>G[maxn],line,V[maxn];
string op[maxn];
int ans[10010][maxn],degree[maxn];
bool vis[maxn];
int n,m;
bool topu(){
int count = 0;
queue<int>q;
for(int i = 1; i <= n+m; i++){
if(degree[i] == 0) {
q.push(i);
line.push_back(i);
count++;
vis[i] = true;
}
}
while(!q.empty()){
int top = q.front();
q.pop();
for(int i = 0; i < V[top].size(); i++){
degree[V[top][i]]--;
if(degree[V[top][i]] == 0 && vis[V[top][i]] == false){
q.push(V[top][i]);
line.push_back(V[top][i]);
vis[V[top][i]] = true;
count++;
}
}
}
if(count == n+m) return true;
else return false;
}
void ele(int row){
for(int i = n+1; i <= n+m; i++){
int j = line[i-1];
if(op[j] == "NOT"){
ans[row][j] = !ans[row][G[j][0]];
}
else if(op[j] == "AND"){
ans[row][j] = 1;
for(int k = 0; k < G[j].size(); k++){
ans[row][j] &= ans[row][G[j][k]];
if(ans[row][j] == 0) break;
}
}
else if(op[j] == "OR"){
ans[row][j] = 0;
for(int k = 0; k < G[j].size(); k++){
ans[row][j] |= ans[row][G[j][k]];
if(ans[row][j] == 1) break;
}
}
else if(op[j] == "XOR"){
ans[row][j] = ans[row][G[j][0]];
for(int k = 1; k < G[j].size(); k++){
ans[row][j] ^= ans[row][G[j][k]];
}
}
else if(op[j] == "NAND"){
ans[row][j] = 1;
for(int k = 0; k < G[j].size(); k++){
ans[row][j] &= ans[row][G[j][k]];
if(ans[row][j] == 0) break;
}
ans[row][j] = !ans[row][j];
}
else if(op[j] == "NOR"){
ans[row][j] = 0;
for(int k = 0; k < G[j].size(); k++){
ans[row][j] |= ans[row][G[j][k]];
if(ans[row][j] == 1) break;
}
ans[row][j] = !ans[row][j];
}
}
}
int main(){
int Q;
cin>>Q;
for(int k = 0; k < Q; k++){
cin>>n>>m;
memset(degree,0,sizeof(degree));
memset(vis,false,sizeof(vis));
for(int i = 1; i <= m; i++){
string s;
int num;
cin>>s>>num;
op[n+i] = s;
degree[n+i] = num;
for(int j = 0; j < num; j++){
cin>>s;
int number = 0;
for(int r = 1; r < s.size(); r++){
number = number * 10 + s[r] - '0';
}
if(s[0] == 'O') number += n;
G[i+n].push_back(number);
V[number].push_back(n+i);
}
}
if(topu()){
int S;
cin>>S;
for(int i = 1; i <= S; i++){
for(int j = 1; j <= n; j++){
cin>>ans[i][j];
}
//计算
ele(i);
}
for(int i = 1; i <= S; i++){
int num;
cin>>num;
for(int j = 1; j <= num; j++){
int number;
cin>>number;
cout<<ans[i][number+n]<<" ";
}
cout<<endl;
}
}
else{
int S;
cin>>S;
for(int i = 1; i <= S; i++){
for(int j = 1; j <= n; j++){
cin>>ans[i][j];
}
}
for(int i = 1; i <= S; i++){
int num;
cin>>num;
for(int j = 1; j <= num; j++){
int number;
cin>>number;
}
}
cout<<"LOOP"<<endl;
}
line.clear();
for(int i = 1; i <= n+m; i++){
G[i].clear();
V[i].clear();
op[i] = "";
}
}
return 0;
}
/**
3
3 6
OR 2 I1 I2
AND 2 I2 I3
XOR 2 O1 O2
NAND 2 O1 O3
NOR 2 O3 O2
NOT 1 O4
3
1 0 0
1 1 0
1 1 1
6 1 2 3 4 5 6
6 1 2 3 4 5 6
6 1 2 3 4 5 6
3 6
AND 2 I2 I3
OR 2 I1 I2
XOR 2 O1 O2
NAND 2 O1 O3
NOR 2 O3 O2
NOT 1 O4
3
1 0 0
1 1 0
1 1 1
6 1 2 3 4 5 6
6 1 2 3 4 5 6
6 1 2 3 4 5 6
3 6
OR 2 I1 I2
AND 2 I2 I3
XOR 2 O1 O2
NAND 2 O1 O3
NOR 2 O3 O2
NOT 1 O4
3
1 0 0
1 1 0
1 1 1
6 1 2 3 4 5 6
6 1 2 3 4 5 6
6 1 2 3 4 5 6
*/

最后

以上就是舒心心锁为你收集整理的CCF CSP202009-3点亮数字人生（c++100）的全部内容，希望文章能够帮你解决CCF CSP202009-3点亮数字人生（c++100）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。