zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600134.html 我太弱了，改不出T4，就把T1-3题解码了。 T1 报数 题目链接 想着T2，T3的题解都写了，就补一下T1的吧。 典型的筛法。 假如一个数含有7，则把它的倍数全筛走。 这里可以加一个小优化，假如这个数已经被筛过，就不需要再筛它的倍数了。 最后再倒着预处理每个数的下一个没被筛的是什么。 如果不预处理，不断6999999就可以卡死你。 Code 123456789101112131415161718192021222324...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600119.html 题目链接 想着T2，T3的题解都写了，就补一下T1的吧。 典型的筛法。 假如一个数含有7，则把它的倍数全筛走。 这里可以加一个小优化，假如这个数已经被筛过，就不需要再筛它的倍数了。 最后再倒着预处理每个数的下一个没被筛的是什么。 如果不预处理，不断6999999就可以卡死你。 Code 12345678910111213141516171819202122232425262728293031323334353637383...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15598937.html 题目链接 Part A 式子化简 首先题目要求的式子就是 n2n^2n2 乘上 1n∑i=1n(ai−aˉ)2\frac{1}{n}\sum_{i=1}^n(a_i-\bar a)^2n1​∑i=1n​(ai​−aˉ)2，其中 aˉ=1n∑i=1nai\bar a=\frac{1}{n}\sum_{i=1}^n a_iaˉ=n1​∑i=1n​ai​。 我们把这三合在一起也就是： n2×1n∑i=1n(ai−1n∑j=1n...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15590387.html 题目链接 首先dp得从低位向高位枚举，因为高位无论如果使用 2ai2^{a_i}2ai​ 都对低位二进制1的个数无影响，满足dp的无后效性。 设 dp(k,i,x,y)dp(k, i, x, y)dp(k,i,x,y) 为 SSS 从低的高二进制的前 kkk 位中，用了数列 aaa 的前 iii 项，且此时 SSS 中共有 xxx 个二进制位为1，第 i+1i+1i+1 位进了 yyy 过去。 则： dp(k,i,x,y...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15585466.html 题目链接 首先第一问很好求，就是求最长下降子序列，n⩽5000n\leqslant 5000n⩽5000，O(n2)O(n^2)O(n2) 暴力转移就行。 而这道题的难点就在于去重。 对于 iii 和 jjj（i>ji>ji>j），如果 ai=aja_i=a_jai​=aj​ 且 dpi=dpjdp_i=dp_jdpi​=dpj​，说明他们是相同的，iii 的方案要清0，但是这里不能break！ 因为对...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15584623.html 题目链接 首先考虑两个物品A，B。 假设先做A，则时间为：Ax+max⁡(Ay,Bx)+ByA_x+\max(A_y, B_x)+B_yAx​+max(Ay​,Bx​)+By​。 假设先做B，则时间为：Bx+max⁡(By,Ax)+AyB_x+\max(B_y, A_x)+A_yBx​+max(By​,Ax​)+Ay​。 对于A、B，我们可以在上面两种情况中取时间较少的方案。 同理，对于每一对物品，我们都可以采用以上方案...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15582269.html 早上6点摸黑起床… 坐地铁去高中部，蹭校车。 今年是我第一次参加noip，希望开门红（WA） 在地铁上在洛谷打卡，中吉，竟然没有大吉！？ 打卡QQ，在每个群里发一遍rp++ 上车了，找cmb要了2块巧克力。 到达gf，crx老师派巧克力，由于我的厚颜无耻绝顶聪明，骗走了3块巧克力。 在门口和同学拍了张照，然后就进去了… 到达考场，发现我和csp上下午的考场都一样。 带了报纸巾，一大堆食物，一瓶水，文件袋进去。 那个老师一...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15579094.html 题目链接 首先我们发现单词个数，也就是 mmm 很小，这启示着我们不需要用到什么神仙字符串算法，可以暴力kmp。 对于每个单词与原串做kmp匹配，用前缀和记录能匹配成功的，每次询问 O(m)O(m)O(m) 回答即可。 时间复杂度：O(m×(n+q))O(m\times(n+q))O(m×(n+q)) Code 1234567891011121314151617181920212223242526272829303132...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574898.html 题目链接 可以发现，我们并不需要对所有节点进行枚举，我们只需要对所有端点甚至只需要枚举右端点即可。 因为如果这个不是端点，那么在它右边的点和它所在的区间个数相同，同时右边的点必然大于这个点，所以不用考虑这个点。 按照线段覆盖问题求出每个点的覆盖情况即可，也可以说是一维扫描线（雾 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，主要是排序耗时间。 Code 12345678910111213141516...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574730.html 题目链接 观察数据范围发现边权都小于255，所以我们可以枚举最大边权。 对于每个最大边权，我们都在不大于这个边权的剩下的边里跑一次最短路。 最后再用最短路求出的答案+所枚举的最大边权=在这个最大边权下的答案。 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555...