题意上CH看吧
按我做的顺序来说题解
C.我们发现求解的答案符合分数规划的一般形式，于是我们考虑使用分数规划。把分母乘过去，二分答案。
不妨认为当前二分的这个值为ans，然后我们让每个点的权值都-=ans，看真正的ans'是否>ans,只需要判断在题目的限制条件下是否能选出若干个格子使得权值和>=ans。这一步我们考虑用费用流求解。在行列匹配模型中最大权匹配的建图上我们对其进行修改（因为题目中说每行每列最多选一个，所以可以不选），那么我们就让s连向行的i，每个都直接连边（i，t，1，0）这就表示了这一行不选数。然后求最大费用最大流即可。
然后剩下的一个问题就是分数的输出问题。
我的方法是把枚举分母看哪个分子最接近于整数ans就是这个。。。然后另一种方法是可以求出取最优解的时候选的是哪些格子，然后直接输出ans。
A.刚开始看见以为要用FWT，可是我不会QAQ 做完C之后回来看A发现是个水题。我们只要记录f[i][j]表示第i位为j=0/1的数的和是多少，然后就可以直接统计答案了。总之就是 与异或相关的题目按位考虑一般都比较容易。
B.有个十分科幻的结论就是好点对的个数是O（n）的。如果有了这个结论，那么什么都好做了。
说标程的做法吧：就是我们把右端点<=x的左端点都建成一棵权值线段树，当然得可持久，在线查询直接到root[r]里查询即可。
但是这个结论是怎么来的呢？我们又怎么去找这些好点对呢？
其实这类问题一般都和单调栈有关（什么某个区间的数<=什么），考虑维护一个单调递减的栈。
我们发现
1）当一个元素被弹栈时它与把它弹出来的那个元素是一个好点对。
2）当一个元素入栈的时候它与栈顶的元素构成一个好点对。
（当时要能模拟一下这个过程估计也能想出来QAQ）
初次之外就没有别的好点对了。所以好点对的个数是O（n）的。
评论 (0)
