退役后做题记录

男娘i 2023-08-17 17:29 114阅读 0赞

# 退役后做题记录 #

--------------------

## AGC030E Less than 3 ##

神仙题Orz

首先，如果你修改了一个位置\\(i\\)，那么\\(i-1\\),\\(i+1\\)一定不同，否则一定会出现连续三个一样的

将0和1之间插入一条红线，1和0之间插入一条蓝线。那么红蓝线一定交替出现

修改相当于移动一条线，移动方案相当于一个匹配（位置1以前、位置n以后可以看做有无数条红蓝交替的线）

最妙的是，“不能出现连续三个一样的”限制没有了（因为一定能找到方案）

枚举匹配的方案即可

[https://atcoder.jp/contests/agc030/submissions/6933519][https_atcoder.jp_contests_agc030_submissions_6933519]

--------------------

## AGC029B Garbage Collector ##

首先，取垃圾的代价固定，为\\(nX\\)，可以无视。

设取了\\(K\\)次垃圾，放垃圾代价就会是\\(KX\\)。

考虑一次取垃圾的过程，取了\\(x\_1<x\_2<\\ldots<x\_s\\)处的垃圾。

显然一定会先走到\\(x\_s\\)，然后返回途中收辣鸡。

推一下，代价会是\\(5x\_s+5x\_\{s-1\}+7x\_\{s-2\}+9x\_\{s-3\}+\\ldots+(2s+1)x\_1\\)。

收了\\(K\\)次辣鸡，会有\\(2K\\)个系数\\(5\\)，\\(K\\)个系数\\(7,9,11,\\ldots\\)，可以任意乘给\\(x\\)

显然最大的\\(2K\\)个拿\\(5\\)，以此类推，前缀和高高就行了

[https://atcoder.jp/contests/agc027/submissions/6921358][https_atcoder.jp_contests_agc027_submissions_6921358]

--------------------

## AGC018C Coins ##

首先消去\\(C\\)。所有\\(A,B\\)变成\\(A-C,B-C\\)，最后答案加\\(\\sum C\\)，就不需要取\\(C\\)了，只要取\\(x\\)个\\(A\\)，\\(y\\)个\\(B\\)。

枚举一条分界线，左右都会从小到大取\\(A/B\\)，用一个堆维护

[https://agc018.contest.atcoder.jp/submissions/6918307][https_agc018.contest.atcoder.jp_submissions_6918307]

--------------------

## LOJ6294 touch ##

我是傻逼

先考虑\\(\\sum\_\{d|x\}\\mu(d)=\[x=1\]\\)，我们要求\\(\\sum\_\{path\}\\sum\_\{d|\\gcd\\\{path\\\}\}\\mu(d)\\)，也就是对所有\\(d\\)求有多少条路径\\(\\gcd\\)是其倍数

分开求跨过不确定边的路径和剩下的，不确定边把树分成了两棵树。

不跨过不确定边的路径直接求，枚举\\(d\\)后，只保留权值是\\(d\\)倍数的边。路径数是\\(\\sum \\binom\{siz\}2\\)，并茶几维护即可

跨过不确定边的路径，\\(u,v\\)分出了两棵树，搜出两棵树所有点到\\(u/v\\)的\\(\\gcd\\)。两棵树的\\(\\gcd\\)记为数组\\(A,B\\)

那么如果不确定的边权为\\(w\\)，这部分答案是\\(\\sum\_\{a\\in A,b\\in B,d|\\gcd(a,b,w)\}\\mu(d)\\)

设\\(s\_i=\\sum\_\{a\\in A,b\\in B\}\[a|i\]\[b|i\]\\)（注意0要特判）可以发现\\(a\\in A,b\\in B\\)会在\\(\\mathbb\{lcm\}(A,B)\\)的倍数处计算一次。

那么如果\\(i|w\\)，答案加上\\(s\_i\\mu(i)\\)，就只会算一次了

[https://loj.ac/submission/573269][https_loj.ac_submission_573269]

--------------------

## CF1205B Shortest Cycle ##

记\\(c\_i\\)表示二进制位有\\(i\\)的数数量，如果有\\(c\_i\\ge 3\\)那么答案就是3了，否则\\(n\\)很小，暴力

--------------------

## CF1205C Palindromic Paths ##

黑白染色后，对于一种颜色，只要确定了一个数就能确定整个颜色的标号，而且黑色已经确定了

然后怎么知道白色的标号呢？？？？？

暴力枚举，找到一个两种情况不同的询问，询问一下就行了。

--------------------

## CF1205D Almost All ##

神仙题

首先选一个点作树根，只考虑经过根的路径

那么先考虑一个问题，在一个大小为\\(n\\)的子树中，让每个点到根的路径长度凑出\\(a,2a,\\ldots,(n-1)a\\)

这个很好构造。先找出所有儿子，分别为\\(son\_1,\\ldots,son\_m\\)，子树大小为\\(siz\_1,\\ldots,siz\_m\\)。根到第\\(i\\)个儿子的边权是\\((1+\\sum\_\{j<i\}siz\_j)a\\)，然后对每个儿子递归下去做。

现在假设选了一个根节点\\(rt\\)，将儿子分为两组\\(A,B\\)，分别做上面的算法，其中\\(A\\)权值是\\(1,2,\\ldots,siz\_A\\)，\\(B\\)权值是\\(siz\_A+1,2(siz\_A+1),\\ldots,siz\_B(siz\_A+1)\\)

那么从\\(A\\)到根节点到\\(B\\)的路径可以凑出来\\(1\\)到\\((siz\_A+1)(siz\_B+1)-1\\)中所有数

考虑怎么将儿子分组，\\((siz\_A+1)(siz\_B+1)-1\\)可以到达\\(\\lfloor\\frac\{2n^2\}\{9\}\\rfloor\\)

显然两边尽量接近才能让结果更优

如果\\(siz\_A,siz\_B\\)都不小于\\(\\lceil\\frac\{n-1\}\{3\}\\rceil\\)，那么最极端的情况就是\\(siz\_A=\\frac\{n-1\}\{3\}\\)，结果\\(\\ge (\\frac\{n+2\}\{3\})(\\frac\{2n+1\}\{3\})-1=\\frac\{2n^2+5n-7\}\{9\}\\)

需要的是\\(\\frac\{2n^2\}\{9\}\\)。结果在\\(n>1\\)时正确，\\(n=1\\)无需考虑。

那么需要选一个根和划分让\\(siz\_A,siz\_B\\geq \\lceil\\frac\{n-1\}\{3\}\\rceil\\)

如果子树数量\\(\\ge 4\\)，一定有两个子树大小之和\\(\\le \\frac n2\\)可以不断合并。

如果子树数量\\(\\ge 3\\)，合并最小的两个子树，剩下那个大小一定\\(\\geq\\frac\{n-1\}\{3\}\\)，那么另一个大小也会\\(\\leq 2\\frac\{n-1\}\{3\}\\)。

子树数量为\\(1\\)只可能是\\(n=2\\)，无需考虑

合并完之后子树数量只可能为\\(2\\)，这时如果有一个子树大小\\(\\ge \\frac\{2\}\{3\}(n-1)\\)就不合法。

选重心做根，最大的子树大小小于等于\\(\\frac\{n\}\{2\}\\)，就合法了。

[https://codeforces.com/contest/1205/submission/59208736][https_codeforces.com_contest_1205_submission_59208736]

转载于:https://www.cnblogs.com/xzz\_233/p/11366234.html

[https_atcoder.jp_contests_agc030_submissions_6933519]: https://atcoder.jp/contests/agc030/submissions/6933519
[https_atcoder.jp_contests_agc027_submissions_6921358]: https://atcoder.jp/contests/agc027/submissions/6921358
[https_agc018.contest.atcoder.jp_submissions_6918307]: https://agc018.contest.atcoder.jp/submissions/6918307
[https_loj.ac_submission_573269]: https://loj.ac/submission/573269
[https_codeforces.com_contest_1205_submission_59208736]: https://codeforces.com/contest/1205/submission/59208736