D – Numbers of Permutations
思考量很小的一道题。
先用间接法来算。初始答案为\(n!\)，然后考虑容斥掉那些符合排序规则的方案。发现，我们可以分开来考虑，按照容斥的顺序：先考虑只算第一维、第二维的，在加回来两维都考虑的。
第一维和第二维的做法非常显然：排序之后用多重集的排列就行了，考虑每一个相同的区间里面内部乘起来。如果有\(k\)个连续的数段，那么部分的答案就是\(\prod_{i = 1}^l len_k!\)。
POJ1639:Picnic Planning 题解
大体思路
做过 LCT 么？（做过基本上就可以切这一道题）
考虑把跟节点先去掉，然后会产生很多个联通块：每一个连通块求出最小生成树，然后找到整个连通块与根节点连接的最小边，连上。
之后如果还剩下一定的可以使用的度数，我们可以考虑用根节点剩余的边去更新整个最小生成树。具体而言，我们找到了一个\((1, v)\)未使用的边，然后我们找\(1 \to v\)上所有的边，找到一个差值最大的。如果这个差值是正数，那么加入这条边，删去之前的边，就会发现答案减掉了这个正差值。不停重复就可以得到答案。
「2018泉州国庆集训#1」 – 解题报告
Educational Codeforces Round 72 Div. 2 解题报告 (CF1217)
C – The Number Of Good Substrings
这道题比较傻逼。
考虑记录上一个最近的\(1\)的位置\(nxt_i\)，然后显然的是：如果在\( O(n \log n) \)时间的扫描中扫描到\([l, r]\)大于当前区间，那么就考虑\(l\)左边是否有足够的零来补足长度。然后这道题就可以愉快的 AC 了。
夏季总结
六月的期末考试
好久没有写总结了。期末考试崩崩之后一直没啥心情，所以也就没有写六月份的总结。期末考试简直就是一场噩梦，数学和语文直接把表现全部拉低，最奇怪的还是数学，因为在我看来全部秒切的题目最后全部 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\)，费用为区间长度。最后源点连左端点，汇点连到右端点。
这样就可以强制满流，且费用最大。