2020-2021:teams:acm_life_from_zero:8.15-8.22

差别

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

到此差别页面的链接

--- 2020-2021:teams:acm_life_from_zero:8.15-8.22 [2020/08/21 13:23]
lak [比赛]
+++ 2020-2021:teams:acm_life_from_zero:8.15-8.22 [2020/08/21 17:16] (当前版本)
kipple [袁熙]
@@ 行 7: / 行 7: @@
 ===== 比赛 =====
 [[https://atcoder.jp/contests/abc175|ABC175]] ''pros:5/6/6''
 TCO20 Round3B pros''0/1/3''
@@ 行 29: / 行 30: @@
 ====== 本周推荐 ======
 ===== 李元恺 =====
+[[https://atcoder.jp/contests/abc175/tasks/abc175|ABC175F]]
+tag:回文串、dp
+题意：$N$($N \leq 50$)个字符串($|S_i| \leq 20$)，每个字符串有一个代价$c_i$，问每个串可以不限次数使用的情况下用这$N$个字符串拼接出一个回文串的最小代价。
+解法：枚举最终回文串的对称轴。对于每个串，枚举每个可能的位置作为对称轴，则一定会剩一段前缀或者后缀没有匹配，并且一定存在另一个串接在另一端来匹配这个子串。计$dp_{i,j,1}$为待匹配为第i个串的第j个前缀的最小代价，$dp_{i,j,2}$为第i个串的第j个后缀的最小代价，转移时参考dijkstra的思想，初始化后每次取出优先队列队首的状态，计算出所有可达状态并推入优先队列，不断重复直到优先队列取出空串。时间复杂度$O(N^2*|S|*log(N*|S|))$
+comment:这周写出来的最难的题
 ===== 姜维翰 =====
+codeforces 1214E
+类型：构造，贪心，图论
+题意：有2n个点，构造一棵树，满足编号2i和2i-1的点的距离恰好为di，保证1<=di<=n
+题解：首先对所有奇数点按di从大到小，从头到尾连成一条链，记下这条链
+然后对奇数点从头到尾在链上添加对应的偶数点，如果某个偶数点正好加到链尾，则扩展这条链，这样的构造是一定存在的。
+评论：奇妙的构造题
 ===== 袁熙 =====
+codeforces 1388E\\
+题意：$n（n\leq2000）$条不相交的线段，将他们按照同一方向投影到x轴上，要求投影不相交，求所有投影间最远两点的距离的最小值\\
+tag：计算几何，扫描线\\
+题解：对任两条高度不同的线段，存在两个向量可以使他们投影的端点为同一点，最优解一定在所有这样的向量中。对每个向量，各点$(x,y)$投影的位置可以表示为$(x+y*arctan(\theta),0),\theta$代表向量与y轴夹角。这样就可以用凸包的形式$O(n^2log(n^2))$得到答案\\
+comment：这周补的比较有趣的题\\

2020-2021/teams/acm_life_from_zero/8.15-8.22.1597987425.txt.gz · 最后更改: 2020/08/21 13:23 由 lak