我写的如此不严谨的程序竟然一遍过了,不过这道题的价值不止如此!

我就是不明白了,为什么windows里 A/B=0输出0.000
而linux输出-0.000!!!!!!!!!!!!!!!!!!!!!!!!!!!!

set完爆

multiset秒爆无压力啊

很水。。。

唔,本题就是个构图问题,起点和终点的容量是1,其它的设成Infinite,再求最大流即可!

1.树形并查集
2.路径压缩
3.算出i,j在该集合之前有几个战舰,相减的绝对值-1

倍增排序只能过5组，剩下5组W

注意：
本题有问题，题目要求有几种素数，数据确实忽略了几个数字的组合，但是如
1+2+8=13和
4+4+5=13是不同的情况
数据算作不同的素数，这一点要注意

法一：O(n3)过五组，剩下超时
法二：O(n2)过三组，剩下错误
求先进流解题法

算“直径对数”即可。

怀疑题目有问题……

NOIP2011留念。

NOIP2011留念。

NOIP2011参赛留念。

首先我们会注意到 主人公一定会看到M位画家的画作，所以我们可以枚举 从 第一幅画 开始枚举 每次找之后拜访总画家为M时停止，判断拜访数是否是最小的。
抽象成数学问题，也就是对于起点a，终点b(a<=b)使得artistNumber[a,b](即从a到b的画家数)=M,并计算出所有情况中b-a的最小值.
但这样的时间复杂度是O(n*m)+的
会超时
所以必须想到优化,于是乎,有了以下的优化方法:
既然以a为起始点,则只与以a-1为起点时差一个单位,如果不看第a-1幅画而不影响观看画家总数Sum,则无疑b可以不动
但是不看第a-1幅画,导致Sum!=M,不满足题意,则b不得不往后继续移动,知道再次满足题意.
如 1 2 3 4 1
如果a=1,b=5
则a=2时b依然等于5
而如果a=2,b=4则要满足题意还要b=5

和乘积最大一模一样,稍稍改改就A了

这个问题很锻炼程序实现能力哦~

第九组稍加优化即可
我的题解，太长了，放我blog上了
：michstar.tk