2018.10.23NOIP模拟赛解题报告

心路历程

预计得分:\(100 + 50 + (10 \sim 50)\)

实际得分:\(100 + 10 + 50\)

这可能是我打的最懵逼的一场考试没有之一。。

T1两个小时才做出来也是醉了。

T2讲过原题但是不会做其实只要改一个字符就能A了

T3只会打套路暴力。。

比赛开场看T1一点思路都没有,不管怎么想都是\(O(n^2)\)的复杂度,做了好久终于发现自己傻逼了这就是个傻逼题。。

开始做T2的时候慌的一批,因为旁边的大佬们都已经把暴力打完了。。T2没多想就写了50分(实际上已经无限接近正解了。)

距离考试还有\(30min\)的时候才开T3,发现暴力单调栈可以拿\(50\)分,但是写起来特别恶心。不过万幸在考试结束前\(2min\)写出来了。但是大数据一拍就wa。。感觉自己药丸。不过最后不知道啥原因该得的分还是拿到了。

出了成绩发现大家考的都不理想。T1、T2都有大佬fst了。

然后我就win了???。。。。

题解

题目数据代码

T1

一道很zz的题目然而被我硬生生的做成了一道不可做题。。

显然\(x\)与\(p\)互质的话一定存在一个\(y\)满足条件,为了不重复统计需要特殊考虑一下\(x = y\)的情况

T2

非常迷的一道题

cf547D. Mike and Fish(欧拉回路)

T3

这个就比较interesting了。。

直接说正解吧

按照cdq分治的思想来做,每次只考虑过\(mid\)的贡献

对于\(mid\)左边的点,维护后缀\(mn, mx\),对于在\(mid\)右边的点,维护前缀\(mn, mx\)

维护\(p_1, p_2\)分别表示在过\(mid\)的点中,比当前\(mn[i]\)小的第一个元素 / 比\(mx[i]\)大的第一个元素

显然\(p_1, p_2\)具有单调性。

这样需要统计的区间就被分成了三段(假设\(p_1 < p_2\))

\((mid - p_1](p_1 - p_2](p_2, r)\)

维护好\(mn, mx, mn \times mx\)的和。所有贡献都是可以算出来的,递归做即可

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Laoqi's Linux运维专列

python3–装饰器

43760
来自专栏章鱼的慢慢技术路

《算法图解》第一章笔记与课后练习

41340
来自专栏祥子的故事

python | 工作笔记 | pandas 常用总结

51290
来自专栏小樱的经验随笔

鸽巢原理(抽屉原理)的详解

抽屉原理 百科名片 ? 桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放两个苹果。这一现象就是我们所说的“抽屉原理”...

62170
来自专栏沈唁志

PHP使用递归算法查找子集获取无限极分类等实操

递归函数是我们常用到的一类函数,最基本的特点是在函数或子过程的内部,直接或者间接地调用自己的算法,但必须在调用自身前有条件判断,否则无限调用下去,也就是所谓的死...

29230
来自专栏章鱼的慢慢技术路

《算法图解》第一章笔记与课后练习_二分查找算法

24040
来自专栏诸葛青云的专栏

C语言控制台界版2048游戏-既然是这样的!

《2048》是最近比较流行的一款数字游戏。原版2048首先在github上发布,原作者是Gabriele Cirulli。它是基于《1024》和《小3传奇》(T...

12700
来自专栏简书专栏

基于Numpy的统计分析实战

标题中的英文首字母大写比较规范,但在python实际使用中均为小写。 2018年7月27日笔记 学习内容: 1.从文件中读取数据 2.将数据写入文件 ...

40720
来自专栏小詹同学

Leetcode打卡 | No.011 盛最多水的容器

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

19320
来自专栏Vamei实验室

纸上谈兵: 图 (graph)

图(graph)是一种比较松散的数据结构。它有一些节点(vertice),在某些节点之间,由边(edge)相连。节点的概念在树中也出现过,我们通常在节点中储存数...

236100

扫码关注云+社区

领取腾讯云代金券