首页 > 其他分享 >P8907 [USACO22DEC] Making Friends P 题解

P8907 [USACO22DEC] Making Friends P 题解

时间:2023-11-22 16:45:31浏览次数:42  
标签:gf int 题解 P8907 fa 加进来 Making size define

明明看着不难的题目,却意外的卡人。

思路

考虑两头奶牛可以成为朋友条件是什么。

存在一条路径连接这两头奶牛。

且除去端点外的路径上的所有点的编号小于两端点的较小值。

充分必要性都比较显然。

如何维护。

我们可以从小到大加入点,维护这些路径。

对于每个点维护一个 \(\text{set}\)。

表示这个点所在的联通块可以去到的还没有加进来的点有多少个。

因为没有加进来的点都比已经加进来的点要大。

那么可以启发式合并维护一下就可以了。

Code

/**
 * @file P8907.cpp
 * @author mfeitveer
 * @date 2023-11-22
 * 
 * @copyright Copyright (c) 2023
 * 
 */
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
#define dbg cerr << "Line " << __LINE__ << ": "
#define EVAL(x) #x " = " << (x)

typedef int64_t i64;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef pair<int, int> PII;

bool ed;

const int N = 1000010;
const int mod = 998244353;

int n, m, fa[N]; i64 ans = 0;
vector<int> to[N];
set<int> q[N];

inline void merge(int x, int y)
{
	if(q[x].size() < q[y].size())
		swap(q[x], q[y]);
	for(auto i : q[y]) q[x].insert(i);
	q[y].clear();
}
inline void calc(int x, int y)
{
	while(q[x].empty() == 0 && *q[x].begin() <= y)
		q[x].erase(q[x].begin());
}
inline int gf(int x)
	{ return fa[x] == x ? x : fa[x] = gf(fa[x]); }
inline void solve()
{
	cin >> n >> m;
	fro(i, 1, m)
	{
		int x, y;
		cin >> x >> y;
		to[x].push_back(y);
		to[y].push_back(x);
	}
	iota(fa + 1, fa + n + 1, 1);
	fro(i, 1, n)
	{
		sort(to[i].begin(), to[i].end());
		for(auto j : to[i]) if(j > i)
			q[i].insert(j);
		int num = q[i].size();
		for(auto j : to[i]) if(j < i && i != gf(j))
			merge(i, gf(j)), fa[gf(j)] = i;
		calc(i, i), ans += q[i].size() - num;
	}
	cout << ans << "\n";
}

bool st;

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	double Mib = fabs((&ed-&st)/1048576.), Lim = 256;
	cerr << " Memory: " << Mib << "\n", assert(Mib<=Lim);
	solve();
	return 0;
}

标签:gf,int,题解,P8907,fa,加进来,Making,size,define
From: https://www.cnblogs.com/mfeitveer/p/17849672.html

相关文章

  • 【luogu题解】P9749 [CSP-J 2023] 公路
    \(Meaning\)\(Solution\)这道题我来讲一个不一样的解法:\(dp\)在写\(dp\)之前,我们需要明确以下几个东西:状态的表示,状态转移方程,边界条件和答案的表示。状态的表示\(dp[i]\)表示到达第\(i\)个站点所需要的最少钱数,\(w[i]\)表示在使用最少钱数到达第\(i\)个站点时多余......
  • 【模板】最小度限制生成树 题解
    其他的题解感觉都好高级,分享一种好想且好实现的方法。我们可以先把点\(s\)和与其相连的边都删除,我们发现剩下的部分变成了一些连通块。我们不难发现,当要求与\(s\)点相连的边的个数为\(k\)时,我们的连通块个数显然是\(k\)的。接下来这个问题就转化成了:\(n-1\)个点中生......
  • [IOI2015] Teams 题解
    妙妙题。不难发现,我们对于每个\(k\)取出的人都是满足\(a_i\leqk\leqb_i\)的。经典的,我们直接将\((a_i,b_i)\)转化到二维平面上,将它转化成一个二维数点问题。我们对于每一个询问,都使\(k\)有序,从小到大贪心的选择,也就相当于\(x\)轴限制不断向右,\(y\)轴限制不断......
  • zookeeper3.5.5以上8080端口占用问题解决
    zookeeper3.5.5启动默认会把AdminService服务启动,这个服务默认是8080端口,是一个通过jetty启动的管理控制台,一般不会用到,网上的复制粘贴就是来自同一个办法如下:方法一、删除jetty方法二、修改端口。修改方法的方法有两种:在启动脚本中增加-Dzookeeper.admin.serverPort=你的端......
  • P9868 题解
    blog。NOIP2023T1。可以对字符串随意交换,即可以重排每个单词。对于询问\(i\),最优方案显然是将\(\forallj\nei\)的\(w_j\)重排至字典序最大,将\(w_i\)重排至字典序最小。这件事情本质是将\(w_i\)与\(\min\limits_{j\nei}w_j\)比较。在开始时将全部串重排至字典序......
  • 【AGC】鸿蒙应用软件包上传问题解析
    ​【问题背景】近期收到了一些反馈,一些鸿蒙元服务开发者在发布应用市场的过程中,上传.app包时遇到了不同的报错,导致上传失败,下面来看一下这些报错的具体原因,如何正确打包上传。 【问题描述1】HarmonyOS元服务软件包上传后,提示“软件包解析失败,请重新上传”,错误详情(5)​​​【......
  • T401305 平面划分(easy) 题解
    LinkT401305平面划分(easy)Solution平面上\(n\)条直线所划分处的区域最大个数\(L_n\)是多少我们考虑假设已经有\(n-1\)条直线,我们需要画一条直线,这条直线最多和\(n-1\)条直线相交产生\(n\)个新的区域所以我们得到了\[\begin{align*} &L_0=1\\ &L_n=L_{n-1}......
  • jsmpeg视频播放器使用方法和常见问题解决方案
    JSMpeg是一个使用JavaScript编写的视频播放器,它可以在浏览器中播放MPEG1视频和MP2音频流。JSMpeg的特点是它能够通过WebSockets实时传输视频流,并且可以在不支持HTML5视频播放器的浏览器上运行。以下是JSMpeg的基本使用方法和一些常见问题的解决方案:主要用来解决移移动端视频播放问......
  • [ABC328D] Take ABC 题解
    链接如果只是扫一遍肯定是不行的,所以我们使用一个栈,遇到C就判断栈顶的两个元素是不是分别为B和A。这样就能做出来这道题了。代码#include<bits/stdc++.h>usingnamespacestd;strings;charstk[200010];intmain(){ cin>>s; intn=s.size(),p=0;//字符串长度和......
  • 【树链剖分】P3401 洛谷树 题解
    P3401考虑先将路径权值进行转化,因为很难对路径直接进行统计。考虑如何表示出这条路径的权值。记\(s_i=\oplus_{j\in\text{path}(1,i)}w_j\),其中\(\text{path}(i,j)\)表示\(i\)到\(j\)的路径上的边集。则\(u\tov\)的路径的权值为\(s_u\opluss_v\)。现在转变为......