【纪中】Day1

【队伍统计】
题意:在n个人中,有m条矛盾关系(u, v),表示编号为u的人想要排在编号为v的人前面。询问矛盾关系不超过k条的排列。
这题早上没有做,也没听讲,但看了眼题目感觉是深搜或者状压dp。
这里采用状压dp。用S表示当前已经排好队的状态,则f[s][k]表示当前状态违背的矛盾关系。对于一个要新加入的i,需要满足i不在排列中。设i与当前排列产生的矛盾关系为q,
那么f[s][k]则可以转移到f[s|(1 << (i - 1)) ][k + q]。暴力转移时间复杂度是O(2^n * n ^ 2 * k)。
由于矛盾关系没有重复,则可以把与i有矛盾关系的用二进制来表示。矛盾关系数便可以表示为&操作后的1个数。
T1【序列问题】
题意:给出一个序列,求每个区间的最大最小值的乘积和。
以前做过一道看上去相似的题目,先暴力预处理,再线段树修改。今天也是怎么想,但显然不对。。。
正解对序列进行分治,考虑过mid的区间[l,r]对答案的贡献。枚举右端点r,那么当右端点的指针往右移时,max增加,min减少,左端点l满足max 𝑙 = min(𝑟),则可以左移。于是,相同的max、min的贡献就可以O(1)求出。序列分治可以用递归处理。
T2【带权排序】
题意:序列A的每一个数在一个区间中随机生成,每个位置有权值si,求排序后A的期望。
期望。。。不会化!不会求!没听懂!
T3【概率博弈 】
题意:给出一颗以1为根的树,树上权值随机生成,求从根节点到叶节点的期望。
设当前要求ans > x。因为只会是向大于x或小于x的方向走,设权值 >x的为1,否则为0.相当于有m - x + 1个1,x- 1个0,则问题转化为求f[1]的概率。可用树形背包来解决。

第一天给我的感觉是题目好难,唯一看的出解的还不需要做。下午的讲题有点难懂,第一题分治方法好理解,但最关键的前缀和处理则一句跳过。第二题期望本来就不会,还要化简。第三题转化听懂了,但树形背包是什么???

发表评论

电子邮件地址不会被公开。 必填项已用*标注