暑假集训 || bitset
bitset是一个存储0和1的数组 可以快速的把两个bitset的每一位对应做与或啥的 在可以用01串表示某个状态的时候可以应用到它 就是有两个集合,求它们的交集 bitset <6> a,b,c; a[1] = a[4] = a[5] = 1; b[2] = b[4] = b[5] = b[6] = 1; c = a & b; cout << c << endl; cout << "size = " << c.count() << endl; ? ? HihoCoder 1513 题意:给出n个学生,他们5门课的排名,问对每个学生,每科都有多少人排在它前面 思路:n是30000,n^2在bitset下可以过的,因为每个学生的排名不同,所以bs[i][j]保存第 i 门课,排名为 j 的学生,有哪些人排名比他高 这里要注意储存的状态的选择,因为输出的时候每个学生我们只知道它该门课它的排名,而对于这门课来说,不同排名的人的bs数组肯定是不同的,所以 j 的状态选择即为排名为 j? #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <bitset> using namespace std; const int SZ = 30010; const int INF = 1000000100; int mp[SZ][6]; int a[SZ],b[SZ],c[SZ],d[SZ],e[SZ]; bitset<SZ> bs[5][SZ],ans; int main() { int n; scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d %d %d %d %d",&a[i],&b[i],&c[i],&d[i],&e[i]); mp[a[i]][0] = i,mp[b[i]][1] = i,mp[c[i]][2] = i,mp[d[i]][3] = i,mp[e[i]][4] = i; } for(int i = 0; i < 5; i++) for(int j = 2; j <= n; j++) { bs[i][j] = bs[i][j-1]; bs[i][j][mp[j-1][i]] = 1; //cout << i <<" "<< j <<" "<< bs[i][j] << endl; } for(int i = 1; i <= n; i++) { ans = bs[0][a[i]] & bs[1][b[i]] & bs[2][c[i]] & bs[3][d[i]] & bs[4][e[i]]; printf("%dn",ans.count()); } return 0; } ? Gym 100342J 题意:给n个城市,有些城市间有有向边,求三元环的个数(三元环:A->B->C->A) 思路:想不到bitset哇。。。把每个城市能到达的城市,和能被到达的用bitset表示出来 循环n个城市(A),对每个A找到它能到达的B(用vector存) B能到达的城市,和A能被到达的城市,这两个集合的交集就是C,&一下然后count1的个数即可 #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <bitset> #include <vector> using namespace std; typedef long long LL; const int SZ = 2010; const int INF = 1000000100; int vis[SZ][SZ]; char s[SZ][SZ]; bitset<SZ> bs[2][SZ]; vector<int> v[SZ]; int main() { freopen("triatrip.in","r",stdin); freopen("triatrip.out","w",stdout); int n; scanf("%d",&n); for(int i = 0; i < n; i++) scanf(" %s",s[i]); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(s[i][j] == ‘+‘) { bs[0][i][j] = 1; bs[1][j][i] = 1; v[i].push_back(j); } LL cnt = 0; for(int i = 0; i < n; i++) for(int j = 0; j < v[i].size(); j++) cnt += (LL)((bs[0][v[i][j]] & bs[1][i]).count()); printf("%lldn",cnt/3); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |