codeforces #381 div2

http://codeforces.com/contest/740

A:现在有n个某种物品,要买k个使得n+k是4的倍数,可以的购买方案为a元1个,b元2个,c元3个,每种方案都可以买无限多。

思路:需要注意买多个未必比买少个贵..

所以分情况讨论:n%4==0,输出0

n%4==1,需要买3+4k个,

可以的方案为,买1个c,或者3个a,或者1个a 1个b(此处用价钱指代方案,下同)

n%4==2时,需要买2+4k个

可以的方案为:2个a,或者1个b,或者2个c

n%4==3时,需要买4K+1个

可以的方案为:1个a,或者1个b+1个c,或者3个c

注意要开long long.

 

B:

题意:给出n个数,以及m个子串,从中选若干个(可以不选或者全选),女孩的幸福值的计算方法为:a[i]*cnt[i],a[i]为值,cnt[i]为第i个数在选中的子串里出现了几次(只考虑位置,相同的值算成不同的数)

思路:n,m很小,一个子串如果最后收益为正,就选,否则不选,暴力即可。

 

 

c:题意:m个区间,要求构造一个长度为n的数组,满足m个区间中,每个区间的mex值中的最小值最大。

s思路:很容易想到的是…这个最大的mex 不可能超过每一组区间长度,假设最小的区间长度为mn

那么是否一定可以构造出mex为mn的数组呢?

是的。

只需要按照

0,1,2…mn-1,0,1….的方式构造即可。

d:题意:一棵树,给出边权和点权,定义点v控制点u,当且仅当u是v的子树中的点,并且dis(u,v)<=a[u],其中dis(u,v)为点u到点v路径上的边权和,a[u]为点u的点权,现在问对于每个节点v,其能控制的点有多少个。

思路:先写了个rmq+dfs的lca。。。那么任意两个点的距离都可以O(1)得到了。然后不会了233333.

upd:和lca没有什么关系,因为一个点能控制另一个点这两个点一定在一条通向根的链上,因此距离直接减一下就好了。

机智的做法:dfs的时候维护一个栈,对于栈中序列,后面一半是对当前点有贡献的。问题时求对于每个v统计其能控制多少个u,现在我们固定u,考虑能控制他的v。这些v在树上的形态时一条链 ,借助第二类前缀和的思想,对于u标记+1,对于u往上的离根最近的且能统治u的v上面的一个标记-1,然后dfs后序遍历(也就是链的起点时距离根远的那一边),距离处理的时候,只需要在递归之后更新ans就好了。

栈里面维护,到哪个节点,从根下来,边权和最大,找边权和>=当前边权和-a[u]的地方。

启示:由于两个存在统治关系的点在一条链上,边权都为正,边权和具有单调性,单调的东西,容易想到二分处理。

 

 

 

e:题意:那个数,定义hill为一段连续的区间,满足该区间为严格单峰。现在有若干操作,每个操作是对某段区间的数同时增加一个数,问每次操作后,所有的hill中,宽度最大的(区间长度最大)的是多少。

思路:同时增加一个数很线段树。。。但是要维护什么呢。。。?

猜测:肯定要维护一个区间中hill的最大宽度…

但是合并的时候要怎么办呢。。。

考虑两个方向的合并。。。

所以还要维护一个区间中,包含右端点的向左单调减延伸的长度,以及左端点的值。

同理,要维护一个区间中,包含左端点的向右单调增延伸的长度,以及右端点的值。

那么每次pushup的时候,就是两个区间hill的最大值,以及两个方向合并的最大值中取最大。。。

。。。上面是我口胡的。。。

解题报告

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz