一个基础做法Alice给点标号，Bob可以传一个\(2^{20}\)的信息给Alice，意味着Alice只能知道点的部分信息，然后根据部分信息得把剩余需要的信息传给Bob。考虑树分块，子树大小\(\ge7\)的时候就划为一块，由于是二叉树（一开始以某个\(\le2\)度点为根），那每个子树的大小在\([7,13

JOISC2022Day1T2京都观光在zr的时候花子讲过这个题，当时就觉得非常的震撼！！现在来看还是觉得这个题好牛啊。假设我们现在只有两条路走：第一条是↓→，第二条是→↓。贡献分别为：\(B_1\timesn+A_n\timesm\)以及\(A_1\timesm+B_m\timesn\)。移项后两侧分别为\((A_n-A_1)\t

大家好，我喜欢珂朵莉树，所以我用珂朵莉树\(AC\)了本题。实际上，我们比较容易发现，这题实际上就是求\([l,r]\)中的所有点作为关键点时，虚树所压缩的所有点（实际上就是显现出来的点+在虚边上的点）。那么我们容易发现，一个点\(x\)作为虚树所压缩的所有点的充要条件为：\(x\)是至少

这篇文章主要讲一下问什么要二分以后还要check(l-1)，以及怎么找距离小于等于\(k\)的边的数量。题目给定\(n\)个点，求出任意两个点的曼哈顿距离的集合的前\(k\)大。思路我们先将曼哈顿距离转化为切比雪夫距离：我们知道形如\((x,y)\)点之间的曼哈顿距离等于\((x+y,

虚树大小可以从两个角度进行思考：最小斯坦纳树大小，或者，子树内至少有一个标记点的点的数量减去虚树上边的点的数量。前者的优点是简洁，后者的优点是不依赖dfn序的排序。这道题在利用后者的同时，将赋值看作了颜色段，用树链剖分保证了颜色段总数为\(O(n\logn)\)，利用了odt。#inc

joisc2023护照这题题意好难理解。题目链接P9331[JOISC2023Day1]Passport题意描述有\(n\)个点，每个点连边连向编号在\([L_i,R_i]\)间的点，有\(Q\)组询问，每次从\(x\)号点出发，求出到\(1\)号点和到\(n\)号点的两条路径经过点的并集的最小值。\(n,Q\leq2\cdot

搞了很久，题解区有线段树爆改pushup高妙做法说下cdq分治先将点都按横坐标从小到大排序，cdq分治，那我们现在只需要考虑分治过程中\([l,mid]\)和\([mid+1,r]\)互相形成的合法点对，显然左边的横坐标都小于右边的横坐标。能够发现，如果右边有一个点插在一对本来合法的点之间，那么那对合法

MyBlogsP10432[JOISC2024Day1]滑雪2感觉是挺好的观察性质题，vp的时候场切了。首先酒店一定是建在最低的某一个点。把高度离散化之后，把点扔到对应的位置。可以发现高度为\(i\)的层的所有点，如果能接上一层的连接器那一定会尽量接上（因为到了下一层它本身也可以贡献一个空

令\(S\)为题面的\(S'\)。首先考虑刻画出\(\texttt{()}\)对应的折线。首先如果\(S\)本身合法，那么直接DP算一下就行了。否则考虑不合法的情况，考虑反转\((l,r]\)合法的情况的判定。令\(s_i\)为前\(S_{1\simi}\)的前缀和的值。那么有：\(s_r-s_l=\frac{s_n}

感觉我太滞后了Day1T1Fish3我们可以做的操作是单点加\(D\)和后缀加\(1\)，考虑把这个操作放在差分数组上，则操作变成了：单点加\(1\)。\(i\)处加\(D\)，\(i+1\)处\(-D\)。需要最小化第二种操作的使用次数，发现只有对于所有差分数组中的负数是不得不用第二种操作的，而对于

Day1T1Cultivation发现任何的两个操作之间时没有偏序关系的，也就是我们可以任意调整操作之间的顺序。那么本质不同的操作，可以用\(l,r,u,d\)四个数表示，分别表示向左/右/上/下移动的次数。假设我们已经确定了\(u,d\)，则会出现\(O(n)\)类本质不同的行，而对于每一行，都会给\(l,r

LOJ传送门考虑若已求出钦定\(k\)个升高的排列数量\(f_k\)，那么二项式反演就可以求出恰好\(k\)个升高的排列数量\(g_k\)，即：\[g_k=\sum\limits_{i=k}^n(-1)^{i-k}\binom{i}{k}f_i\]考虑求\(f_i\)。相当于钦定原序列构成了\(n-k\)个上升段。相当于把\(n\)个

JOISC2018loj上有几乎全部的题目，写了题意的就是loj上没有的。D1T1简单题。根据颜色段均摊的结论，每个点到根的路径上颜色段的总和是\(O(n\logn)\)的，于是直接每次暴力找颜色段即可。复杂度\(O(n\log^2n)\)。提交记录D1T2又是计算几何。我们需要画出一条闭合折线，并且

JOISC2017loj上有几乎全部的题目，写了题意的就是loj上没有的。D1T1开场放大。首先，对于一个点，它最后覆盖的一定是一个矩形，这就意味着如果我们知道了\(u,d,l,r\)操作各用了多少次，他们之间的顺序是不重要的，我们可以直接当做把一种操作做完再做剩下的操作，这样就可以做到\(O(

JOISC2016loj上有几乎全部的题目，写了题意的就是loj上没有的。D1T1一开始把题目看错了，还写了棵线段树。把询问离线，倒着扫一遍，就变成了求最长不上升子序列，用树状数组维护即可。提交记录D1T2来自Kubic的神仙做法。考虑Filp一个位置和剩下所有位置，记录每个数作为答案

JOISC2015loj上有几乎全部的题目，写了题意的就是loj上没有的。D1T1简单题。因为\(k\)很小，考虑依次确定最后第\(i\)位是什么。我们倒序考虑所有操作，维护最后第\(i\)位当前在第几位，就可以一直推下去。提交记录D1T2直接暴力复杂度就是\(O(k4^k)\)的，可以通过。提交

JOISC2014loj上有几乎全部的题目，写了题意的就是loj上没有的。D1T1想到了最短路的做法，不过可能还需要整体二分，复杂度至少有2log。有复杂度更优秀的贪心做法。把边按时间倒序加边，然后从终点开始dfs来更新每个点可以的最晚出发时间，每条边走之后肯定就不会再让答案变优了，

Day1T1Examination三维数点板子题，直接cdq分治+树状数组，时间复杂度\(O(n\log^2n)\)。Day1T2Meetings对于一个大小为\(n\)的树，我们可以在\(n-2\)的询问中得到某一条我们选定的链\((x,y)\)上的所有节点的集合\(S_0\)，以及在断掉这条链之后，得到的若干连通块集合\(S_1,

Day1T1Building4首先有一个\(O(n^2)\)的DP：记\(f_{i,j,0/1}\)表示已经填了前\(i\)位，其中有\(j\)位选择了A序列，当前第\(i\)位是选自A序列还是B序列是否可行。通过打表或推理发现，对于\(f_{i,j,0/1}\)中的每一个\((i,0/1)\)，为\(1\)的\(j\)是一个连续段，这

题意给定\(n\)个点，求平面上，曼哈顿距离最近的\(k\)点对。Sol仔细想想就会发现，曼哈顿距离不好做最近\(k\)点对。考虑转成切比雪夫距离。\(x'=x+y,y'=x-y\)。二分答案，每次\(check\)一个\(dis\)，询问距离小于\(dis\)的点对是否有\(k\)个。\(check\)是平凡

Day\(\mathbb{P}_1+\mathbb{P}_2+\mathbb{P}_3+\mathbb{P}_4+\mathbb{P}_5+\mathbb{P}_6\)。放到二维平面上考虑，点\((x,y)\)表示\(x\)时刻在\(y\)位置上，那么第\(i\)顾客的路径可以看成起点为\((t_i,a_i)\)，终点为\((t_i+|b_i-a_i|,b_i)\)的线段\(P_i\)。注意到一个

最终形态一定是\(n\)个点形成的一个大环。故每个点的入度一定为\(1\)，我们考虑保留每个点入度中\(c_i\)最大的边，剩下的删除，此时原图一定变成一堆链加一些环。对于环，我们是需要拆开的，此时我们可以枚举环上每个点，考虑将其反悔，反悔代价为环边代价减去其次大入边（最大入边一定为

[JOISC2021Day2]道路の建設案(RoadConstruction)题意给定图上\(n\)个点，求前\(k\)小曼哈顿距离点对距离。题解很好的一道题。首先有一个\(O(nlog^2n)\)的做法，个人感觉还是很有启发性的。一般对于第\(k\)小的处理方法是二分，二分第\(k\)小的距离是多少。然后统

  朴素的DP形式是定义\(f_{i,j,A/B}\)表示前\(i\)个元素选择了\(j\)个\(A\)的可达性.\(\mathcalO(n^2)\).交换状态与值域,定义\(f_{i,A/B,A/B}\)表示前\(i\)个元素中的最后一个元素(即\(i\))选择了\(A/B\),在最大化\(A/B\)的数量的目标下求得的\(

試験/Examination直接三维偏序。#include<iostream>#include<cstdio>#include<cstring>#include<numeric>#include<algorithm>usingnamespacestd;constintN=100005;intn,Q;intv[N*6],cnt;structQuery{inta,b,c;intv,i