费用流练习，分块练习， 概率期望，费用流(Dinic版)，CDQ分治，基环树

题面

思路：

很裸的一道树剖题，我们把边权化为点权就可以了。注意不要加上两点的LCA。当我们两个点跳到同一条链上时，深度更浅的点就是两点的LCA了。我们只需查询区间$[id[x]+1,id[y]]$就可以了。

思路：

我们先考虑暴力，我们可以先按题意模拟先从N点跑一次最短路，然后我们在从每个草垛跑一次最短路，时间复杂度$O(kn)$，得到$70$分的好成绩。我们再考虑优化，我们发现我们从每个草垛跑最短路时跑了许多冗余状态。

思路：

正解做法：考虑容斥。

不能和谐的奶牛的对数等于总对数-和谐的奶牛数。
我们可以统计出与当前的奶牛口味有1个相同的奶牛数，有2个相同的……
根据容斥，奇数加，偶数减。我们就可以在$O(2^5N)$的时间复杂度内完成了。

题面

思路：

依赖关系不存在环，说明这是一颗有向树，0为根节点(不依赖任何的软件包)。安装时是查询x到根路径上权值为0的节点个数，然后再将x到根路径上的节点权值全部变为1就行了。卸载时查询x的子树中有多少个权值为1的节点个数，然后再将x及其子树的所有节点全部变为0就行了。上述操作只需用树链剖分实现，把线段树改为01可区间修改的线段树就可以了。

题面

思路：

树链剖分模板题，1操作直接修改，2把线段树维护信息加上区间最大值

题面

LCT板子

评测

2019.01.27

2.食物

问题描述：

辉夜本来是生活在月宫的月之公主。

辉夜从月都弄了很多吃的回到了幻想乡，有$n$中不同的食物，第$i$中食物的美味度为$t_i$，一份食物的大小为$u_i$，共有$v_i$份。但是麻烦的事情出现了，她有把这些食物运回永和亭，于是辉夜便弄来了$m$种运载工具。第$i$种运载工具可以运输大小总和不超过$x_i$的食物，运输一次的费用是$y_i$，总共可以运输$z_i$次。
辉夜打算选取一些食物运回永和亭，他们的美味度之和（每份食物的和，即使他们都是同一种食物）至少是$p$。值得注意的是，一份食物可以被拆成几份分批次运输，达到永和亭后在组装起来。但是如果不把一份食物完整的运过去，是无法得到美味度的。辉夜想知道最少需要花费的运输费用是多少。由于辉夜的预算仅有$50000$，因此如果费用超过这个数或者无法获得$p$的的美味度，输出”TAT”。
$1\leq n,m \le200,0\leq p \le 50000,1\leq t_i,u_i,v_i,x_i,y_i,z_i\le100$

$\color{red}{NOIP2018}$反省与分析

关于本次$\color{red}{NOIP}$的一点总结

先总结一下自己这次$\color{red}{NOIP}$做的好的一点吧。

这次$\color{red}{NOIP}$是抱着平常心态去考的，虽然其中出现了很多的障碍，但是心态保持的很好，没有出现什么心态爆炸。可以说这是我相对发挥不错的一次了。

$\color{Blue}{NOIP}$退役记

关于本次的$NOIP$心里都是悔恨。。。。。（文件名都打错了）；

• 考前

蒟蒻的我是最后一批停课的（果然还是太菜了），但还是因此逃过了期中考试然后接下来就是各种各样的集训，每天就是上午写题，下午改题，晚上接着考。感觉自己经历了绝望，看着自己不忍入目的分数与大佬的神仙成绩，感觉$NOIP$凉了。