【纪中】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]的概率。可用树形背包来解决。

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

Day11

【虚】
题意:从数轴的原点开始,有1/4的概率往左或往右走,有1/2的概率被-1s(站在原地不动)。询问t时到p点的概率。
把一个点拆成两个点,则题目可化成有1/2的概率往左或往右走,询问2t时到2p点的概率。可用排列组合求解。
【传送】
题意:一张n*m的图,从(1,1)开始,可以往左或往下走,在一些点有传送门,可以传送到另一个点,询问最大收益。
tarjin缩点+spfa即可。(为什么说的那么简单?因为我还没写出来)。
【串】
题意:n次操作,有p的概率出现1,否则为0。每个长度为x的1可以获得x^3的分数,求答案的期望。
假设在i之前已经出现了x个1,那么如果新加入的是1,对答案的贡献是(x + 1)^3 - x^3, 化简得3x^2 + 3x + 1。
所以,现在只需要维护x^2、x的期望即可。
x的期望:x1[i] = (x1[i - 1] + 1) * x
x^2的期望:x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) * x
答案期望:sum += (3 * x2[i - 1] + 3 * x1[i - 1] + 1) * x

[NOIP2016]换教室

换教室

任意最短路算法预处理出任意两点最短路径,dist[u][v]即为点u与点v的最短距离。

求最小期望使用DP。

设f[i][j][0/1]到第i个时间段为止一共有j次申请,此刻不申请/申请的最小期望。显然f[i][j]与任意f[i-1][k],(k<=min(j,m))有关,还与申请是否被通过以及前后两教室的距离,即w[i]与dist[u][v]有关。

由期望的定义可知,

时间复杂度为

继续阅读[NOIP2016]换教室