当前位置：网站首页>【7.9】代码源 -【选数】【序列操作】【Minimum Or Spanning Tree】

【7.9】代码源 -【选数】【序列操作】【Minimum Or Spanning Tree】

2022-07-17 18:28:00 【ZhgDgE】

试着刷一下代码源的每日一题

#456. 选数

题意：给出 1 1 1 个长度为 n n n 的序列，以及 1 1 1 个正整数 n ( 1 ≤ n ≤ 1 0 5 ) n(1\leq n\leq 10^5) n(1≤n≤105)。问这个原序列中是否存在非空子序列，使其元素之和能被 n n n 整除。

题解：CF557B Modulo Sum/Namomo Spring Camp 每日一题 Week1 Day4 选数

思路：构建前缀和。首先，排除掉某数是 n n n 的倍数的情况；然后，可以发现前缀和的值域为 1 ∼ n − 1 1\sim n-1 1∼n−1 ，由鸽巢原理可知必然有两个前缀和相等。

AC代码：http://oj.daimayuan.top/submission/280624

B. Modulo Sum

题意：将上一题的模数改为 m ( m ≤ 1 ≤ 1 0 3 ) m(m\leq 1\leq 10^3) m(m≤1≤103)

思路：有了上一题的基础，容易知道这题为特判 + DP 转移存在性。

AC代码：https://codeforces.com/contest/577/submission/163381506

#452. 序列操作

题意：给出一个长度为 n ( 1 ≤ n ≤ 1 0 6 ) n(1\leq n\leq 10^6) n(1≤n≤106) 的序列 a a a，有两种操作 q ( 1 ≤ q ≤ 1 0 6 ) q(1\leq q\leq 10^6) q(1≤q≤106) ，一种是给定 x , y x,y x,y 使得 a x = y a_x=y ax​=y ，另一种对所有 a i = max ⁡ ( a i , y ) a_i=\max(a_i,y) ai​=max(ai​,y)

思路：单点修改 + 半区间覆盖。考察每个元素，元素的最终值要么取决于最后一次单点修改，要么取决于若干次半区间覆盖。由于半区间覆盖的性质，那么我们以时间为下标，存下来第二种操作的 y y y ，然后跑一遍后缀 modify i = max ⁡ j = i n ( y ) \text{modify}_i=\max_{j=i}^n(y) modifyi​=maxj=in​(y) 。那么我们处在时间 t t t 的时候，可以取用 modify t \text{modify}_t modifyt​ ，就可以得到时间后缀中的最大的第二种操作。两个取最大即可。

AC代码：http://oj.daimayuan.top/submission/280625

#454. Minimum Or Spanning Tree

题意：求无向连通图的最小按位或生成树。 n ≤ 2 × 1 0 5 , m ≤ 4 × 1 0 5 n\leq 2\times 10^5,m\leq 4\times 10^5 n≤2×105,m≤4×105

思路：从高位向低位贪心。枚举到某一位，如果只选该位为 0 0 0 的边就可以将其连通，则这一位不能为 1 1 1 ，将改为为 1 1 1 的边删去，防止影响后面的判断；否则，只能将该位置为 1 1 1 ，不删去任何点。

AC代码：http://oj.daimayuan.top/submission/280712

原网站

版权声明
本文为[ZhgDgE]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_51948235/article/details/125699101

边栏推荐

猜你喜欢

随机推荐