- 問題:給出每個人(n<=100000)的五門學科成績,求出所有人:五門學科名次都比自己靠前的同學的人數
學過cdq分治的應該知道,這就是個五維偏序,隻要一維排序,二維分治,然後樹套樹套樹就能輕松搞定了。。。去他媽的
請拉到最下面,先感受一下代碼。開始的确想過用集合,但是兩秒放棄,因為無法用充分利用二進制,集合手動還得合并,而且得到集合的過程也得一一成績對比,好像不可能完成。
oh,然後hihocoder介紹了強無敵的bitset,以前見過,但是沒仔細看,因為那次隻有60位,我好像用string解決的,沒想到有這麼強大(欠打)。
下面介紹以下bitset的基本使用資訊,(大多是别人的東西,篩選後複制過來的),詳細的還請移步百度文庫:
和int long的比較 :
一般,int占4個位元組,long占8個位元組。而一個位元組是由8個位組成的。
粗略估計,int和BitSet的比例為4*8:1,即32:1(因為bitset隻儲存0或者1,一位就夠了)。如果是long,差距就更大了。(是以你能想象開到上億的數組感覺多麼快樂嗎。。。。)
和vector的比較:
類似于vector,bitset類是一種類模闆;而與vector不一樣的是bitset類型對象的差別僅在其長度而不在其類型。在定義bitset時,要明确bitset含有多少位,須在尖括号内給出它的長度值:
bitset<32> bitvec; //32位,全為0。
給出的長度值必須是常量表達式比如16,32,1313520,4008208820,etc。正如這裡給出的,長度值必須定義為整型字面值常量或是已用常量值初始化的整數類型的const對象。
這條語句把bitvec定義為含有32個位的bitset對象。和vector的元素一樣,bitset中的位是沒有命名的,程式員隻能按位置來通路它們。位集合的位置編号從0開始,是以,bitvec的位序是從0到31。以0位開始的位串是低階位(low-order bit),以31位結束的位串是高階位(high-order bit)。
bitset的初始化:
bitset<maxn> b; | b有maxn位,每位都為0 |
bitset<maxn> b(u); | b是unsigned long型u的一個副本 |
bitset<maxn> b(s); | b是string對象s中含有的位串的副本 |
bitset<maxn> b(s, pos, n); | b是s中從位置pos開始的n個位的副本 |
(string和int的方向有點差别,string是從右往左)
本題bitset的巧妙:
22,23行充分利用了相鄰排名的關系,如果不用二進制,一一傳遞很費時。
26,28行充分利用了二進制的交集運算,如果不用二進制,也很麻煩。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<iostream>
4 #include<cstring>
5 #include<algorithm>
6 #include<bitset>
7 using namespace std;
8 const int maxn=30010;
9 int Rank[maxn][6],sa[maxn][6],ans;
10 bitset<maxn+2>Set[maxn][6],tmp;
11 int main()
12 {
13 int n,i,j;
14 scanf("%d",&n);
15 for(i=1;i<=n;i++)
16 for(j=1;j<=5;j++){
17 scanf("%d",&sa[i][j]);
18 Rank[sa[i][j]][j]=i;
19 }
20 for(j=1;j<=5;j++)
21 for(i=2;i<=n;i++){
22 Set[i][j]=Set[i-1][j];
23 Set[i][j].set(Rank[i-1][j]);
24 }
25 for(i=1;i<=n;i++){
26 tmp=Set[sa[i][1]][1];
27 for(j=2;j<=5;j++)
28 tmp&=Set[sa[i][j]][j];
29 printf("%d\n",tmp.count());
30 }
31 return 0;
32 }