退役II次后做题记录

悠悠 2023-08-17 17:29 50阅读 0赞

# 退役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][http_uoj.ac_submission_364286]

## \[NOI2019\]序列 ##

五堆贪心/px不写了

## AT2446 Rope ##

[https://www.luogu.org/problem/AT2446][https_www.luogu.org_problem_AT2446]

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

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

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

## AT2535 Sparklers ##

[https://www.luogu.org/problem/AT2535][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][https_blog.csdn.net_qq_39972971_article_details_91863290]

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

[http_uoj.ac_submission_364286]: http://uoj.ac/submission/364286
[https_www.luogu.org_problem_AT2446]: https://www.luogu.org/problem/AT2446
[https_www.luogu.org_problem_AT2535]: https://www.luogu.org/problem/AT2535
[https_blog.csdn.net_qq_39972971_article_details_91863290]: https://blog.csdn.net/qq_39972971/article/details/91863290