Gym 100345H Settling the Universe Up

Gym 100345H Settling the Universe Up"/>

Gym 100345H Settling the Universe Up

bitset模板

bitset可以看作bool数组，但优化了空间复杂度和时间复杂度，并且可以像整形一样按位与或。

优化作用：

常常碰到处理的数组只有0和1的变化，此时就可以使用bitset优化。比如求两个集合的交集可以使用按位与运算，求并集可以使用按位或运算

#include<bitset>
biset<32> s(10);  //32位的bitset,赋值为十进制的10
bitset<32> bs("011010101001"); //用字符串初始化
bs[20]=1; //像数值一样对某一位进行操作s=10; //赋值为十进制的10
s.reset();//清零
s.set(); //全部位置放置为1
s.count(); //统计1的个数b.flip(); //把b中所有二进制位逐位取反
b.to_ulong();//用b中同样的二进制位返回一个unsigned long值b1 = b2 ^ b3;//按位异或
b1 = ~b2;//按位补
b1 = b2 << 3;//移位

例题：

Gym 100345H

这是一个有向无环图，可以有拓扑序列

bitset<maxn> f[maxn]; // f[i]保存i的到达信息，其中f[i][j]表示i是否可以到达j

对于任意与i相连的点j,f[i]=f[i]|f[j],f[i][j]=1,更新信息，具体dfs实现，bitset实现压位

修改操作只有1000次，每一次重新建图即可,O(1000*n^2)

查询为O(1)

#include<bits/stdc++.h>using namespace std;const int maxn=210;
int n,m,k;
bool a[maxn][maxn],vis[maxn];
bitset<maxn> f[maxn];void init()
{memset(a,0,sizeof(a));for (int i=1; i<=m; i++){int u,v;scanf("%d%d",&u,&v);a[u][v]=true;}
}void dfs(int x)
{if (vis[x]) return;vis[x]=true;for (int i=1; i<=n; i++)if (a[x][i]){dfs(i);f[x]|=f[i];//bitsetf[x][i]=1;}
}void build()
{memset(vis,0,sizeof(vis));for (int i=1; i<=n; i++) f[i].reset();for (int i=1; i<=n; i++)if (!vis[i]) dfs(i);int sum=0;for (int i=1; i<=n; i++)sum+=f[i].count();printf("%d\n",sum);
}void work()
{build();scanf("%d",&k); getchar();for (int i=1; i<=k; i++){char c,ha;int u,v;scanf("%c%d%d%c",&c,&u,&v,&ha);if (c=='?'){if (f[u][v]) puts("YES"); else puts("NO");} else if (c=='+'){a[u][v]=true;build();} else if (c=='-'){a[u][v]=false;build();}}
}int main()
{freopen("settling.in", "r", stdin);freopen("settling.out", "w", stdout);while(cin>>n>>m){init();work();}fclose(stdin);fclose(stdout);return 0;
}

转载于:.html