专栏文章

题解：P14023 [ICPC 2024 Nanjing R] 社交媒体

___ZYX__
P14023题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miny30dg
此快照首次捕获于
2025/12/02 10:14
3 个月前
此快照最后确认于
2025/12/02 10:14
3 个月前
查看原文
我们把所有数对 (x,y)(x,y) 分成三类：
  1. 初始时 x,yx,y 都是我的好友，直接记入答案。
  2. 初始时只有 xx 是我的好友，此时给 cntycnt_y 加 11。cntycnt_y 的含义是只要选择 yy 就会给答案加上 cntycnt_y。
  3. 初始时 x,yx,y 都不是我的好友，这里需要计算一个额外的贡献，对于这样的关系计数，mpx,y←mpx,y+1mp_{x,y} \gets mp_{x,y}+1。
处理后面两类增加的贡献。考虑枚举新增的第一位好友 xx，对于与 xx 不存在第 33 类关系的点 zz，没有额外的贡献，直接选择 zz 中 cntzcnt_z 最大的那个。
对于与 xx 存在第 33 类关系的点 yy，暴力枚举这样的 yy 计算贡献。增加的贡献是 cntx+cnty+mpx,ycnt_x+cnt_y+mp_{x,y}。
由于第 33 类关系只有 O(m)O(m) 个，时间复杂度 O(klog⁡k+m)O(k \log k+m)，瓶颈在于排序。
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int T,n,m,k;
bool cmp(int a,int b){return a>b;}
unordered_map<int,int> cnt,bj,mp[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m>>k;
        cnt.clear();bj.clear();
        for(int i=0;i<=k;i++)mp[i].clear();
        for(int i=1;i<=n;i++){
            int f;
            cin>>f;
            bj[f]=1;
        }
        int ans=0;
        for(int i=1;i<=m;i++){
            int a,b;
            cin>>a>>b;
            if(bj[a]&&bj[b])ans++;
            else if(bj[a])cnt[b]++;
            else if(bj[b])cnt[a]++;
            else if(a==b)cnt[a]++;
            else{
                mp[a][b]++;
                mp[b][a]++;
            }
        }
        vector<int> v;
        for(int i=1;i<=k;i++)
            if(cnt[i]!=0)v.push_back(cnt[i]);
        sort(v.begin(),v.end(),cmp);
        int res=0;
        for(int i=1;i<=k;i++){//新增的第一位好友
            if(bj[i])continue;
            if(!v.empty()){
                if(cnt[i]==v[0]){
                    if(v.size()>=2)res=max(res,cnt[i]+v[1]);
                    else res=max(res,cnt[i]);
                }
                else res=max(res,cnt[i]+v[0]);

            }
            for(auto it=mp[i].begin();it!=mp[i].end();it++){
                res=max(res,cnt[i]+cnt[(*it).first]+(*it).second);
            }
        }
        cout<<ans+res<<'\n';
    }
    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...