退役II次后做题记录

时间:2020-11-27 22:13:03

退役II次后做题记录

感觉没啥好更的,咕。


atcoder1219 历史研究

回滚莫队。

[六省联考2017]组合数问题

我是傻逼

按照组合意义等价于\(nk\)个物品,选的物品\(\mod k\) 余\(r\)的方案数,直接矩乘优化。

[六省联考2017]相逢是问候

\(c^x\mod p=c^{x\mod \varphi(p)+\varphi(p)}\mod p(x>p)\)

\(\varphi\)跳\(\log\)次就会跳到\(1\)。

用欧拉定理时取膜这么写:int Mod(ll a,int b){return a<b?a:a%b+b;}

[六省联考2017]分手是祝愿

硬推了N久高斯消元,,,差分状态即可

[BJWC2018]Border 的四种求法

暴力(雾

CF809E

好像ts早切过了= =

\(\varphi(ab)=\frac{\varphi(a)\varphi(b)\gcd(a,b)}{\varphi(\gcd(a,b))}\)

认真写一个

\(\sum_i\sum_jdist(i,j)\frac{\varphi(a_i)\varphi(a_j)\gcd(a_i,a_j)}{\varphi(\gcd(a_i,a_j))}\)

\(\sum_i\varphi(a_i)\sum_j\varphi(a_j)dist(i,j)\frac{\gcd(a_i,a_j)}{\varphi(\gcd(a_i,a_j))}\)

\(\sum_d\frac{d}{\varphi(d)}\sum_{d|a_i}\varphi(a_i)\sum_{d|a_j}\varphi(a_j)dist(i,j)[\gcd(a_i,a_j)==d]\)

\(\sum_d\frac{d}{\varphi(d)}\sum_{d|a_i}\varphi(a_i)\sum_{d|a_j}\varphi(a_j)dist(i,j)\sum_{d|o,o|a_i,o|a_j}\mu(\frac{o}{d})\)

\(\sum_o(\sum_{d|o}\frac{d}{\varphi(d)}\mu(\frac{o}{d}))(\sum_{o|a_i}\varphi(a_i)\sum_{o|a_j}\varphi(a_j)dist(i,j))\)

\(d\)部分随便做,右边枚举\(o\)后把\(o\)的倍数拿出来建虚树跑就行了,复杂度两个\(\log\)

还有这个鬼题测了我十几min= =

CF125E

凸优化板子题

然而凸优化边界好**鬼畜,,,WA爆了

二分精度要设小一点(否则就会收获一大片WA

[APIO/CTSC 2007]数据备份

凸优化板子题

学到了正确的凸优化姿势

因为可以存在切不到答案的情况,2分时如果二分到了左边,就用这个值更新答案(赋值),最后直接输出。

uoj339 小Y和二叉树

毒瘤贪心题,首先先序遍历最小的肯定是度数<=2中最小的,找到这个点后向右上和右下扩展,根据一些东西分几种情况,只能向右上/只能向右下/两种方向兜星,然后分情况贪心即可。

http://uoj.ac/submission/364286

[NOI2019]序列

五堆贪心/px不写了

AT2446 Rope

https://www.luogu.org/problem/AT2446

显然一开始先修改好然后直接折,那么修改好的序列要满足一些性质才能折的起来,这个性质就是拿出所有同色极大段,去掉头尾,剩下的长度都是偶数,证明看屎然博客

“剩下的长度都是偶数”说明同种颜色开始位置奇偶性相同

然后枚举一种颜色,枚举奇偶性,要维护一种数据结构,支持+1/-1/取max,直接数组模拟

AT2535 Sparklers

https://www.luogu.org/problem/AT2535

屎题,意识流题解

二分答案,然后可以猜到一堆结论

  1. 一个人火烧完了才会传给下一个人
  2. 没火的人开局都会向中间的火走,碰到了会跟着火走,直到得到火

2可以看成有一个火可以走,其他人会过来给他续命排队枪毙

所有人肯定全速走,火肯定一直在朝一个人走

有两边走进火,如果火向左走,和左边距离会减小,和右边距离不变,向右走一样

火有初始燃烧值\(T\),火每次需要走向一个人花费\(cost=dist/v\)并获得\(value=T\),也就是满足现在燃烧值至少是\(cost\)然后获得\(\Delta=value-cost\)

然后懒得写了,https://blog.csdn.net/qq_39972971/article/details/91863290