本周无团队训练

ABC175 pros:5/6/6

TCO20 Round3B pros0/1/3

没有专题

没有比赛

没有专题

没有比赛

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：这周补的比较有趣的题