noip模拟6

# 6.10 考试总结 ## T1 辣鸡 考试的时候没想到单个矩阵中氢键的数量可以直接算 结果像个傻子一样计算横纵坐标 最后调了一个多小时才和样例对上…… 然后单题爆0 以后还是要好好分析性质，想出靠谱的思路再码 求氢键的数量分两部分 单个矩阵氢键的数量就是$(x_2-x_1)*(y_2-y_1)*2$ 至于矩阵相连的氢键数量，按照x和y关键词排序， 将横向或纵向距离为1的矩阵计算相交的长度，再判断有没有斜对的两个氢键 ## T2 模板 线段树进阶里的题，先留坑 ## T3 大佬 考试的时候一直在证结果只和队列里的元素有关，结果不仅没证出来，样例都没整过。。。只好输出0 将每天做的题看成一个长度为k的队列，计算队列里的元素最大值出现的概率 排名第i的元素成为最大值有$i^k$种可能 其中有$(i-1)^k$种可能，i不在队列中出现 故i成为最大值的概率为$i^k-(i-1)^k$，i对答案的贡献为概率乘以劳累度 每天都以这种方式计算，所以最后将答案乘以$n-k+1$ ## T4 宝藏 做到这个题还剩一个多小时，看完题面很迷茫，不知道怎么维护最小值 瞅到%40数据满足$1<=n<=8,v<=5000$，且所有的$v$都相等 也就是，说求个$floyed$，再计算$v*max\sum_{i=1}^{n}dfs(i,x)$即可 抱着40分在手的信心，且没有注意到$v$求了两次，交上了一个5分的代码 我就很不明白，我当时脑子是瓦特了吗竟然会乘一次$v$，再乘一次$n-1$ 还是对自己在干什么没有清楚的认识 正解之一是搜索$+$状压~~尽管单独dfs或状压也能AC~~ 设f[s]表示当前连边情况为s，有一个显然的结论是最优情况一定是颗树，~~这就是我乘n-1的原因~~ 因为各个宝藏屋恰好完全联通，再加一条显然没用，少一条不联通 所以用状压储存各个宝藏无有没有在树上 只需要考虑用当前的状态来更新的各个情况 即，若存在有边直接相连$i,j$，满足$i$属于集合$s$，$j$不属于集合$s$，就计算所有这样的$i$贡献的最小值 $f[s']$=$min${${f[s]+dis[i][j]*deep[j]}$} $j$比$i$更深一层，用$deep[i]$更新$deep[j]$ $j$的深度随更新它的i变化，记录$deep[j]$的初值，回溯时再赋回初值即可 由于$j$的在树上的深度只和父节点的深度有关， 所以不要用递归深度来更新，因为递归深度只代表树的大小 ## 总结 没有认真分析题就开始码，最后码出个0分的代码，实在没法交代，，，，，人倒是差点给交代了 虽然有的题知识点没学，但基础暴力分都没有就说不过去了，还是代码能力弱，还有脑子不清醒，以后要集中精力，知道自己在码什么 数学逻辑和运算能力差，自己多推推式子，多思考