noip2018能力提升训练一解题报告

发布于 20 天前  110 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:noip2018能力提升训练一解题报告

A.「HDU6129」Just do it

Decription

给定一个数组\(a\),定义一次变换为把\(a_i\)设为\(a_1..a_i\)的异或前缀和,求变换\(m\)次后的\(a\)数组。

Solution

~~打表~~可以发现,变换\(2^k\)后,\(a_i=a_{i} xor a_{i-k} xor ...xor a_{i \mod k}\)。

知道这个性质后对\(m\)二进制拆位直接做即可。

B.「Codeforces814E」An unavoidable detour for home

Decription

求满足以下条件的图的方案数。

1. 第\(i\)个点的度数为\(d_i\)
2. 第\(i\)个点到\(1\)号点的距离\(\leq\)\(i-1\)号点的距离(边权为1)

Solution

设\(f_{i,j}\)表示当前总共有\(i\)个点,有\(j\)个点与\(i\)号点在同一层。
\(g_{i,j,k}\)表示当前层有\(i\)个点,有\(j\)个点还可以连出\(1\)条边,有\(k\)个点还可以连出\(2\)条边.
\(N_i\)表示\(i\)个点组成的项链数.

\(f_{i,j}=\sum_{k=1}^{i-j}f_{i-j,k} \times g_{j,c1,c2}\)

1. \(g_{0,0,0}=1\)
2. 当\(i=j=0\),\(k>0\)时,\(g_{i,j,k}=\sum_{l=2}^{k-1}C_{k-1}^lg_{i,j,k-l-1}N_{l+1}\)
表示从\(k-1\)个点中选出\(l\)个点与最后一个点配成环(由于题目要求不能有重边所以大小为\(2\)的环不符要求)
3. 当\(i=0\),\(j>0\)时,\(g_{i,j,k}=(j-1)g_{i,j-2,k}+kg_{i,j,k-1}\)
前者表示从剩余点度为\(1\)的点与最后一个点(设最后一个点剩余点度为\(1\))连边,后者表示选出一个剩余点度为\(2\)与最后一个点连边,剩余点度为\(1\)的点没有变化,剩余点度为\(2\)的点减少\(1\).
4. 当\(i>0\)时,\(g_{i,j,k}=jg_{i-1,j-1,k}+kg_{i-1,j+1,k-1}\)

C.「POJ3685」Matrix

二分水题,咕咕咕。

D.「CF576C」Points on Plane

按莫队算法的方法排序即可。~~当然你也可以写曼哈顿最小距离生成树~~

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:noip2018能力提升训练一解题报告


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前,相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!