760A - Petr and a calendar 24285727
水题,基本等价于一个月多少天. 忘记了 七月大,八月大,错了一发.
760B - Frodo and pillows 24285741
比寻常B题稍难,推公式二分. 规避了溢出问题,但是依然错了两发.
错误&更正:
公式推错,没考虑到 at least one pillow 条件对公式的影响. => 公式分段
没考虑到只有一个人的情况,上界开小了. => 二分区间[1,m+1)
760C - Pavel and barbecue 24285747
需要稍微分析的图论问题.
分析过程:
按照抽代的思想,排列可以看做一个有向环,在不考虑正反的情况下,问题等价于多个环连成一个环.
考虑正反的时候,不难想到. 有效方案 <=> 存在一个节点v, 能通过若干次转移到达 v'(其反面).
即 v ->* v' .
同时 v ->* v' <=> 一圈翻转次数为奇数
水得出奇的D题.
D题只是题意难理解(其实是题意没有完全体现在题面中,部分细节在样例2中才体现),在理解后就是个大水题.
题目中 optimal 的定义:
结合之前的付款时间与数量, 分别考虑三种所需补价, 取最小.
然后我代码中用了一个尺取的优化,维护指针,把整体复杂度降低到了O(n)
for(int i = 0; i < n; ++i){
for(int k = 0; k < 3; ++k)
while (prev[k] < i && t[prev[k]] + width[k] <= t[i])
++prev[k];
...
}
760E - Nikita and stack 24285764
很有新意的数据结构,想了很久,无果.看tutorial才恍然大悟.
Q:为什么需要逆序 or 为什么是后缀和?
A:(按照我的理解)如果存在一个后缀和 sum[i] > 0,那么可以把栈拆分为两个部分.
|stack1|stack2(top) |[0,i) |[i...n) |
其中stack1是可能为空,而stack2为必定非空的栈. 此时,栈顶的元素必定在stack2中,只需要单独考虑stack2.
即求 max({i|sum[i] > 0})
特殊地 当 {i|sum[i] > 0} 为空时, 栈为空.
Q:为什么是线段树?
A:经过上面的分析,不难看出是维护动态最大值.
只需要维护一个这样的线段树:
Update: 区间加减
Query: 区间最大值 => max({i|sum[i] > 0})
760F - Bacterial Melee 24285774
组合数学+dp.
tutorial中分析的很好,我简单概括一下.
对于一个长为n的串,考虑最终状态为l 节 , 则其方案数为 C(n-1,l-1).这里用了隔板法的思想.
给定串S, 长为l的 合法 子序列个数可以用dp求解.
合法 : 子序列中任意相邻两位不相同.
Q:2.中的dp为什么是 O(n^2)的?感觉上O(n)更合理啊.
A:这么考虑,dp数组同时维护着n个状态.
接受一个输入字符时, n个状态都需要转移.
串S输入n次,所以复杂度为O(n^2)
Q:2.中的dp依然很迷茫.
A:类比其他序列型dp,每接受一个字符的输入,遍历一次dp数组并更新.
那么我们考虑单次遍历更新, 此时长度为l,以c结尾的 合法 子序列 有两类:
a)在本次输入前已经确定的长度为l序列 保持不变,dp[l][c].
b)在本次输入前已经确定的长度为l-1序列 在末尾附加上c, dp[l-1]['a'] + ... + dp[l-1]['z'] — dp[l-1][c] (减去不合法部分)
然而a)b)中有部分重复统计,所以需要 -dp[l][c].
为了优化b)中求和过程,不妨设 sum[l] = 长度为l的子序列个数(无论以什么字符结尾).
Q:以下两个边界条件是否互相冲突
dp[0][i] = 0 , 'a' <= i <= 'z'
sum[0] = 1
A:不冲突,因为sum[0]中还包含了以 '\0' 结尾的空串.
Q:Div.1前面几个大牛的解法直接dp是什么思想?
A:我没看懂...如果你看懂了请务必告诉我,非常感谢.
Comments (0)
