4.5省选模拟solution
\(4.5\)省选测试\(solution\)
题面可是我精心准备(咕咕咕)了一周写出来的,大家就当看故事吧(那里面的人物确实是存在的,\(E\)就是本人啦,也算是对一段经历的回忆吧,所以这套考试的题目叫——忆)
暴力分给了\([20,40]+30+[30,60]=[80,130]\)
\(std\)的代码量\(1kb+1kb+2kb\)
因为出题人自己也不喜欢很长的代码,所以就找了几个较短的题
知识点考察
\(T1:wqs\)二分\(+\)斜率优化\((P5308)\)
\(T2:\)小清新结论题\((CF351E)\)
\(T3:\)图论,最小路径覆盖\((P5769)\)
总的来说,知识点考察比较全面,还是不错的
预计得分情况人均\(100+100+[30,60]=[230,260]\)
思维难度系数\(Lv4\)
代码难度系数\(Lv2\)
综合难度系数\(Lv3\)
\(T1\)
比较显然的,既然出现了恰好\(k\)次的限制,比较容易想到\(wqs\)二分,每次需要\(O(n)\)转移
考虑优化\(O(n^2)\)
正推式子\(:\)
\(f[i]=f[j]+\frac{i-j+1}{n-j}\)
发现并不是很好搞
那么考虑一下倒推
\(f[i]\)表示从后往前进行选人还剩\(i\)个人的最大贡献
\(f[i]=\max(f[j]+\frac{i-j}{i})\)
\(f[i]=\max(f[j]+1-\frac{j}{i})\)
直接以\(i^{-1}\)为斜率就好了
凸性证明的话,如果\(k\)越大,价值越多,我们每决策一次就减去一部分贡献就好了
\(T2\)
首先全部取正
\(a_1...a_n\)
那么我们考虑代价
对所有的\(i<j\)
要产生逆序对
\(Sit_1:a_i<a_j\)
\(sol_1:j取反\)
\(sol_2:i,j取反\)
\(Sit_2:a_i>a_j\)
\(sol_1:\)都不取反
\(sol_2:j\)取反
那么对于每一个\(i\)进行两个决策
我们考虑我们决策的话为了保证逆序对不重复
那么我们只需要对于目前最大的数字求一下贡献就好了,或者说,每个数都会比自己小的数进行逆序对统计
那么我们的贡献就是取正,右边小的,取负,左边小的,直接求就好了
\(T3\)
原本是要出\(NOI2016\)循环之美的
至于换题的原因嘛,\(MD\)代码怎么才\(1kb,\)教练不得吐槽我\(?\)
那我换成\(2kb\)的目前的\(T3\)了。。。\(kx\)
对于航线之间的关系建图,然后就成了最小路径覆盖问题
直接建一建图,写一个网络流板子就好了
建图的话\(:\)
考虑怎么才能从航线\(i->j\)
\(d_i+t(x_i,y_i)+p_{y_i}+f(y_i,x_j)\leq d_j\)
后记
并没有打算出很难的题,找了几道有意思的题就出了
其实做了这么多题,感觉一道题最快乐的地方是能体会到这道题的乐趣,这个算法的精妙
或许目前成绩是唯一衡量标准,但是,对一个事物的喜欢不仅仅是无论怎样都要取得好成绩,能每天在自己热爱的事业上努力着,也是一件快乐的事,\(OI\)嘛,是乐趣,如果沾染太多功利和虚伪,那就不快乐了,不是吗\(?\)
考试最开心的事也是思考的过程啊,即使最后可能没有想通,但是那份过程也是难得的快乐\(\sim\)
每个人的人生都是联通图,没有到达终点之前,我们就没资格说失败\(!\)
\(2022.4.5--Eternal\underline{}Battle\)
最新文章
- 体验报告:微信小程序在安卓机和苹果机上的区别
- ROWNUMBER() OVER( PARTITION BY COL1 ORDER BY COL2)用法,先分组,然后在组内排名,分组计算,主表与附表一对多取唯一等
- Volley框架设置sessionid
- Contractive Auto-Encoder
- converntion
- 本博客迁移到Github,之后停止更新
- poj2388解题报告(排序)
- SQL、LINQ、Lambda 三种用法
- 修改cas登陆页面-服务器端
- 第十篇:web之前端之django一些feature
- asp.net网站性能优化2则
- 使用adb签名并安装Android程序
- Winform常用开发模式第一篇
- Flex中的FusionCharts 四图监听
- node.js与比特币(typescript实现)
- python的安装,IDLE基本操作
- 初涉IPC,了解AIDL的工作原理及使用方法
- koa 写简单服务
- 欧拉函数-gcd-快速幂(牛客寒假算法基础集训营1-D-小a与黄金街道)
- 【BZOJ3613】[HEOI2014]南园满地堆轻絮(贪心)