cty

cty

noip模拟6

posted on 2021-06-12 19:40:15 | under 考试总结 |

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分的代码,实在没法交代,,,,,人倒是差点给交代了

虽然有的题知识点没学,但基础暴力分都没有就说不过去了,还是代码能力弱,还有脑子不清醒,以后要集中精力,知道自己在码什么

数学逻辑和运算能力差,自己多推推式子,多思考