NOIP集训-10.20总结

水啊水..
-------------------------------------------------------------------
 
math:SuperOjP941
贪心,已乘积和最大为例。
首先把a排序,然后就只需考虑b的排列
假设b中有一个逆序对(i,j),易证交换(i,j)后比原来更优
因此b中一定没有逆序对,即升序排好了序
乘积最小同理易证
-------------------------------------------------------------------
tree:SuperOjP942
SB 倍增...
-------------------------------------------------------------------
shortest:SuperOj943
考虑从右往左加点
每加入一个点,考虑更新这个点以及其他点的最短路径
考虑floyd算法
但是发现需要改变的点一定是和当前加入的点有关的
因此有一层循环就已经固定下来了
因此就只有两层循环,n^2
统计答案就暴力统计,也是n^2
因此总的复杂度就是O(n^3)的
-------------------------------------------------------------------