题解：P16437 [XJTUPC 2026] 全都登不上 2

MengTian1120 · 2026-05-10 20:04:41 · 题解

前言

本篇题解的解题方法为：模拟。

题目大意

题目还是比较好理解的。

:::info[题目] 有 n 个机房，分属 m 个小组，第 i 个机房属于小组 a_i。OJ 服务器放在小组 v 的某个机房中。

神秘管理员误操作，将 k 个小组“隔离”了。一个小组被隔离后，该小组内的机房将无法联系其他任何小组的机房。没有被隔离的小组之间都可以正常通信。小组 v 永远不会被隔离。

请你计算：在隔离了这 k 个小组之后，总共有多少个机房仍然能够访问 OJ 服务器。 :::

有 n 个机房，分属 m 个小组，第 i 个机房属于小组 a_i。OJ 服务器放在小组 v 的某个机房中。

管理员将 k 个小组“隔离”。一个小组被隔离后，该小组内的机房无法联系其他任何小组的机房。未被隔离的小组之间均可正常通信。小组 v 永远不会被隔离。

求隔离后，仍然能够访问 OJ 服务器的机房总数。

解题思路

1. 服务器所在小组 v：不会被隔离，其内部所有机房都能直接访问服务器。
2. 其他未被隔离的小组：可与 v 组通信，其内部所有机房也都能访问服务器。
3. 被隔离的小组：无法与其它组通信，且服务器不在本组，其内部机房完全无法访问服务器。

到这里，结论很简单就出来了：

代码实现

我们用一个二维动态数组来存储每个小组包含的机房编号。

其实我这里多余了，只需要统计次数就行了，读者可以试试。

代码实现还是比较简单的。

AC 代码

#include <bits/stdc++.h>
using namespace std;

vector <int> a[100005];
int n,m,k,v;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        int tmp;
        cin>>tmp;
        a[tmp].push_back(i);
    }
    cin>>v;
    int ans=n;
    while(k--){
        int tmp;
        cin>>tmp;
        ans-=a[tmp].size();
    }
    cout<<ans;
    return 0;
}

record

后记

这是本蒟蒻的第 1 篇题解，求过。

给个赞再走呗！