【0】做题心得 - 2025 NOIP #64 - T2【bitset】

ExFish · 2025-11-18 21:24:30 · 题解

离正解就差一个 bitset。你会发现一个性质就是直接把确定发生的往下扔一定是对的，要是一个已经发生了且它的前驱没有一个是可以不经过 v 就能发生，那么显然此时会导致 v 自己也是对的。这个写出来容易做到 \mathcal O(nm+qn^2)，超时。发现数据范围不是人 2\times 10^9 有两只怎么办呢发现经典 bitset 哦这扯不扯。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e4+10;
int n,m,q,deg[2][N];
bitset<N>ans,upset[N],downset[N];
vector<int>e[N],g[N];
queue<int>Q;
int main(){
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v), deg[0][v]++;
        g[v].push_back(u), deg[1][u]++;
    }
    for(int i=1;i<=n;i++)if(!deg[1][i])
        Q.push(i);
    while(Q.size()){
        int p=Q.front();
        Q.pop();
        upset[p][p]=1;
        for(auto v:g[p]){
            if(!(--deg[1][v]))Q.push(v);
            upset[v]|=upset[p];
        }
    }
    for(int i=1;i<=n;i++)if(!deg[0][i])
        Q.push(i);
    else
        downset[i].set();
    while(Q.size()){
        int p=Q.front();
        Q.pop();
        downset[p]|=upset[p];
        for(auto v:e[p]){
            if(!(--deg[0][v]))Q.push(v);
            downset[v]&=downset[p];
        }
    }
    while(q--){
        int k;
        cin>>k;
        ans.reset();
        while(k--){
            int p;
            cin>>p;
            ans|=downset[p];
        }
        for(int i=1;i<=n;i++)
            if(ans[i]) cout<<i<<" ";
        cout<<"\n";
    }
    return 0;
}