当前位置: 首页 > news >正文

P8250 交友问题

P8250 交友问题https://www.luogu.com.cn/problem/P8250


题面描述:

一个有n个点m条边的无向简单图

每次询问u,v,问与u相邻且不为v的点中有多少个的点不与v相邻


题解:

正难则反,我们考虑有多少个点为v或与v相邻,在用u.size()减去即可

首先,让我们抛弃大O,先来思考暴力,

暴力1:我们对每个点开一个bitset,每次询问直接返回两个bitset相与的结果,时间复杂度O(\frac{nq}{w})

暴力2:我们开一个桶,每次将v的所以邻居加入桶,再用计算其中u的邻居的出现次数时间复杂度O(nq)

正解:

考虑将他们融合根号分治!!!

设置一个阈值T,将入度大于T的称为重点,入度小于等于T的称为轻点

因为图中一共只有2m个入度,所以当我们将阈值T设为sqrt(2m)时,即可将重点个数定为根号级

分四种情况讨论

1.(重,重) 采用暴力1的做法,O(\frac{nq}{w})

2.(轻,轻) 采用暴力2的做法,O(\frac{nq}{T})

3.(重,轻) 枚举轻点的邻居,利用重点的bitsetO(1)判断,O(\frac{nq}{T})

4.(轻,重) 与情况3相同,O(\frac{nq}{T})

在T取\sqrt{2m}时,情况1时间复杂度仍为O(\frac{nq}{w}),较为危险,容易别卡常,因此考虑面向数据编程

我们开桶记录答案,使答案变为O(\frac{(\frac{m}{T})^2n}{w}),即O(\frac{m^2n}{T^2w}),于是将T开大一点,实测T=1000可过

其实不加也可以

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,q,rd[N],cnt,anss[1100][1100];
vector<int>a[N];
bitset<N>vis[1100];
bool mp[N];
int main()
{memset(anss,-1,sizeof(anss));scanf("%d%d%d",&n,&m,&q);int k=1000;for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);a[x].push_back(y);a[y].push_back(x);}for(int i=1;i<=n;i++){if(a[i].size()<=k) continue;rd[i]=++cnt;vis[cnt][i]=1;for(auto it:a[i]) vis[cnt][it]=1;}while(q--){int x,y,ans=0;scanf("%d%d",&x,&y);if(x==y){printf("0\n");continue;}if(a[x].size()>k&&a[y].size()>k){if(anss[rd[x]][rd[y]]!=-1) ans=anss[rd[x]][rd[y]];else ans=anss[rd[x]][rd[y]]=(vis[rd[x]]&vis[rd[y]]).count()-(vis[rd[x]][y]);}if(a[x].size()>k&&a[y].size()<=k){for(auto it:a[y]) if(vis[rd[x]][it]) ans++;}if(a[x].size()<=k&&a[y].size()>k){for(auto it:a[x]) if(vis[rd[y]][it]) ans++;}if(a[x].size()<=k&&a[y].size()<=k){mp[y]=1;for(auto it:a[y]) mp[it]=1;for(auto it:a[x]) ans+=mp[it];for(auto it:a[y]) mp[it]=0;mp[y]=0;}printf("%d\n",a[x].size()-ans);}return 0;
}

http://www.lryc.cn/news/613007.html

相关文章:

  • 如何理解“信号集是位掩码,每个bit代表一个信号”这句话?
  • QtC++ 中使用 qtwebsocket 开源库实现基于websocket的本地服务开发详解
  • UE5多人MOBA+GAS 39、制作角色上半身UI
  • Redis中间件(四):主从同步与对象模型
  • HarmonyOS系统 读取系统相册图片并预览
  • 基于django的非物质文化遗产可视化网站设计与实现
  • Jenkins全链路教程——Jenkins项目创建与基础构建
  • 2025年机械工程与自动化技术国际会议(ICMEAT 2025)
  • 单链表专题---暴力算法美学(1)(有视频演示)
  • Numpy科学计算与数据分析:Numpy数组索引与切片入门
  • 【论坛系统自动化功能测试报告】
  • 动手学深度学习(pytorch版):第一节——引言
  • 具身智能机器人 - Reachy Mini
  • MyCAT实战环节
  • 考研复习-计算机组成原理-第三章-存储系统
  • 微服务平台需求-部署一体化文档V1.0
  • cv2.threshold cv2.morphologyEx
  • Ubuntu 25.04 安装 pyenv 并配置多个 python 版本
  • Java并发与数据库锁机制:悲观锁、乐观锁、隐式锁与显式锁
  • 构建一个简洁优雅的 PHP 参数验证器 —— php-schema-validator
  • 金仓KingbaseES逻辑架构,与Oracle/MySQL对比
  • Python实现点云随机一致性(RANSAC)配准——粗配准
  • (Python)Python爬虫入门教程:从零开始学习网页抓取(爬虫教学)(Python教学)
  • 利用vue.js2X写前端搜索页面,express写后端API接口展现搜索数据
  • python数据结构与算法(基础)
  • DrissionPage自动化:高效Web操作新选择
  • 怎么在本地引入字体
  • 深入解析嵌套事务:原理与应用
  • 基于langchain的两个实际应用:[MCP多服务器聊天系统]和[解析PDF文档的RAG问答]
  • HTTP 协议升级(HTTP Upgrade)机制