2021-2022:teams:aaub:2021.7.19_牛客2

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2021-2022:teams:aaub:2021.7.19_牛客2 [2021/08/02 21:16]
hugegun
+++ 2021-2022:teams:aaub:2021.7.19_牛客2 [2021/08/02 22:09] (当前版本)
hugegun [G: League of Legends]
@@ 行 4: / 行 4: @@
 因为长度为$1$的边不管横向还是纵向滑行都不会影响是否成环，所以能连接的边数必为$n*m-1$，奇数先手赢。
+> 赛场上数错边数卡了一会
 ----
-==== D: Draw Grids ====
+==== D: Er Ba Game ====
-$n*m$个网格点，两人交替操作，每次连接一条长度为$1$的边，且连接后不能形成环，不能连就输，问先手的胜负。
+模拟
+----
-因为长度为$1$的边不管横向还是纵向滑行都不会影响是否成环，所以能连接的边数必为$n*m-1$，奇数先手赢。
+==== I: Er Ba Game ====
+模拟
 ----
+==== K: Stack ====
+数组$a$生成单调栈$b$，已知$b$的其中$k$个位置上的值，构造出$a$。
+从左往右构造$a$数组，将相邻两个要求$b_{p_i}, b_{p_{i+1}}$抽象为：使用$x=p_{i+1}-p_{i}$个数让单调栈的长度增加$y=b_{p_{i+1}}-b_{p_i}$。
+分情况解决：
+  - x<y，无解
+  - x>y，填入y个数后，x变为x-y，y变为0，转为第三种情况
+  - y<=0，将当前单调栈前y+1个数增加x，此时后面x个数比这y+1个数小，因此将x个数从大到小放置，会剩下一个数，总长度增加(y-1)+1
+区间加采用打标记，记录单调栈中每个数在原序列$a$中的位置即可，每次更新。
+----
+==== F: Girlfriend ====
+两球体积交，积分一下
+----
+==== G: League of Legends ====
+将$n$个区间分为$k$组，每组的交不能为空，最大化$k$组区间交的和。
+如果区间$i$包含$j$，那么要么$i$自己一组，要么对答案没有影响，将所有包含其他区间的区间分开考虑。
+剩下的区间可以用dp做，$dp_{i,j}$表示前$i$个区间分为$j$组的最大值，决策单调。
+最后循环枚举$i$个大区间自己分组，加上其他区间分为$k-i$组的最大值，选择和最大的$i$。
+> 赛场上没想到单独处理大区间，发现没有单调性，就不会了
+==== L: WeChat Walk====
+按更新的权值从大到小枚举，每个点记录上次更新的时间和上上次更新的时间，考虑在时间$i$上被更新的点。
+按度数大小分类，对于度数小于$sqrt(m)$的点，直接从周围的点获取答案，对于度数大于$sqrt(m)$的点，在更新其他点的时候更新(每个点记录它连了哪些大点)
+> 赛场上某人读错题否认了队友的正解

2021-2022/teams/aaub/2021.7.19_牛客2.1627910181.txt.gz · 最后更改: 2021/08/02 21:16 由 hugegun