NanoApe's Blog

既是咸鱼又是辣鸡

Codeforces糊做

NanoApe posted @ 2016年6月03日 16:35 in 蒟蒻不做题提前退役 with tags codeforces , 617 阅读

update:16.06.30

671 A. Recycling Bottles

枚举两个人分别拿什么瓶子(只需枚举最大和次大)然后取最小值即可(注意:可以只移动一人)

671 B. Robin Hood

给一列数,每次将最大的-1,最小的+1,重复 $K$ 次,求最后的极值

直接模拟比较麻烦,可以考虑二分结束操作时的最小值和最大值从而得到极值

671 C. Robin Hood

给一列数,定义 $F(i,j)$ 表示将 $[i..j]$ 删去后序列两两最大gcd,求 $\sum F(i,j)$

一开始定义 $pr[i]$ 表示当左端点为 $i$ 的时候右端点的最小值

从大到小枚举gcd,将其倍数全部提出来,容易知道有三段 $F$ 区间的值一定是等于d(大于d的已经被计算过了)就可以通过线段树区间修改 $pr[i]$,计算总数减少了多少即是 $F(i,j)=d$ 的个数

这样做有点麻烦,不妨设 $nx[i]$ 表示当左端点为 $i$ 的时候非法右端点的最大值,然后“计算总数减少”改成“计算总数增加”,这样也是一样的

671 D. Roads in Yusland

一棵大小为 $N$ 的树,树上的边全部损坏,$M$ 个工人能修复从 $u_i$ 到 $v_i$ 的路(保证其 $Lca=v_i$)花费为 $c_i$,问把所有边修好的最小费用

dfs一遍,将工人按 $x_i$ 的dfs序排列,子树也记录下dfs序中对应的区间;然后第二次dfs统计答案,用线段树维护轮到哪个工人修路的最小代价,每次dp从里面转移,dp再转移到线段树中,例如将某棵子树除外的其他子树信息加到线段树中

顺便其对偶问题可以贪心解决

660 C. Hard Process

给01序列,最多能将 $K$ 个0修改成1,使得全部都是1的子串尽可能长

双指针大法,0太多了就右移左指针,否则右移右指针

660 D. Number of Parallelograms

给 $N$ 个点,无三点共线,问有多少平行四边形

两两枚举线段然后排序,求得多少对重复的线段,最后除以4即可

660 E. Different Subsets For All Tuples

设 $F(a)$ 表示序列 $a$ 的不同子序列个数,现在给你序列集 $S$,其中包含全部长度为 $N$ 并由 $[1..M]$ 构成的所有可能的序列,求 $\sum F(a \in S)$

首先为了去重,有多个位置匹配则取最前面,那么就可以分成三个阶段(子序列未匹配完且以关键字作为结尾的方案数、子序列未匹配完且以非关键字作为结尾的方案数、子序列匹配完的方案数)分别设为 $A,B,C$,则转移方程为

$$A(i)=m(A(i-1)+B(i-1))$$

$$B(i)=(m-1)(A(i-1)+B(i-1))$$

$$C(i)=mC(i-1)+A(i)$$

685 D. Kay and Eternity

给 n 个点,问端点为整数边长为 K 且包含 $i=1,2,..,n$ 个点的矩形有多少个

转成矩阵求交

离散化 y,然后按 x 排序,维护每列的最后一次变化时刻和当前值,复杂度 $O(nlogn+nk)$

662 C. Binary Table

给 n*m 的 01 矩阵,每次可以取反一列或一行,求最少 1 个数,$n<=20,~m<=100000$

假设行的操作为 mark,预处理出经过操作 mark 后有 k 个 1 的列数(dp[k][mark])然后就可以 $O(n2^n)$ 求得答案

关键是 dp 怎么求,我们一开始能得到 dp[0],接下来构造 $F[k][mark]=[count(mark)=k]$,然后我们会发现 $dp[k]=dp[0]*F[k]$,这一步是用 fwt 实现的,总复杂度 $O(n^22^n)$


登录 *


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