?

3578: GTY的人類基因組計劃2

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?367??Solved:?159
[Submit][Status][Discuss]

Description

? GTY召喚了n個人來做實驗，GTY家的房子很大，有m個房間一開始所有人都在1號房間里，GTY會命令某人去某個房間等待做實驗，或者命令一段區間的房間開始實驗，實驗會獲得一些實驗信息點數，點數為房間里的人數，如果一個房間里的一群人已經做過實驗了那么這些人將不會增加實驗信息點數(不會增加是針對這一群人的，不是對這群人中的每個人，即1,2,3做了實驗，1,2再做實驗還會增加2點實驗點數)

Input

第一行兩個整數n,m,q(n,m,q<=10^5)表示人數，房間數和操作數
接下來q行每行一個操作 "C i j"表示讓第i個人去房間j "W l r" 表示讓區間[l,r]的房間做實驗

Output

對于每一個W操作，輸出一個數，表示此次操作所獲得的實驗點數

Sample Input

3 5 7
C 1 2
C 2 2
W 1 2
C 3 2
W 1 2
C 3 3
W 1 3

Sample Output

3
3
0

HINT

善用STL

Source

By orzpzmaimeng

Solution

這道題是親學長zky出的，學長本人有多種做法：傳送門

這里采用的是DavidLee1999課件中的方法，利用STL亂搞

首先，我們用set去維護可以計入答案的房間，

所以同時會涉及如何對集合Hash，一個神奇的方法：對每個數rand出來一個longlong，對于集合Hash值，就是對于集合中每個數計算異或和

（這里之所以rand出longlong，考慮生日悖論所導致的沖突）

那么這里還需要記錄幾個量：每個房間的人數，每個人所在的房間號，再利用map去記錄每個集合是否用過

那么對于一次移動，我們刪去兩個房間，并且最多加入兩個新房間，所以其本質上有用的房間數是O（Q）級的

那么每次詢問，我們把set中的房間取出統計答案，再標記為已用，并刪掉就好了

Code

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<ctime> #include<cstdlib> #include<set> #include<map> using namespace std; int read() {int x=0,f=1; char ch=getchar();while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}return x*f; } int N,M,Q; #define MAXN 100010 #define MAXM 100010 long long id[MAXN],room[MAXM]; int num[MAXM],pos[MAXN]; map<long long,bool>mp; set<int>st; set<int>::iterator ist; long long GetHash() {return (((long long)rand()<<16) | rand());} void Change(int x,int y) {if (pos[x]==y) return;st.erase(pos[x]); st.erase(y);room[pos[x]]^=id[x]; num[pos[x]]--;if (!mp[room[pos[x]]]) st.insert(pos[x]);pos[x]=y; room[y]^=id[x]; num[y]++;if (!mp[room[y]]) st.insert(y); } void Solve(int x,int y) {int ans=0;for (ist=st.lower_bound(x); ist!=st.end() && *ist<=y; ist=st.lower_bound(x))mp[room[*ist]]=1,ans+=num[*ist],st.erase(ist);printf("%d\n",ans); } int main() {srand(2000+1+4);N=read(),M=read(),Q=read();for (int i=1; i<=N; i++) id[i]=GetHash(),room[1]^=id[i],num[1]++,pos[i]=1;st.insert(1);while (Q--){char opt[10]; scanf("%s",opt);int x=read(),y=read();switch (opt[0]){case 'C' : Change(x,y); break;case 'W' : Solve(x,y); break;}}return 0; }

隨機的話，比較穩妥的是srand（time（0）），但是BZOJ上會RE，那么據說采取妹子的生日會有特殊加成哦（我不會告訴你我用的妹子生日的）

轉載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5671665.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的【BZOJ-3578】GTY的人类基因组计划2 set + map + Hash 乱搞的全部內容，希望文章能夠幫你解決所遇到的問題。

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