zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15778453.html 比赛总结 分数：100+100+48+30 个人认为，T2乱搞竟然是正解，而T3看到 10710^7107 就一直在想 O(n)O(n)O(n) 做法，但其实打 O(nlog⁡n)O(n\log n)O(nlogn) 就行了。 而当时我在赛场上懒得打 O(nlog⁡n)O(n\log n)O(nlogn)，就随便糊了一个 O(nn)O(n\sqrt n)O(nn​) 的做法上去。这启示着我，有些时候 O(nlog⁡n)O...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15780513.html 题目链接 题目 定义f(n)=∣n−∑d∣n,d≠nd∣f(n) = |n - \sum_{d|n,d\not =n}d|f(n)=∣n−∑d∣n,d=n​d∣。 每次给出A,BA,BA,B，求∑i=ABf(i)\sum_{i=A}^B f(i)∑i=AB​f(i)。 对于100%100\%100%的数据，A,B≤107A,B\le 10^7A,B≤107。 思路 看到 A，BA，BA，B 的范围，想着能不能快速求 ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15780442.html 成绩： （惨败） A题，写成一个函数，题目怎么说就怎么做。 B题，直接 O(n2)O(n^2)O(n2) 枚举，调了好久，最后发现是欧式距离写错了。于是我得到了经验，欧式距离不能再记错了（dis=(xi−xj)2+(yi−yj)2dis=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}dis=(xi​−xj​)2+(yi​−yj​)2​）。 C题一看，拿出计算器算了一下前几个样例，发现就是输出一个数的二进制，...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15778576.html 题目链接 题目 给定两个长度为 nnn 的只包含’a’,‘b’,'c’的字符串s,ts,ts,t。 请打乱串 sss，使得 ∀i,si≠ti\forall i,s_i \not= t_i∀i,si​=ti​，且 sss 字典序最小。 思路 对于 ttt 串中从前往后每一个字母，在 sss 的剩余可选字母中选字典序最小的。 如果 sss 的剩余字母中没了，就往前找第一个可以替换的替换。 最后再对每种 ttt 中的字母按...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15778449.html 题目链接 题目 给定一个数字 NNN，请问有哪些区间 [L,R][L,R][L,R] 使得 ∑i=LRi=N\sum_{i=L}^R i=N∑i=LR​i=N。 请按 LLL 从小到大的顺序输出所有区间。 思路 根据题意我们可以列出方程： (L+R)(R−L+1)2=n\frac{(L+R)(R-L+1)}{2}=n 2(L+R)(R−L+1)​=n 也就是： (L+R)(R−L+1)=n×2(L+R)(R-L+1)=n...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15774893.html 题目链接 题目 一年一度的展会要来临了，Farmer John 想要把 NNN（1≤N≤100,0001 \leq N \leq 100,0001≤N≤100,000）只奶牛和公牛安排在单独的一行中。 John 发现最近公牛们非常好斗；假如两只公牛在这一行中靠的太近，他们就会吵架，以至于斗殴，破坏这和谐的环境。 John 非常的足智多谋，他计算出任何两只公牛之间至少要有 KKK（0≤K<N0 \leq K \lt ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15774512.html 题目链接 题目 给定一个多项式 (by+ax)k(by+ax)^k(by+ax)k，请求出多项式展开后 xn×ymx^n\times y^mxn×ym 项的系数。 思路 根据二项式定理 (a+b)k=∑i=0kCkiaibk−i(a+b)^k=\sum_{i=0}^kC_{k}^ia^ib^{k-i}(a+b)k=∑i=0k​Cki​aibk−i 我们可以把原式变为： (ax+by)k=∑i=0nCkiaibk−ixiy...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15731432.html GDKOI前我的算法复习情况： 好了，GDKOI死了。 这个是根据一本通提高篇章节制定的。 练习 剩余题量 备注 练习 剩余题量 备注 练习 剩余题量 备注 练习 剩余题量 备注 贪心算法 已完成 区间DP 1 质数 5 同余 8 二分三分 已完成 RMQ 1 我做出的两题都不是用平衡树 状压dp 5 斜率优化 9 差分约束 已完成 矩阵乘法 2 有时间再做，luogu上都有 约数 ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15730268.html 丽泽普及2022交流赛day1总结 提交情况 8:52 T1 9:19 T3 9:26 T4 9:28 T4 10:32 T2 10:49 T1 A. Efim与奇怪的成绩 题目 众所周知，每当我们看见自己糟糕的成绩时，我们总希望以奇怪的方式将其四舍五入。 Efim同样如此。在晴朗的一天，Efim拿到了他的成绩X，他希望通过最多m次四舍五入使他的成绩最大化（每一次四舍五入舍掉的的位置任意，但只能在小数部分，不能在整数...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15728574.html 题目链接 题目 Peter decided to wish happy birthday to his friend from Australia and send him a card. To make his present more mysterious, he decided to make a chain. Chain here is such a sequence of envelopes A A A = {...