4
12
2015
0

CH Round #64 - MFOI杯水题欢乐赛 day1

题意上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)的。

 

Category: contest hunter | Tags: | Read Count: 344

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com