校网赛复盘

发表于 2023-04-27 更新于 2023-05-03 分类于 acm 阅读次数：

我是个菜菜。

T1 有坑信我

注意到 $a \times b \times c$ 是 10 的倍数，所以可知 $a,b,c$ 其中至少有一个 2 的倍数和一个 5 的倍数。
将其中 2 的倍数和 5 的倍数分别除以他们的因数，可以根据题目知道剩下的数乘积小于 $2^{64}$，故答案可以用 unsigned long long 存储。
该题亦可用 Java 解决。

紫不要也罢……

也是紫不要也罢……

对于有 $n$ 个属性值的雷达图，相邻两个点的属性值 $a_i,a_j$，可以证明其相邻的三角形面积为 $a_i \times b_i \frac{sin\frac{2\pi}{n}}{2}$ 。问题转化为重新排序使相邻的属性点乘积最大。
很容易想到将属性值排序后挑出第 1 大的数，并将第 2 大的数和第 3 大的数放在其左右两侧，这样依次按照 $2k,2k+1$ 的顺序放置在数列的左右侧，直到第 n 大的数被放置。之后求出相邻的数的总和，其值为 $S_n=\sum_{i=3}^{n}a_ia_{i-2}+a_1a_2+a_{n-1}a_{n}$。注意 $a_1a_2$项不要漏掉。
可以证明交换任两个数都会使值的总和减少。这里不证了。
复杂度 $O(nlogn)$。

还是紫不要也罢……

对于任意一个杠杆的分布情况，其都可以表示成所有力矩相等情况对应的情况数的总和。
对于一个杠杆左右力矩相等且都为 $k$ 的情况，我们可以用杠杆左侧的力矩为 $k$ 的情况数，杠杆右侧的力矩为 $k$ 的情况数，杠杆支点情况数的乘积表示。其中杠杆支点只有放和不放 2 种情况。
对于两侧的支点，我们用 $dp[i][j]$ 来代表其在两侧有 $i$ 个摆放点的情况下力矩总和为 $j$ 的情况总数，根据题目可得 $dp[0][0]=1$ 。
在已经有 $i-1$ 个点所有力矩和的情况下，我们很容易根据第 $n$ 个点是否放置的情况分为两种：
- 如果选择不放置，假设 $i-1$ 个点力矩和为 $j$ 的情况数为 $k$，那么此时 $i$ 个点的力矩和为 $j$ 的情况数也会加上 $k$。即 $dp[i][j]= dp[i][j] + dp[i-1][j]$ 。
- 如果选择放置，假设 $i-1$ 个点力矩和为 $j$ 的情况数为 $k$，由于选择导致力矩变化，第 $i$ 个点的力矩为 $i$ ，此时 $i$ 个点的力矩和为 $i+j$ 的情况数也会加上 $k$。即 $dp[i][i+j]= dp[i][i+j] + dp[i-1][j]$ 。
依次遍历各种可能的相等情况并统计总和，对于 $n$ 个点，其力矩总和的范围为 $[0,n(n+1)/2]$。
注意数据范围和模数。
复杂度 $O(n^3)$。

凌晨才写出来，不好评价……

对于一场合法的棋盘，其只有两个可能，黑子走棋（获胜）或白子走棋（获胜）。
- 如果黑子走棋，此时黑子的个数等于白子的个数+1，此时仅可能黑棋获胜。
- 如果白子走棋，此时黑子的个数等于白子的个数，此时仅可能白子获胜。
- 如果子数不满足上述判定，为不合法棋盘。
对于一场获胜的结算，若其为合法棋盘，则应该满足在走棋一方走棋前，场上没有任何五子连线（这里假设五子以上的连线内可以有多条五子连线）。也就是说，如果场上经过连线数最多的子，等于场上的五子连线数，那么这一场棋局就是合法的。
检测横，竖，斜的五子，分别统计各自经过的连线数和总共的五子连线数。
复杂度 $O(n^2)$。

佬写的是dp，瞬间觉得自己是个小丑……

题意可转化为:给定一张由集合A到集合B的二分图G，其中每个匹配给定一个权值v。求出在完美匹配的情况下，该图中最大权值的最小值。
因为是最值的最值问题，所以考虑二分答案。我们以该权值为标准来分割区间，设为X。这里说的标准可以理解为我们假定的正确答案。显然，在×左边(即小于X)的部分是合法的。所以我们用×对二分图进行二次处理，将权值大于×的匹配舍去。对处理后的图用匈牙利算法求最大匹配，看其是否满足完美匹配即可。
复杂度 $O(n^3)$。

附:二分图上的边一般叫做匹配。

复杂度$O(n^4)$也能过。

但是自己没做出来，不说了去学了……