[短期持续更新]Codeforces 构造题一览

说实话我觉得做这种题很没意思(不够硬核),
可是人有短板终究是要补的...起码这种类型补起来相对简单
所以还是把先前准备好的专题放下吧,做点实现上比较休闲的题
ps.为了精简篇幅,代码全部丢到ubuntu上

Codeforces - 483C
题意:给定\(k\),构造\(n\)的某一排列\(p\)满足\(|p_i-p_{i+1}|\)共有\(k\)种不同的值

做法:当\(k\)为\(n-1\)时,分奇偶前后插可满足情况,\(k<n-1\)时从\(k\)处开始排序可消除差异
https://paste.ubuntu.com/p/v92ScdR2WY/

Codeforces - 931C
题意:lpy决定在实验课上抄dzc大佬的实验数据,已知dzc大佬的数据共有n个,其中最大值与最小值之差最多为2,
lpy要魔改这n个数据满足数据的平均值和dzc的平均值一样,且最大值最小值分别不大于不小于dzc的最大值最小值
在此前提下魔改出两个人相同数据最少的方案

做法:最大最小值差小于2时没法修改,直接输出
否则判断把中间的值折为两边还是两边折为中间划算
https://paste.ubuntu.com/p/n5tj848xBZ/

Codeforces - 570C
题意:给定字符串,每两个'.'都可合并为1个'.',求操作到不可再简的次数,注意带修改

做法:上线段树,维护操作数/前缀/后缀三个tag
https://paste.ubuntu.com/p/9YzSbm4Gyh/

Codeforces - 268C
题意:给定n*m整格矩形,求最大的点集满足各点均在点格中且两两距离非整数,(0,0)不可取

做法:显然是按斜线构造,即使是^型走法也是不可以的,那我们按最小边的反对角线走就行(正对角线无法取原点)
https://paste.ubuntu.com/p/hyGv7MVQ43/

Codeforces - 743C
题意:给出\(n\),求\(\frac{2}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\)中的\(x,y,z(x≠y≠z)\)

做法:样例2就暴露做法了,除了1以外x取n,然后y和z可以作差令和为1/x,既分别为n+1和n*(n+1)
https://paste.ubuntu.com/p/YN476hFFVT/

Codeforces - 359B
给出一个\(k,2k≤n\),构造一个长为2n的排列使得\(\sum_{i=1}^{n}|a_{2i-1}-a_{2i}|-|\sum_{i=1}^{n}a_{2i-1}-a_{2i}|=2k\)

使前一项等于后一项+1,则原式等于n-n=0
相邻两项相互交换对前一个和式无影响,后一样相差2,那么交换k对则满足条件

垃圾桶 //做了浪费人生的题目
~~CF731B/CF732C/CF199A/CF740B/CF675B/CF441C/CF625C~~

Greedy

1020C

题意:每人投票一个党派,共m个党派,当某党派的投票数严格大于其他党派时则获胜,每个人有py改投到党派1的价格,求令党派1获胜的最小代价,n,m<3000

题目麻烦在于此消彼长,因此需要减少变量,枚举其他党派小于x且党派1大于等于x的最小代价,其他党派大于等于这个数目的就挑最便宜的人去py,还不够则全局挑剩下最便宜的py

题解说可以\(O(nlogn)\),想不出来啊

https://paste.ubuntu.com/p/VzgMJGf4XG/

628C

题意:给定字符串长为n,构造出同样长为n的与原串各字符距离绝对值之和为k的串

最多能操作的范围是\([0,\sum_{i=1}^{n}maxdis_i]\)

注意到代价是连续的,只要能判断每一步操作之后,后面肯定存在合法解就直接选取,就是说每一步之后都反复套用上面的结论

改的多,代码写的很挫

https://paste.ubuntu.com/p/S3cM4zKp2Z/

557C

题意:一张桌子有\(n<100000\)条腿,每条腿砍掉它需要\(d_i<200\)的费用,桌子稳定仅当最长的边超过存在的腿的一半时满足,问稳定需要的最小代价

如果以某条长为\(len\)的边作为最长边,且数量为\(x\),那么大于\(len\)的边必然被砍,小于\(len\)的边至多能保留\(x-1\)条

此时如果固定了变量\(len\),把\(x\)条腿中砍掉一条,那么小于\(len\)的边至多只能保留\(x-2\)条,显然要花费更多的费用,所以我们至少有小结论,\(len\)的边全部保留

在枚举len的过程,我们可以预处理出\(sum_i\)表示长度\([1,i]\)的全部腿的代价和,那么可以\(O(1)\)求出后面必然被砍的代价和

