1. 首頁 > 生活百科 > >

control 掌控 方法記錄

生活百科

掌控(control)題面描述公元\(2044\)年 ， 人類進入了宇宙紀元 。L國有\(n\)個星球 ， 分別編號為\(1\)到\(n\)，每一星球上有一個球長 。有些球長十分強大，可以管理或掌控其他星球的球長，具體來說 ， 第\(i\)個星球的球長管理\(k_i+1\)個星球的球長 ， 分別是 \(a_{i1},a_{i2},...,a_{iki}(a_{ij}<i)\) ， 但若想要掌控一個星球的球長，就沒那么容易了，第\(i\)個星球的球長掌控第\(j\)個星球的球長當且僅當他管理的所有球長都掌控第\(j\)個星球的球長，當然，所有球長都掌控他自己 。這些球長要召開\(q\)次會議，每次會議由\(t_i\)個球長召開 ， 所有被他們掌控的球長都會參加 ， 你作為宇宙會議室室長，需要知道每次會議有多少個球長參加 。
輸入第一行一個數\(n\) ， 表示星球的個數；接下來\(n\)行 ， 每一行首先給出一個\(k_i\)（可能為\(0\)） ， 接下來\(k_i\)個數，描述第\(i\)個星球的球長管理的球長 。保證沒有重復；接下來一行，給出一個數\(q\)，表示詢問的個數；接下來\(q\)行，每一行描述一個詢問：格式同上文的格式 。不保證沒有重復（重復的球長當做只出現了一次）
輸出輸出共\(q\)行，第\(i\)行輸出第\(i\)次詢問的答案 。
樣例輸入701 11 11 22 2 302 2 632 2 32 3 52 4 5樣例輸出334樣例解釋對于第一個詢問，2、3號球長都掌控1號球長，所以總共有3個球長參會 ， 編號分別為1，2，3；對于第二個詢問，3、5號球長都掌控1號球長，所以總共有3個球長參會，編號分別為1 ， 3，5；對于第三個詢問 ， 4號球長掌控第1、2號球長 ， 所以總共有4個球長參會，編號分別為1 ， 2 ， 4，5；特別說明：第5號球長沒有掌控球長2，因為3屬于\(k_5\),但2不屬于\(k_3\) 。但球長4掌控球長2，因為球長掌控自己 。

control 掌控 方法記錄

文章插圖
圖片說明：u->v表示v管理u
數據范圍
control 掌控 方法記錄

文章插圖
題解暴力做法（40pts）仔細閱讀數據范圍，發現部分分的\(n,q\)較?。?為了方便處理，我們可以用類似鄰接矩陣的思路來存 。
考慮所有可能需要儲存的信息，我們開以下數組 。
bool vis[N];//i是否與會int con1[N][N];//i管理jint cnt1[N];//i管理的球長數量int con2[N][N];//i掌控jint cnt2[N];//i掌控的球長數量int ans1[N][N];//i的第j個管理的球長為nint ans2[N][N];//i的第j個掌控的球長為n然后依照題意進行模擬，求出每一個球長的掌控情況，最后求出與會者掌控情況的并集即可 。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=2005;int n,q;int final;int meet;//開會bool vis[N];//i是否與會int con1[N][N];//i管理jint cnt1[N];//i管理的球長數量int con2[N][N];//i掌控jint cnt2[N];//i掌控的球長數量int ans1[N][N];//i的第j個管理的球長為nint ans2[N][N];//i的第j個掌控的球長為nint main(){ freopen("control.in","r",stdin); freopen("control.out","w",stdout); scanf("%d",&n); for(int i=1,k;i<=n;i++) {scanf("%d",&k);cnt1[i]=k;for(int j=1,m;j<=k;j++){scanf("%d",&m);con1[i][m]=1;ans1[i][j]=m;} } for(int i=1;i<=n;i++) {ans2[i][1]=i;con2[i][i]=1;cnt2[i]=1; } for(int i=1;i<=n;i++) {if(!cnt1[i]) continue;for(int j=1;j<=n;j++)//i是否掌控j{bool flag=0;for(int l=1;l<=cnt1[i];l++){int nxt=ans1[i][l];//nxt是i管理的第l個球長if(!con2[nxt][j]){flag=1;//nxt無法掌控jbreak;}}if(!flag){con2[i][j]=1;cnt2[i]++;ans2[i][cnt2[i]]=j;}} } scanf("%d",&q); for(int i=1,t;i<=q;i++) {final=0;scanf("%d",&t);memset(vis,0,sizeof(vis));meet=0;for(int j=1;j<=t;j++){scanf("%d",&meet);for(int l=1;l<=cnt2[meet];l++){vis[ans2[meet][l]]=1;}}for(int j=1;j<=n;j++){if(vis[j]) final++;}printf("%d\n",final); } return 0;}正解暴力為什么會寄？首先是存狀態的方式不科學：消耗空間過大，且維護起來相當笨重 。其次是維護的效率低下：純模擬，導致很多不必要的重復運算 。
怎么解決呢？首先來看更好的存狀態方式 。
control 掌控 方法記錄

文章插圖
如圖，倘若想要掌控\(A,B,C\)，那么我們只需要掌控它們的最近公共祖先\(D\)即可，即所有點的掌控關系是一棵樹，新進的節點就應該接到它掌控的所有節點的LCA,即上文的\(D\) 。而我們自然而然就選擇樹形結構來存 。

推薦閱讀