"尚学堂杯"哈尔滨理工大学第七届程序设计竞赛D--Distinct Package Manager

    xiaoxiao2021-03-25  166

    http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2328

    题意:就是有n个软件0–n-1 之后每个软件安装需要提前安装其他软件。之后把依赖关系给出,当然第0个软件不依赖任何软件。最后给出q次查询,每次查询询问安装软件x需要的体现安装软件的个数,或者删除软件x需要删除软件的个数。0 0

    好吧,我在赛场上第一个想到的是并查集,但WA后发现,我理解有误,之后发现这就是个模拟题,之后转用vector,但发现0 0…………继续WA,之后发现原因是我忘记了软件之间可以相互制约。 就是 安装软件2依赖于软件3,软件3依赖于软件4,那么我们就在安装软件2的时候安装上软件3和4………………之后我们再安装软件3时就不需要安装了,因为安装软件2已经安装完毕。

    #include <iostream> #include <algorithm> #include <stdio.h> #include <vector> #include <set> #define ins(x) insert(x) #define maxs 202020 #define pb(x) push_back(x) #include <string.h> #include <bits/stdc++.h> #define mme(i,j) memset(i,j,sizeof(i)) #define lbt(x) (x&-x) #define ll long long using namespace std; vector<int>depend[105]; vector<int>depended[105]; char s[23]; bool isInstall[200]; int Install(int x) { if(isInstall[x]) return 0; isInstall[x]=1; int ans=0; for(int i=depend[x].size()-1;i>=0;i--) ans+=Install(depend[x][i]); return ans+1; } int Unstall(int x) { if(!isInstall[x]) return 0; isInstall[x]=0; int ans=0; for(int i=depended[x].size()-1;i>=0;i--) ans+=Unstall(depended[x][i]); return ans+1; } int main() { int t,n,m; scanf("%d",&t); while(t--) { mme(isInstall,0); scanf("%d",&n); for(int i=0;i<=n;i++) { depend[i].clear(); depended[i].clear(); } int m,x; for(int i=1;i<n;i++) { scanf("%d",&m); while(m--) { scanf("%d",&x); depend[i].pb(x);// i 依赖 x depended[x].pb(i);// x 被 i 依赖 } } int q; scanf("%d",&q); while(q--) { scanf("%s%d",s,&x); if(s[0]=='i') { printf("%d\n",Install(x)); } else if(s[0]=='u') printf("%d\n",Unstall(x)); } } return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-3670.html

    最新回复(0)