4.19测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------------------
强省SD的省选题(Day1)...
--------------------------------------------------------------
T1:
打表找规律乱搞了一下...竟然A了...
把n和m拆位一下，拆成像0~100000,100000~100010（二进制）这样
然后假设n拆成了pi这些区间，m拆成了qi这些区间
然后对没个二元组(pi,qi)统计一下答案就好
然后打表发现每个二元组的答案都是一段连续的区间，并且每个数出现的次数都一样
然后把这个二元组的最大最小值求出来，然后用数的个数除以连续区间的长度，得到每个数出现的次数
然后随便算一下贡献就行了
--------------------------------------------------------------
T2:
随便建个费用流，然后只需要求费用小于等于0的情况下的最大流量就行了
可以对流量二分答案
也可以直接跑，限制费用在0一下，一旦必须高于零就减少一些流量，如果流量等于零了就退出
--------------------------------------------------------------
T3:
经典问题了...
线段树，有交叉的时候，每次把较小区间下放，每次只会下放一个方向到底也就是log层，而每次加一个区间会有log的节点，复杂度log^2
算上树链剖分的log，最后复杂度是q*log^3
--------------------------------------------------------------
评论 (0)
