比赛链接

solved by 2sozx

• 题意：给定 $3\times N(N\le25)$ 个数，将其分为三个长度为 $N$ 的序列 $A,B,C$ ,使得 $\sum_{i=1}^{N}(A_i-B_i)\times C_i$ 最大。
• 题解：首先我们有两个很显然的结论：$B$ 一定是由最小的 $N$ 个数构成，$A_i\ge C_i$。下面有几个不太显然的结论。
  • 由 $(A_i-B_i)\times C_i +(A_j-B_j) \times C_j \ge (A_j-B_i)\times C_i + (A_i-B_j)\times C_j$ 可得 $(A_i-A_j)\times (C_i-C_j) \ge 0$
  • 由 $(A_i-B_i)\times C_i +(A_j-B_j) \times C_j \ge (A_i-B_i)\times C_j + (A_j-B_j)\times C_i$ 可得 $(A_i-B_i-A_j+B_j)\times (C_i-C_j) \ge 0$
  • 由 $(A_i-B_i)\times C_i +(A_j-B_j) \times C_j \ge (A_i-B_i)\times A_j + (C_j-B_j)\times C_i$ 可得 $(A_i-B_i-C_j)\times (C_i-C_j) \ge 0$
  • 将 $B_i$ 从小到大排序我们可以知道 $A_i$ 取得尽可能大答案会更优。假设此时位置 $i$ 上 $A_i$ 并没有取得最大值 $X$，设位置 $j(j>i)$ 上 $A_j=X$，此时两个位置的贡献为 $(A_i-B_i)\times C_i+(A_j-B_j)\times C_j=A_i\times C_i+A_j\times C_j - B_i\times C_i - B_j\times C_j$ 由于第一个推论我们知道 $C_i \le C_j$ 所以如果此时我们将 $A_i,A_j,C_i,C_j$ 交换得到的贡献为 $A_i\times C_i+A_j\times C_j - B_i\times C_j - B_j\times C_i$ 由于$C_i \le C_j ,B_i \le B_j$ 我们可以得到交换后的贡献不会更差，因此结论成立。
  • 由于上一个结论，我们可以发现每次向后移动一个位置，对于答案的贡献会减少，因此我们可以根据已经更新出的 $Ans$ 来进行剪枝。
  • 暴力枚举 $A,C$ 通过上面几个结论进行剪枝即可。

solved by 2sozx

• 题意：巨水
• 题解：巨水

solved by Bazoka13

• 题意：求欧拉回路，记录路径
• 题解：dfs，记得存路径的顺序

solved by 2sozx

• 题意：给定一个序列 $a$ ，对于 $1\le i<j<k\le N(N\le10^6)$
  若有 $\forall x\in [i,j-1] a[i]<a[i+1]$ 并且 $\forall x\in [j,k-1] a[i]>a[i+1]$ 则 $i\sim k$ 构成了一个 $hill$ ，高度为$\min(j-i,k-j)$ ；
  若有 $\forall x\in [i,j-1] a[i]>a[i+1]$ 并且 $\forall x\in [j,k-1] a[i]<a[i+1]$ 则 $i\sim k$ 构成了一个 $dale$ ，深度为$\min(j-i,k-j)$ 。
  求高度和深度的最大值。
• 题解：从左到右扫一遍即可，注意 $a_i==a_{i+1}$ 时要重新记录

solved by JJLeo

• 题意：求$1$到$n$波动排列的个数。$(n \le 10000)$
• 题解：$f_{i, j}=f_{i-1,j-1}+f_{i-1,i-j+1}$

solved by

• 题意：
• 题解：

solved by

• 题意：
• 题解：

solved by

• 题意：
• 题解：

solved by

• 题意：
• 题解：

solved by

• 题意：
• 题解：

solved by Bazoka13

• 题意：$n$个礼物，$m$个人，每人每次选一个盒子，如果有礼物就拿走，无论有没有礼物盒子都放回，求送出礼物的期望。
• 题解：设$dp[i]$为第$i$个人拿到礼物的概率，然后递推就行了，有$dp[i]=dp[i-1]*(1-dp[i-1])+dp[i-1]*(dp[i-1]-1/n)$，前半部分代表上一个人没有拿到礼物，此时拿到的概率不变，后半部分代表上一个拿到了🎁，概率就会减少$1/n$。

solved by Bazoka13

• 题意：给定$n$条线段，求有一个端点重合并且垂直的线段对的个数
• 题解：枚举$+$点积

-1min：MJX打开语音，电脑暴毙，耳机无声音，重启设备调试好后已经快10min。
8min：ZYF写E，挂了
11min：ZYF发现没写文件，过E，MJX写B
14min：MJX WA
17min：MJX发现文件名写错了，过B，CSK写L
23min：CSK过L，MJX写D
40min：MJX WA,ZYF写F
43min：ZYF 过F，CSK写K
46min：CSK 过K，MJX重写D
51min：MJX 过D，ZYF写H，开始了长时间的WA作战
84min：CSK WA C
98min：MJX RE G
99min：CSK 过C，MJX发现数组开小了过G
112min：ZYF发现二分反了过H
112min~208min：MJX，ZYF讨论A，慢慢剪枝TLE，CSK看I
208min：MJX过A
till end：CSK每次多剪一枝多过一个点，最后倒在了test 7，ZYF，MJX自闭于J

• MJX开局要放松，细节要注意好，不要出现文件名写错的低级错误
• CSK也在文件名上白给了两发，$dfs$的选择要慎重，不要T了再去想剪枝。
• ZYF要注意标准输入输出还是文件输入输出，二分的时候要想清楚如果有多个值满足条件是要最大值还是最小值，另外对拍要大量数据，不要随便输几个就当对拍过了。