脚本宝典收集整理的这篇文章主要介绍了noip73，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
考场想法：第一眼不太可做，于是只去写了部分分，第一个子任务直接写，第二个直接背包即可，后来想了想，想到了之前前缀和那道题，觉得应该也是个结论题，然而自己啥也没想出来...于是跑路了。
60pts：前两个子任务...
100pts：从小到大排序，假设 ([1,k]) 的数能被前 (m) 个数给凑出来，那么如果 (k-1ge a_{m+1}) ，则 ([1,k+a_{m+1}]) 可以被前 (m+1) 个数凑出来，否则答案就是 (k+1) 。
考场想法：一眼矩阵快速幂，然而矩阵能力过弱，所以打了个暴力走人了...
50pts：直接暴力，注意判断 (n<k) 的情况。
80pts：发现所有 (f_{i},i>k) 都是有 (f_{k}) 转移过来的，要求的只是它的指数，所以可以构造一个 (ktimes k) 的转移矩阵，矩阵 ((i+1,i)) 设为1， ((i,m)) 顺着填上 (b_{m-i+1}) ，初始矩阵为 (1times k) 第 (i) 位表示对应位最后求答案时的指数，suBTask3中，只有第 (k) 位初始时为1，然后矩阵快速幂即可，注意矩阵里是指数，由费马小定理，取模应模 (mod-1) 。
100pts：对于 (k) 个数都单独算一遍即可，因为是乘法，所以最后再把答案合并是一样的。
前边一亿@H_777_56@些知识学的都不太行，于是频频暴毙。
貌似卡常...可以加无脸优化...
考场想法：黑白点分开，显然跑个多源最短路，以所有黑点为源点跑个最短路，记录前驱，因为数据是随的，所以直接跳前驱即可，发现过不了自己造的数据，发现如果最短路相同的，需要选择路上白色点个数多的那一条，改了就过了。想了想，发现应该是假的，于是预估得分0pts。
然而事实上因为数据是随的有70pts，边权设小了，设大点就过了...
但它确实是假的，随便造就能卡。
正解就是白点取所有跟它相连的最短路上的边，权值最小的哪一个即可。
考场想法：一看就是状压dp，然而还是写不出来，糊了个暴力上去....
然而暴力还错了...
正解：就是状压dp...
对于一种拓扑序 (P) ，可以求出原图中有几条边可以被这个拓扑序满足，假设有 (k) 条，对答案的贡献就是 (2^{k}) 。
用状压DP计算，每次新加入一个点可以算出有几条和这个点有关的边被满足了。
粘的题解
因为其他大佬改的太快了，所以又加了四道....
第一道是轮廓线dp，不会，第二道也不会，第三道神奇dp，第四道数学题。
直接暴毙...
有时间可能会补...
以上是脚本宝典为你收集整理的noip73全部内容，希望文章能够帮你解决noip73所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。