0214

今天做了NOIP2022 T4，没做完联合省选2022 D1T3，晚上打了比赛。

NOIP2022 T4 比赛

有一说一，比去年的T4阳间多了。

不难想到离线，然后枚举右端点，对于左端点维护答案。然后线段树需要维护 suma,sumb,sumab,sumans，然后需要区间a,b赋值，维护历史和。

然后最直观的想法是直接上矩阵，由这4个和1构成5*5矩阵，对于赋值和历史和都能轻易地列出矩阵，然后线段树维护矩阵即可。然后TLE了。

矩阵不行，那么就只能开始动脑子——维护tag，然后发现每次sumans+=sumab的tag在与a,b赋值的tag合并时会需要有suma,sumb,len产生贡献。于是可以列出tag:ta,ta(赋值tag),sa,sb,sab,slen(sumans+=suma*sa+sumb*sb+sumab*sab+sumlen*len)。

然后就可以合并tag了。 比矩阵快得多得多得多。

这个题想出O(n^2)就很轻易地想到线段树维护历史和，然后几乎不用脑子就可以推出矩阵做法，但是如果直接莽就会TLE。然后在此基础上再思考怎么打tag，构造tag的重点是要支持合并，然后只要足够细心就可以做出来了。

比chess良心多了。

联合省选2022 D1T3 学术社区

口胡了，但是还没写完。

对于一对消息 (x,y)，如果排在一起，可以对答案有0,1或2的贡献。如果贡献为2，把它们直接配对到一起一定不劣。然后就只剩下有一些对的贡献为1，然后我们可以跑最大流求出最大匹配（在这里要优化建图，只要有信仰网络流就跑得过）。然后我们获得了每个人的左/右是谁的信息。但是我们要构成的是序列，如果出现环就糟糕了。但是发现题目保证每个人至少有一个学术消息，可以使用学术消息替代一边的消息，然后就把环断开了，并且可以吧这一段首尾相同的看作新的学术消息。于是我们可以把环拆开，构造出序列。复杂度全在网络流上。

挺麻烦的，十分的难写。

0214 模拟赛

T1

感觉就是结论题，于是天马行空地猜结论，大胆假设，小心求证。

首先，感觉一定存在一个根节点，使得其每一个子树，子树中的边要么全部向上，要么全部向下。手玩了几组都是对的。那么这个点是哪个点，又如何确定每个子树的方向呢？想一想这个时候有哪些路径是不行的：同方向的子树之间都不行，于是我们想要同方向的子树尽量少，即每个方向的子树大小之和尽量接近n/2，于是就发现这个点应该是重心。

然后证明比较麻烦，但是感性理解确实很对，然后就AC了。

然后复杂度在背包上，1e6的背包很难，但是这是bool背包且物品体积大小一定，不仅可以按体积分类，还可以对cnt很小的类直接bitset，然后跑得嘎嘎快。

T2

考虑找到n到1路径上的那些点，在1~n-1之间要选出k个父亲，然后这条路径就 确定了。对于剩下的点，父亲编号显然越小越好，路径上填的越大越好，于是路径上填的是剩下的中最大的k个。

然后考虑要能使剩下的人都找到父亲，选出这条路径以后，除了路径上的点，每个点的可选父亲数量都会减少，所以对于最开始就只有一个父亲可以选的点，它一定要在路径上。即：如果\(i=\sum_j [a_j<=i]\)，则 \(i+1\) 一定在n到1的路径上。然后每个点最多选一次，所以路径长至多是去重后的点数。选了必选的点之后，为了使得权值尽量大，所以新加的点从小到大加，然后要维护剩下的最大k个数，双指针即可，复杂度O(n)。