2009-2010 ACM-ICPC, NEERC, Western Subregional Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 3/369 | 10 | 12 | 12 |
A¶
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\) 通过上面几个结论进行剪枝即可。
B¶
solved by 2sozx
题意¶
巨水
题解¶
巨水
C¶
solved by Bazoka13
题意¶
求欧拉回路，记录路径
题解¶
dfs，记得存路径的顺序
D¶
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}\) 时要重新记录
E¶
solved by JJLeo
题意¶
求\(1\)到\(n\)波动排列的个数。\((n \le 10000)\)
题解¶
\(f_{i, j}=f_{i-1,j-1}+f_{i-1,i-j+1}\)，这是第一个元素为波峰的情况，最后答案为\(2 \sum_{i=2}^nf_{n,i}\)。
F¶
solved by JJLeo
题意¶
构造一个\(n \times m\)的黑白方格，其中有\(x\)个白色连通块，要求边界不能有白色方块。
题解¶
模拟即可。
G¶
solved by 2sozx
题意¶
求有多少对 \(A,B(A<B)\) 使得 \(\exists X,Y\ge1, AX+BY =N (N\le 10^5)\)
题解¶
先预处理出 \(1\sim N\) 的约数，之后枚举 \(A\) 与 \(X\) 可以得到 \(BY=N-AX\) ，统计 \(BY\) 的约数即可。注意对同一个 \(A\) 要去重。
H¶
solved by JJLeo
题意¶
求第\(n\)个不含子串\(13\)的正整数。\((n \le 10^{18})\)
题解¶
二分答案，使用数位dp验证即可。注意如果\(x,x+1\)都满足，取\(x\)为答案，二分代码写的时候要略微调整。
I¶
upsolved by Bazoka13
题意¶
\(n\)栋楼，给出相应坐标和高度，在房顶安灯，使得所有楼的两侧完全被照亮，求需要灯的最小值。
题解¶
两个显然：只在楼顶的端点放是最优的、最左侧和最右侧的顶点一定有灯。
不妨先考虑只照亮左侧的做法，可以维护一个从当前遍历的楼中的最高者开始的凸包，在每个凸包的顶点都安装，从而保证如果遍历到第\(i\)栋楼，前\(i+1\)栋楼的左侧都能被照亮。但是这只考虑了右顶点安装，但是如果相邻的两者左低右高，显然在右楼的左顶点安灯更优，因为照明效果不变的同时可能会照到更多的楼，这个比较可以放在处理左侧的过程中。
处理右侧的时候只需要找右顶点没有安灯的楼，用相同方法维护凸包即可。
J¶
upsolved by 2sozx
题意¶
给定一个类似于 \(Word\) 文档的东西，文档的宽度 \(w\le 10^3\)，其中包含了 \(n(n\le 10^4)\) 个单词，单词与单词之间至少有一个空格。现在要向文档中插入大小为 \(r\times c (r,c\le 10^3)\) 插图，按照 \(Word\) 文档中环绕式的方法重新排列单词的位置，问最终此文档所占最少多少行。
题解¶
枚举插图插入的列，处理出来每一个单词作为含有插图的一行最开始的单词下面一行开始的单词是哪个。之后枚举插图最上面一行最开始的单词，可以通过倍增求出 \(r\) 行后第一个单词，之后可以通过预处理求出 \(1\sim i\) 与 \(i\sim n\) 最少需要几行，答案去最小值即可。复杂度 \(O(wn(\log(r)+\log(n)))\)。相信测评机
K¶
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\)。
L¶
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要注意标准输入输出还是文件输入输出，二分的时候要想清楚如果有多个值满足条件是要最大值还是最小值，另外对拍要大量数据，不要随便输几个就当对拍过了。