4.19测试总结

--------------------------------------------------------------
强省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
--------------------------------------------------------------