首页 > 其他分享 >P2391 白雪皑皑 题解

P2391 白雪皑皑 题解

时间:2023-10-31 21:37:38浏览次数:39  
标签:ch P2391 白雪皑皑 题解 ll get times fa le

一种很新的区间染色

题目传送门

题目大意

有 \(n\) 个数初始都为 \(0\) ,有 \(m\) 次操作,第 \(i\) 次将 \((i \times p + q) \bmod n + 1\) 与 \((i \times q + p) \bmod n + 1\) 之间数都改为 \(i\) ,问 \(m\) 次操作后每个数分别是多少。
其中 \(1 \le n \le 10^6 , 1 \le m \le 10^7 , 1 \le m \times q + p , m \times p + q \le 2 \times 10^9\) 。

分析

首先不难想到 倒叙枚举数字 \(i\) ,这样就可以保证修改数字时 只修改数字 \(0\)
可是这样枚举并修改的时间复杂度是 \(O(n \times m)\) 的,明显无法通过本题。
所以我们需要一种算法来实现 区间跳跃 ,换句话说就是实现 维护每个数字左边(右边)第一个为 \(0\) 的数的位置
那么我们就可以想到使用 并查集 来维护这个值,然后进行修改操作就可以了。这样的时间复杂度就是 \(O(mlogn)\) 了。

跑不过暴力

代码

#include<bits/stdc++.h>
#define ll long long
#define ma 2000010
using namespace std;
//---------------------------------
ll read() {
	ll x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
//---------------------------------
ll n, m, p, q;
ll fa[ma];
ll get_fa(ll x) {
	if (fa[x] == x) return x;
	return fa[x] = get_fa(fa[x]);
}
ll col[ma];
//---------------------------------
int main() {
	n = read(), m = read(), p = read(), q = read();
	for (ll i = 1;i <= n;i++) fa[i] = i;
	for (ll i = m;i >= 1;i--) {
		ll l = (i * p + q) % n + 1, r = (i * q + p) % n + 1;
		if (l > r) swap(l, r);
		for (ll j = r;j >= l;j = get_fa(j)) {
			ll t = get_fa(j);
			if (t == j) {
				col[t] = i;
				fa[t] = get_fa(t - 1);// 维护每个数字左第一个为 0 的数的位置
			}
		}
	}
	for (ll i = 1;i <= n;i++) cout << col[i] << endl;
	return 0;
}

为什么维护右边位置就会T呢?

标签:ch,P2391,白雪皑皑,题解,ll,get,times,fa,le
From: https://www.cnblogs.com/mukari/p/17801589.html

相关文章

  • P4397聪明的燕姿 题解 & Miller~Rabin 质数判定
    涉及质数的时间复杂度都是玄学的。——题记传送门由整数唯一分解定理:\(\coprod\limits_{i=1}^{k}p_i^{c_i}\)有该正整数的正约数为:\(\coprod\limits_{i=1}^k(\sum\limits_{j=0}^{c_i}p_i^j)\)即我们要求有多少个数满足\(\coprod\limits_{i=1}^k(\sum\limits_{j=0}^{c_i}p_i^......
  • CF1707 题解
    CF1707题解A考场上1h才出思路...弱智了。我们将参加大于当前智商的行为叫做“摆烂”。我们考虑如果现在摆一次,将来某一次不摆,那么现在不摆,将来那次开摆,中间过程的智商会加1。更优。所以一定一摆就摆到底。而且一定会摆到最后一个。所以我们二分从什么时候开摆,看是否能摆到......
  • 题解:洛谷P3745 期末考试(整数三分)
    题解:洛谷P3745期末考试(整数三分)题目传送门题目大意:给出\(n\)个同学期望出成绩的时间限制\(a_i\)和\(m\)个学科公布成绩的初始时间\(t_i\),1个同学每多等一天就产生A的不愉快度。问通过一番操作后最小的不愉快度之和是多少?操作有两种:1.让学科X的发布时间晚1天,学科......
  • P5404 [CTS2019] 重复 题解
    题目链接观察题目,我们发现直接计算是困难的,先构造单个合法的\(T\)分析其性质。为了构造出\(T\),先考虑构造时\(T\)时什么时候会出现不合法的情况,此时\(T\)会有一段和\(S\)相同的前缀,且这段前缀后面跟着的字符比\(S\)所跟的小。为了避免这种情况出现,我们需要在每次添......
  • CSPRO 历届题目与题解
    官方题目链接:http://118.190.20.162/\(\Huge目录\)201609201612201709202104202109202112202203202206202209202303202305202309\(\Huge\text{CSP201609}\)火车购票问题描述请实现一个铁路购票系统的简单座位分配算法,来处理一节车厢的座位分配。假设一节车厢......
  • AT_abc326_d ABC Puzzle 题解
    AT_abc326_dABCPuzzle题解看题事实上,即使在\(N=5\)的情况下,也只有\(66240\)个网格满足「每行/每列恰好包含一个A、B和C」。——官方题解其实看到这道题,就感觉是搜索,这很显然。但是我们会发现,最最最native的搜索,是\(4^{5\times5}=2^{50}\)的。感觉不大可过,但是......
  • AT_abc326_e Revenge of "The Salary of AtCoder Inc." 题解
    AT_abc326_eRevengeof"TheSalaryofAtCoderInc."题解一道简单的概率论+动态规划题目(然而我赛时没看这道题题意有一个长度为\(n\)的序列\(A\)、一个\(n\)面骰子,掷若干次骰子,如果这一次掷骰子的点数小于等于上一次的点数,则结束。定义这若干次掷骰子的总的结果为,每次......
  • AT_abc326_f Robot Rotation 题解
    AT_abc326_fRobotRotation题解经典问题,以前遇到过一个类似的问题:[ABC082D]FTRobot。建议对比着看一看这两道题,是两种不同的思路。(那一道题不用输出方案,因此可以用bitset优化;而此题需要输出方案,因此需要双向搜索。思路注意到每次只能「左转」和「左转」。所以,偶数次走......
  • AT_abc325_f Sensor Optimization Dilemma 题解
    AT_abc325_fSensorOptimizationDilemma题解Date20231025:修复手滑公式\(\min\)、\(\max\)写反了。动态规划。类似背包问题。朴素算法记\((x,y)\)表示使用\(x\)个(1)传感器、\(y\)个(2)号传感器。设\(f(t,i,j)\)表示覆盖前\(t\)个区间,使用\((i,j)\)传感......
  • AT_abc325_g offence 题解
    AT_abc325_goffence题解一道不难但是需要想一想的区间DP。有一个比较复杂的例子:ooofofxxx,简单的分析可知,一个of后面删除多少,与其前、后都有关,于是考虑区间DP。想到这里,其实问题已经解决一半了。状态设计设\(f(l,r)\)为闭区间\([l,r]\)经过操作之后的最小长度。注......