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，因为球长掌控自己。

文章插图
图片说明：u->v表示v管理u
数据范围

文章插图
题解暴力做法（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;}正解暴力为什么会寄？首先是存状态的方式不科学：消耗空间过大，且维护起来相当笨重。其次是维护的效率低下：纯模拟，导致很多不必要的重复运算。
怎么解决呢？首先来看更好的存状态方式。