首页 > 其他分享 >P2391 白雪皑皑(并查集)

P2391 白雪皑皑(并查集)

时间:2023-08-03 10:56:48浏览次数:42  
标签:10 P2391 fa int 查集 雪花 times leq 白雪皑皑

P2391 白雪皑皑(并查集)

https://www.luogu.com.cn/problem/P2391

题目背景

“柴门闻犬吠,风雪夜归人”,冬天,不期而至。千里冰封,万里雪飘。空中刮起了鸭毛大雪。雪花纷纷,降落人间。 美能量星球(pty 在 spore 上的一个殖民地)上的人们被这美景所震撼。但是 pty 却不高兴,他不喜欢白色的世界,他觉得这样太单调了。所以他想对雪花进行染色,让世界变得多彩些。

题目描述

现在有 \(n\) 片雪花排成一列。 pty 要对雪花进行 \(m\) 次染色操作,第 \(i\) 次染色操作中,把第 \(((i\times p+q)\bmod n)+1\) 片雪花和第 \(((i\times q+p)\bmod n)+1\) 片雪花之间的雪花(包括端点)染成颜色 \(i\)。其中 \(p,q\) 是给定的两个正整数。他想知道最后 \(n\) 片雪花被染成了什么颜色。没有被染色输出 \(0\)。

输入格式

输入共四行,每行一个整数,分别为 \(n,m,p,q\),意义如题中所述。

输出格式

输出共 \(n\) 行,每行一个整数,第 \(i\) 行表示第 \(i\) 片雪花的颜色。

样例 #1

样例输入 #1

4
3
2
4

样例输出 #1

2
2
3
0

提示

  • 对于 \(20\%\) 的数据满足:\(n,m\leq 1000\)。
  • 对于 \(40\%\) 的数据满足:\(n\leq 8000\),\(m\leq 10^6\)。
  • 对于 \(80\%\) 的数据满足:\(n\leq 5\times 10^5\),\(m\leq 10^7\)。
  • 对于 \(100\%\) 的数据满足:\(1\leq n\leq 10^6\),\(1\leq m\leq 10^7\)。

保证 \(1\leq m\times p+q,m\times q+p\leq 2\times 10^9\)。

思路

前面已经染过的颜色会被最后染的颜色覆盖,所以倒着求解:如果当前染色区间存在没被染过的点就把他染上(最终颜色一定是当前染上的色)。并查集维护连通性:\(fa_i\) 表示 \(i\) 后第一个可操作的点。

Code

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 5, M = 1e7 + 5;
int n, m, p, q;
int fa[N], ans[N]; //fa[i]: i后第一个可操作的点

int find (int x) {
    if (x != fa[x])     fa[x] = find (fa[x]);
    return fa[x];
}

int main () {
    cin >> n >> m >> p >> q;
    for (int i = 1; i <= n; i++)    fa[i] = i;
    for (int i = m; i >= 1; i--) {
        int l = (i * p + q) % n + 1, r = (i * q + p) % n + 1;
        if (l > r)  swap (l, r);
        for (int j = r; j >= l; j = fa[j]) {
            int fj = find (j);
            if (fj == j)    ans[j] = i, fa[j] = find (j - 1);
        }
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << endl;
}

标签:10,P2391,fa,int,查集,雪花,times,leq,白雪皑皑
From: https://www.cnblogs.com/CTing/p/17602674.html

相关文章

  • 并查集
    一般用于合并集合并查找集合1intfind(intx){//查找x的祖先2if(pre[x]==x)returnx;3returnpre[x]=find(pre[x]);//压缩路径4}5voidjoin(intx,inty){6intfx=find(x),fy=find(y);//查找这两个数的祖先7if(fx!=fy)pre[......
  • 闲置资源优化,轻松检查集群中的空闲成本
    作者:梁成昊(景祁)前言Kubernetes提供了对计算、网络、存储资源的抽象,提升了集群资源管理的效率。然而,由于用户不需要直接管理底层资源,可能导致部分闲置资源未及时发现,造成成本浪费。在企业IT成本治理过程中,如何发现并处理这部分资源,是成本优化的重要环节。为解决上述问题,阿里......
  • [并查集] 题单刷题摘要
    题单1.P6121[USACO16OPEN]ClosingtheFarmGP3144[USACO16OPEN]ClosingtheFarmS(逊版)思路\(\scr{Solution}\)每一时刻关闭农场,求是否全联通。也就是维护将单个集合分成多个集合。很容易想到爆搜算法,用vector邻接表建图,每次跑完图就将当前点的连边关系删去。复杂度......
  • luogu P3733 [HAOI2017] 八纵八横 题解【线段树分治+线性基+可撤销并查集+bitset】
    目录题目大意解题思路code题目大意题目链接给出一张\(n\)个点\(m\)条边的连通无向图,边带边权\(w_i\)。有以下三种操作,共\(q\)次:\(\centerdot\)在点\(x,y\)之间加入一条边权为\(w_i\)的边,如果这是第\(i\)个此种操作,则记这条新边为第\(i\)条。\(\centerdot\)将第\(k......
  • 并查集优化 - 按大小合并时间复杂度证明
    并查集优化-按大小合并时间复杂度证明if(sz[b[x]].size()>sz[b[y]].size())swap(x,y);对于每个元素,当它当前所在的集合中,需要有其它大于该集合大小的集合,才会被遍历如果元素在一个大小\(1\)的集合中,会转移到大小\(2\)的集合中如果元素在一个大小\(2\)的集合中,会......
  • 并查集
    简述并查集其实是一个很有用的算法(至少我是这么认为的),很简单,代码也很好写,今天突然想写一下并查集。直接讲并查集不太好说,我们先看下面这一道题:洛谷P3367【模板】并查集【模板】并查集题目描述如题,现在有一个并查集,你需要完成合并和查询操作。输入格式第一行包含两个整数......
  • 超市-并查集应用
    【超市】【问题描述】超市里有N件商品,每个商品都有利润pi和过期时间di,每天只能卖一件商品,过期商品(即当天di<=0)不能再卖。求合理安排每天卖的商品的情况下,可以得到的最大收益是多少。【输入格式】输入包含多组测试用例,测试用例最多30组。每组测试用例,以输入整数N开始,接下里输......
  • 并查集-讲课内容补全(未完
    施工中......先在这里给出我的并查集模板以下为比较常用的路径压缩intf[MAXN],n,m;voidclean(){for(inti=1;i<=n;i++)f[i]=i;}intfind(intx){if(x!=f[x])f[x]=find(f[x]);returnf[x];}voidadd(intx,inty){intfx=find(x),fy=find(y......
  • The Third Letter带权并查集
    Problem-1850H-Codeforces题意是给你a,b,c说明a在b后面c个单位(c<0就是在左边),每个位置只能有一个数,一共有n个位置,告诉你m个关系,问是否符合条件我们可以设置d[x]表示x到它的最早的父节点的距离,然后如果两个数父节点一样,那么c!=d[a]-d[b]时就说明不符合条件那么对于并查......
  • 算法刷题笔记--并查集的运用
    1、题目描述:一个城市中有两个犯罪团伙A和B,你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为,警察所获得的信息是有限的。假设现在有N起案件(N<=100000),编号为1到N,每起案件由团伙A或团伙B所为。你将按时间顺序获得M条信息(M<=100000),这些信息分为两类:D[a][b]其中[a]和[b]表示两......