组队排位赛14 GCPC2018

题解 (opens new window)

Gym 102021G *

Gym 102021J *

Gym 102021K 背包Dp

裸的背包Dp：数组$Dp[i][j]=(0/1)$代表使用了$i$根线，总长度为$j$时的状态情况（0：不存在，1：存在）

复杂度$O(1400n^2)$（或$O(gn^2)$）

bool dp[62][1401];
int n, g, len[62];
// ......
dp[0][0] = 1;
for(int i=0; i<n; i++){
    int slen = len[i];
    for(int j=59; j>=0; j--){
        for(int k=1400-slen; k>=0; k--)
            dp[j+1][k+slen] |= dp[j][k];
    }
}

Gym 102021M 勇敢地暴力！

对点的高度进行排序，从低向高遍历，并尝试合并周围4个点：如果目标比自身低，则合并；否则不合并。

对于第$i$个查询$(p1,p2)$，如果发现待合并的两个连通块$b1,b2$中都存在同一个编号$i$，那么$ans[i]$为当前点高度（注意特判$p1=p2$的情况）。

我们可以使用list/set/unorder_set维护各个连通块内的查询编号；用并查集维护连通性，当合并两个连通块时，合并两个list/set/unorder_set（小的并入大的）。

不会TLE！