一些踩到的坑
- 数据范围: 最多
500
个器件,每个器件最多 5
个输入,所以输入的编号至少为2500
,如果想要把普通输入(没有入度)和器件一起存储,就要开到3010
;
- 初始化:注意初始化的数组范围(我卡在70分就是因为清空
vector
的时候只清空了[1,n]
,应该是[1,n + m]
)
- 全部读入: 不管是否为
”LOOP“
,都要把全部数据都读入。
- 记得用
scanf、printf
: acwing上 cin、cout
超时了。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int M = 10010;
const int N = 3100;
vector<int> e[N];
vector<int> from[N];
int in[N],label[N];
int val[M][N],vis[M][N];
int m,n;
int qq[M];
map<string,int> mp;
void init()
{
mp["NOT"] = 1;
mp["AND"] = 2;
mp["OR"] = 3;
mp["XOR"] = 4;
mp["NAND"] = 5;
mp["NOR"] = 6;
for(int i = 1;i <= n + m;i ++)
{
e[i].clear();
from[i].clear();
}
memset(vis,0,sizeof(vis));
memset(in,0,sizeof(in));
memset(val,0,sizeof(val));
memset(label,0,sizeof(label));
}
int cul(int q,int now)
{
if(now > n) return val[q][now];
if(label[now] == 1) return (!val[q][from[now][0]]);
int fr = from[now][0];
int ans = val[q][fr];
int L = from[now].size();
for(int i = 1;i < L;i ++)
{
fr = from[now][i];
if(label[now] == 2 || label[now] == 5) ans &= val[q][fr];
else if(label[now] == 3|| label[now] == 6) ans |= val[q][fr];
else if(label[now] == 4) ans ^= val[q][fr];
}
if(label[now] == 5 || label[now] == 6) ans = !ans;
return ans;
}
int toplist()
{
int hh = 0,tt = -1;
for(int i = 1;i <= m + n;i ++)
if(in[i] == 0)
qq[++tt] = i;
while(hh <= tt)
{
int now = qq[hh];
hh ++;
for(int i = 0;i < e[now].size();i ++)
{
if( --in[e[now][i]] == 0)
qq[++tt] = e[now][i];
}
}
if(tt == m + n - 1) return 0;
else return 1;
}
int getnumber(string s)
{
int L = s.length();
int num = 0;
for(int i = 1;i < L;i ++)
{
num = num * 10 + s[i] - '0';
}
return num;
}
int main()
{
int T;
scanf("%d", &T);
while(T --)
{
init();
scanf("%d%d", &m, &n);
for(int i = 1;i <= n;i ++)
{
char s[1000];
int cnt;
scanf("%s%d",s,&cnt);
in[i] = cnt;
label[i] = mp[s];
for(int j = 1;j <= cnt;j ++)
{
char input[1000];
scanf("%s",input);
int number = getnumber(input);
if(input[0] == 'I')
{
e[n + number].push_back(i);
from[i].push_back(n + number);
}
else
{
e[number].push_back(i);
from[i].push_back(number);
}
}
}
int q;
scanf("%d", &q);
int ok;
for(int i = 1;i <= q;i ++)
{
for(int j = 1;j <= m;j ++)
{
scanf("%d", &val[i][j + n]);
}
}
ok = toplist();
for(int i = 1;i <= q;i ++)
{
int num;
scanf("%d", &num);
if(ok == 0)
{
for(int k = 0;k < m + n;k ++)
{
val[i][qq[k]] = cul(i,qq[k]);
}
}
for(int j = 1;j <= num;j ++)
{
int o;
scanf("%d", &o);
if(ok == 0)
printf("%d ", val[i][o]);
}
if(ok == 0)
printf("\n");
}
if(ok == 1)
printf("LOOP\n");
}
}