题解 20CCF-CSP-T3点亮数字人生
本文最后更新于 32 天前,其中的信息可能已经有所发展或是发生改变。

题目传送门

两次拓扑排序,剩下的就是码力了。

小插曲:用auto遍历会T飞。

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

//本题毒瘤

const int N=3000+5;
const int M=1e5+5;

struct edg{
    int from,to,nxt;
}g[M];

int head[N],cnt;

inline void add(int from,int to){
    g[++cnt].nxt=head[from];
    g[cnt].to=to;
    g[cnt].from=from;
    head[from]=cnt;
}

vector<int> in[N];
int d[N],ans[N];

int m,n,k;

void init(){
    memset(head,0,sizeof head);
    memset(d,0,sizeof d);
    cnt=0;
    for(int i=1;i<=n;i++) in[i].clear();
}

int toint(string s){
    int x=0;
    for(int i=1;i<s.size();i++) x=x*10+s[i]-'0';
    return x;

}

int dd[N];

struct que{
    vector<int> v,v2;
}q[10005];

bool topo1(){
    for(int i=m+1;i<=m+n;i++) dd[i]=d[i];
    queue<int>q2;
    int idx=0;
    for(int i=1;i<=m;i++){
        q2.push(i);
    }
    while(!q2.empty()){
        int u=q2.front();
        q2.pop();
        for(int i=head[u];i;i=g[i].nxt){
            int to=g[i].to;
            dd[to]--;
            if(!dd[to]) q2.push(to),idx++;
        }
        
    }
    return idx==n;
}

string ss[N];

int doit(int x){
    string sss=ss[x];
    if(sss=="NOT") {return (in[x][0]^1);}
    else if(sss=="AND"){
        int res=1;
        for(int i=0;i<in[x].size();i++) res=(res&in[x][i]);
        return res;
    }
    else if(sss=="NAND"){
        int res=1;
        for(int i=0;i<in[x].size();i++) res=(res&in[x][i]);
        return (res^1);
    }
    else if(sss=="OR"){
        int res=0;
        for(int i=0;i<in[x].size();i++) res=(res|in[x][i]);
        return res;
    }
    else if(sss=="XOR"){
        int res=0;
        for(int i=0;i<in[x].size();i++) res=(res^in[x][i]);
        return res;
    }
    else if(sss=="NOR"){
        int res=0;
        for(int i=0;i<in[x].size();i++) res=(res|in[x][i]);
        return (res^1);
    }
    else cout<<"wdnmd"<<endl;
}

void topo2(int x){
    queue<int>q2;
    for(int i=1;i<=m;i++) ans[i]=q[x].v[i-1], q2.push(i);
    for(int i=m+1;i<=m+n;i++) in[i].clear();
    while(!q2.empty()){
        int u=q2.front();
        q2.pop();
        for(int i=head[u];i;i=g[i].nxt){
            int to=g[i].to;
            in[to].push_back(ans[u]);
            if(in[to].size()==d[to]){
                ans[to]=doit(to);
                q2.push(to);
            }
        }
    }
}

int main(){
    int T=read();
    while(T--){
        init();
        m=read();n=read();
   //     cout<<"done"<<endl;
        string s;
        for(int i=1;i<=n;i++){
            cin>>ss[i+m]>>k;
     //   cout<<"done2"<<endl;
            d[i+m]=k;
            for(int j=0;j<k;j++){
                cin>>s;
                int x=toint(s);
                if(s[0]=='I') add(x,i+m);
                else add(x+m,i+m);
            }
        }
        int S=read();
        for(int i=0;i<S;i++){
            q[i].v.resize(m);
            for(int j=0;j<m;j++)  q[i].v[j]=read();
        }

        for(int i=0;i<S;i++){
            k=read();
            q[i].v2.resize(k);
            for(int j=0;j<k;j++)  q[i].v2[j]=read();
        }
        if(!topo1()){
            cout<<"LOOP"<<endl;
        }
        else{
            for(int i=0;i<S;i++){
                topo2(i);
                for(int j=0;j<q[i].v2.size();j++){
                    cout<<ans[q[i].v2[j]+m];
                    if(j!=q[i].v2.size()-1) cout<<" ";
                    else cout<<endl;
                }
            }
        }

    }
    return 0;
}


暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