【CJOJ】4.9考试

day2

1.lplane

今天第一题是水题呢。。一眼秒题

不过居然写萎了。。被r_64无情嘲讽

就是让你把平面上一堆点连成一个多边形

选最左边一个点然后以这个点建系,将其它点按极角排序,极角相同的按距离从大到小排

然后注意到有一种特殊情况:前几个点若在同一条直线上要从近到远

扫一遍reverse一下就可以了

2.fibseq

蜜汁数学题

作为数学鶸无法做出这么高端的题目

3.matrix

听说这叫做斯坦纳树问题 好高端

大概理解了当矩阵中的数不大于8时的做法

设\(dp_{i,j,S}\)表示在(i,j)格子,拿到数的情况为S的答案最小值

先枚举S,在枚举i,j

有两种转移:

$$dp_{i,j,S}=\begin{cases}

dp_{i’,j’,S}+dis&直接从i,j走过来,不收集数字\\

dp_{i,j,S_0}+dp_{i,j,S-S_0}&将之前出去收集的数字合并起来\end{cases}$$

第一种跑SPFA即可;第二种枚举\(S_0\)即可

至于正解。。要用随机映射

将每一种数字随机映射到1-k的一个数字,跑几百遍然后取个最大值= =

今天知道了这就叫做蒙特卡洛算法?

蒟蒻做不动= =

说点什么

  Subscribe  
提醒