好了,直接进入真题。

Day1

$T1:$

直接$a*b-a-b$

$T2:$

第二题就是个大模拟$233$

$T3:$

先正序处理$d_x$,即$1$到$x$的最短距离。

观察$k,n$的大小,可以尝试$n*k$的记忆化搜索。

建反图之后,有$(u,v,w),f_{u,k}=\sum f_{v,k-w+d_u-d_v}$

之后答案显然,如果有无限的方案的话,也就是出现了$0$环。

如何在记忆化搜索的过程中判出$0$环,也就是之前在栈中的状态(还未统计完整的状态)被访问到了。

Day2

$T1:$

能到达的建条边就好了。

$T2:$

状压显然$233$.

题意就是找一颗生成树,使代价最小。

考虑状压DP,在任意时刻,我们只关心集合里已经有那些点,且最大树高为多少

设要求的当前状态为$S$,那么这个状态要从$S$的子集中来,枚举子集$S_0$,判断出边所包含的点集$G_0$是否

包含$S$,因为这样才能拓展到$S$,在这个条件成立的前提,判断新增的点有哪些,记为$ss$集合,之后

$ss$集合的点取一条最短的边,与$s_0$的最深点连接起来,统计代价,至于为什么只是与最深的点连接,

待会会解释。

对于一个集合$ss=S ~\operatorname{xor}~ S_0$和$S_0$,如果他们之间的边不是被$S_0$中最大深度的点连接成的,那么一定

存在另一个$S_1$($S_1$也是$S$的子集),包含另一种连边的情况,使得$S_1$包含除被最大深度点连接的点以外

的所有点,也就是$ss$部分点转移到了$S_1$中,仅有只与最大深度点连边的点集,才不能转移到$S_1$,那么

通过$S_1$转移的答案就是最小值,一定是正确的。所以不会漏解。

$O(n^2*4^n)$的,可以改变枚举子集的顺序从而变成$O(n^2*3^n)$

这里放个代码,好好理解。

T3:

现在只会平衡树的做法,分析题意可以得知,对于每一次操作$(x,y)$,改变的只有第$x$行$y$位置之后,最后一列的编号,因此可以尝试维护一段连续的区间(因为其是连续的数),具体操作如下:

  • 每一次操作,取出最后一列的第$x$个数,推入第$x$行。
  • 取出第$x$行$y$个数,输出,并将其推入最后一列的末尾。
  • 在进行查询排名操作时,由于可能是一段连续区间,可以考虑将其拆成三个部分(前半部分+你要的那个数+后半部分)