[NOIP]11.21总结

T1:粉刷匠
刚一开始看错题目啦!我认为竖着也可以粉刷,然而并不是,这只是每行粉刷。
因为每一行都是独立的，所以可以分开一行一行染色，随后染色的数目等于T，对于每一行，只需要看这一行用j次粉刷能粉刷的最大数目是多少就可以了。

T2:迷路
在不知道是矩阵乘法时，我是没思路的，当知道是矩阵乘法时只知道边权为1时怎么做。当边权为1时，矩阵乘法一次邻接矩阵，就相当于都走了一步。
因为边权很小在$[1,9]$之间,所以可以将一个点拆成9个点,将他们连接起来。做T次矩阵乘法，就能得到答案。

T3:游戏
将对应关系建成一幅图，发现整个图是有若干个环组成。答案就是求若干个环的大小相加为N时的$\Sigma(LCM)$。到了这一步就不知道怎么做了。因为这里有一个性质

考虑最小公倍数不为1的情况，这它为m。
则m=p1^a1*p2^a2…，而对于一个m，存在一个序列的最小公倍数为m的充要条件是：
p1^a1+p2^a2+….<=n。

按照上述条件做一下背包就可以了。$F[i][j]$表示做到第i个质数$\Sigma$为j时$(j<=n)$