对于长为\([1,len-1]\)的腿,因为代价至多200,我们用桶来对它们动态地维护,贪心地保留价值最大的\(x-1\)条腿,那么\([1,len-1]\)全部腿-保留的价值最大的腿就是最优的花费

复杂度\(O(n*200)\)

https://paste.ubuntu.com/p/9rVdzHYmfV/

673B

题意:你要制定一套div1和div2,总共有n道题难度依次递增,其中有些题目存在相似性不可以放在同一个div,还要求div1的最低难度要大于div2的最大难度,问题目摆放的方案数(顺序无关)

凭直觉乱搞..

https://paste.ubuntu.com/p/yQz6JyGSF8/

831D

贪心做法说不清道理,暂时搁置

979B

题意:给出三个串,总共n轮操作,每轮操作要求三个字符串必须更改一个字符,求n次操作后哪个字符串有最多的相同字符(仅1个)

易WA水题

很容易想到挑最大的相同字符,其他的尽量覆盖为选定的最大相同字符,若超出字符串长度表明2轮操作等于没有操作a->A->a,超出1轮就长度-1

然而容易忽略的是3轮也是可以的a->A>b>a,也就是说除了1以外都是这样

还有别忘了特判长度为1时怎么改都是1

https://paste.ubuntu.com/p/nHzPZ9DGfx/

558C

827A

题意:有一个字符串，最长1e6，现在给你若干个它的子字符串，每个子字符串长度不超过1e6，最多给你1e5个子字符串，告诉你第i个字符串出现了ki次，并告诉你它每次出现的位置。所有子字符串的长度之和不超过1e6，出现的次数总和也不超过1e6。然后问你最短的满足要求的字符串中字典序最小的那个是什么。

没有覆盖的地方用a来填充最优,由于输入是合法的,只需离线排序逐步处理即可

729C

题意:n辆车,每辆车有价格和油箱容量,k个加油站,每个加油站给出位置,可以在一瞬间补给汽油,汽车有两种用车方式,一种每公里2L油跑1min,一种每公里1L油跑2min,挑最便宜的一辆车使得能在T秒内到达s公里

首先不考虑价格的话油箱越大越占优势,那么按油箱大小排序并且对其进行二分判断找出最小的邮箱满足条件

怎么跑最快就每段加油站距离分类讨论一下

然后从前往后找最小的价格就ok

https://paste.ubuntu.com/p/B5JvTwsgp9/

527D

题意:n个点,每个点有属性a和b,求最大的点集使得集合内任意两点\(|a_i-a_j|≥b_i+b_j\)

很神奇的一道题,把a作为中心,往左右扩展b单位的线段,显然就是求最多的不相交区间,嘴巴AC了

733C

题意:给你n个数，a1,a2,a3,…an,再给你m个数b1,b2,b3,…bm，问你a序列能否通过合并变成b序列。合并的条件为只能相邻的数合并，ai与ai+1能合并的条件为ai> ai+1或ai< ai+1。合并出来的值为ai+ai+1。然后通过新序列合并下去问你能不能达到b序列？能达到的话输出是如何合并的，不能的话输出NO。

922D

题意:给n个只包含‘s’和‘h’的字符串，调整他们的顺序，使拼起来的串含有最多的以‘s’开头以‘h’结尾的字串。

https://blog.csdn.net/pootree/article/details/79632524

https://blog.csdn.net/qq_37383726/article/details/79418097

476D

题意：给一个N，K。要找N个集合，每个集合有四个不同的数字，每个数字只能在一个集合。要让每个集合满足以下条件：
集合中任意两个数字的gcd（最大公约数）为K。
现在要让N个集合中最大的数字最小，并输出方案。

若k=1则找互质的数,k!=1则把前者的集合乘上k,那就简化为只考虑互质的情况

可以发现从某个奇数x开始,x,x+1,x+2,x+4必然互质,偶数每两个必然不互质,所以贪心找奇数的不断顺着构造即可

https://paste.ubuntu.com/p/bw6hfWXHVz/

675C

题意：有n家银行围成一个圈，有个人在有些银行里欠了钱，在一些银行里有存钱，欠的钱总数等于存的钱总数。
现在可以有操作，如果两个银行相邻，那么就能在一个银行转任意多的钱到另一个银行。问最少的操作次数，使得在所有银行的存款钱数都为0

https://blog.csdn.net/hovees/article/details/66983122

270C

题意:小明需要一个大箱子把所有的小箱子装进去，而小箱子又可以把比他小的箱子装入，求小明所需的大箱子的最小 size 是多少

转化为四进制

巴特西