題目鏈接：點擊查看

題目大意：給出一張 n 個點和 m 條邊組成的有向無環圖，每個節點都有一個開關和一個燈泡，初始時節點 1 的燈泡是亮的，每次操作開關可以將當前燈泡的狀態置反，且會對子節點的開關產生連鎖反應，問至少需要操作多少次才能將所有的燈泡關上

題目分析：看到有向無環圖首先想到拓撲，但是如果暴力拓撲轉移每個點的狀態的話，時間復雜度是 n * n 級別的，必定會超時，但是看到數據范圍其實有經驗的同學就會想到利用 bitset 優化了，可以優化掉 64 層的時空復雜度，經過優化后的時空復雜度就可以暴力轉移了，令每個節點都維護一個 bitset 變量，記錄一下前面有哪些節點會影響到該節點，如果有奇數個節點影響到了該節點的話，因為每個燈泡初始時都是滅著的，所以需要利用一次操作將其關閉，如果是偶數個則直接跳過即可，每次利用位運算向下傳遞狀態就好了

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=4e4+100;bitset<N>b[N];vector<int>node[N];int du[N],n,m;int topo() {int ans=0;queue<int>q;q.push(1);b[1][1]=1;while(q.size()){int u=q.front();q.pop();if(b[u].count()&1){b[u][u]=1;ans++;}for(auto v:node[u]){b[v]|=b[u];if(--du[v]==0)q.push(v);}}return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%d%d",&n,&m);while(m--){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);du[v]++;}printf("%d\n",topo());return 0; }

?

總結

以上是生活随笔為你收集整理的牛客 - Strange Bulbs(bitset优化拓扑)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。