夏季总结

六月的期末考试

好久没有写总结了。期末考试崩崩之后一直没啥心情,所以也就没有写六月份的总结。期末考试简直就是一场噩梦,数学和语文直接把表现全部拉低,最奇怪的还是数学,因为在我看来全部秒切的题目最后全部 GG。所以,期末考试唯一能说得上的就是理综回到正常智商水平,其他全 GG。

期末考试之前在学校还是非常用功的,只是练习的实在太少,以至于考试场场挂飞。在 17 班和同学的关系好了一些,前后桌讨论题目和奇怪话题的声音一直不断。文化课生活也挺好呢。

纪中集训

暑假开始之后我先是花了几天疯狂颓,然后就来纪中七月集训了。打 B 组还是比较顺畅的,一般表现都比较正常,题目一个下午之内就能改完,算是非常舒适了。只不过发现自己的知识和暴力能力确实不太强,或者说是非常的弱。不过 B 组的题还是让我在短时间内搞定了我的基础。

八月份打 A 组简直就是噩梦,先抛开三月份打 A 组的快乐时光不谈,这次的题目难度比三月份强得多,且经常被踩成傻逼。心态崩崩的时候基本上就到了听课的时间,几位神仙都讲的很好啊,也很耐心的感觉(特别是讲 SAM 的 Cold_Chair),所以还是学到了很多省选的东西。感觉如果 NOIp 发挥正常去做省选题应该不会碰上太多科技没学过的问题。

经常比赛打着打着就开始看 Twitter 和空间,分散注意力,导致一堆正解想到一半就弃掉了,有的时候暴力分都拿不稳,非常的惨。感觉自己的做题能力和整体智力在随着时间增长的情况下越来越差,当然也确实没啥特别的。

所以暑假的最后几天,我准备整理一下思绪和思维方式,迎接针对 NOIp 2019 的训练了。

我是很怕,但是我真不知道除了往前走还能干啥。There would be always ways for everyone, isn’t ?

[Libre OJ]6014「网络流 24 题」最长 k 可重区间集题解

主要思路

这道题还是很妙的,我只想到了最大费用最大流之后就想不动了。

我们在这里介绍边数为\(O(n)\)级别的解法。考虑把所有的端点离散化为\(2n\)个连续的点,然后相邻端点\(i, i+1\)相互连接流量无限、费用为零的边。考虑区间左右端点,左端点连到右端点,流量为\(1\),费用为区间长度。最后源点连左端点,汇点连到右端点。

这样就可以强制满流,且费用最大。

继续阅读[Libre OJ]6014「网络流 24 题」最长 k 可重区间集题解

P4556:[Vani有约会]雨天的尾巴题解

主要思路

这道题可以离线回答,很大概率是什么树上差分之类的东西。但是树上差分无法维护区间信息,然后想到用权值线段树来维护。如果暴力开\(1e5\)个线段树来维护会 GG,但是我们可以动态开点,然后每个点对应的线段树大小差不多为\(O(\log n)\)级别的,这样空间就可以接受的了。

既然有了很好用的动态开点线段树,我们就可以用树上差分那一套路,在端点和\(LCA\)处打标记,然后考虑从下往上合并答案。合并可以用线段树合并,复杂度为重合部分,差不多就是\(O(\log n)\)。然后就没了,很傻逼的一道题。

继续阅读P4556:[Vani有约会]雨天的尾巴题解

[Fortuna OJ]4682「GDOI2017模拟8.11」生物学家

主要思路

这道题原题解作者的思路非常的清晰。我来阐述一下。

首先思考答案的意义,一定是总的权值和减去:

  • 变性花费
  • 不要的赞助费
  • 喝茶费用

我们可以用上面这三个元素组一个网络流,计算最小割使答案最大。

考虑将源点连入雌性,雄性连入雄性,流上限就是变性花费:如果将这种边割掉,那么就是不需要进行变性。考虑朋友的边,如果倾向于变雌性,源点连入,向所有的对应编号连边;如果雄性,连入汇点,所有对应编号的向该朋友连边。

继续阅读[Fortuna OJ]4682「GDOI2017模拟8.11」生物学家

[Fortuna OJ]4681「GDOI2017模拟」8.11选择

主要思路

这道题所有购买方案的取值上界为\(a_i \times k\),差不多就是\(1e5\)级别。考虑超级大暴力,设置状态\(f[i][j][w]\)为选了\(i\)个次、最后一次是第\(j\)种硬币且当前总价为\(w\)是否可行。这个转移算上取值上限就差不多是\(O(n^4)\)的,只能过掉一部分分数。

考虑进行状态转化。我们先让所有商品的价格减去价格最小值,然后剩下购买的方案就变成了形如\(k*minVal + sum\)的形式,然后我们设置状态\(f[i][j]\)最后一次选第\(i\)种商品,且选到\(j\)的最少选择次数,统计次数小于\(k\)的状态就可以了。

继续阅读[Fortuna OJ]4681「GDOI2017模拟」8.11选择