首页 > 其他 > 详细

2015 Changchun Regional

时间:2015-10-30 23:06:45      阅读:497      评论:0      收藏:0      [点我收藏+]

弱没机会去长春,但拿了题来做了,加上请教各路大牛,理论AC了一发,但没实现~(感谢各路有形无形的大牛的指导)

 

A题~Too Rich

给你1,5,10,20,50,100,200,500,1000,2000这几个数的个数,用最多的数组成和为p。

解:一眼看上去像个贪心题,其实,如果没有20,50,200,500这样怪的数,确实只是一个
简单的贪心题。转换一下题目,求p用最多的数组成,设S是所有数的和,即要求s-p用最少的
数组成。对于60,如果贪心的话,对20,20,20,50而言,很明显会造成无解,那么,怎么
办呢?题目的关键在于20,50,200,500这样的数的转化。
我们发现,如果50,500或者20,200不存在了,这个题也是一个贪心题,那么,是否可以把
它们其中一个消去呢?
假设把50,500消去,即变成50*2=100,500*2=1000,那么,可选的数中就不再存在
50,500了。
注意一种情况是~假设题目中可能会存在一种情况是,至少选了一个50或500后会使得情况更
优,那么,我们枚举这4种情况,分别是00,01,10,11 。于是,题目按照一般贪心可解。

  

B题~Count a * b

定义f(m)a×bmodm0(a,b)对数,其中0a<m,0b<mT(T20000)次询问dnf(d)mod264,1n109

解:一种很自然的想法是必须先求解f(m),那么f(m)=m^2-(a,b)中使a*b mod m=0的对
数。定义(a,b)中使a*b mod m=0的对数为h(m)。分析一下,怎么样才能使得
a*b mod m=0呢?设a=ix,b=jy,如果i*j=m的话,那么a*b%m=0,而且gcd(x,j)=1,这是为了避免产生重复计数,有phi(j)。
h(m)=sigma( d*phi(d) )。
发现h(m)其实是一个积性函数,h(pq)=h(p)h(q),
f(m)=m*m-h(m),那么,我们计算所有的m*m的和减去所有h(m)的和即可,那么,怎么才能快速计算所有m*m的和呢?
枚举m乘积所有的素数,可能根据以下式子
(p1^0*2+p1^1*2+p1^2*2+p1*3*2....)*(p2^0*2+p2^1*2+p2^2*2.....)*(.....),
由于h(m)是积性函数,同理可有上面的式子。

  

E题~Rebuild

解:这道题只要确定第一个圆的半径,就可以确定其他圆的半径了。需要分奇偶情况讨论吧,据现场的人说有坑,但弱没机会提交~~

  

F~Almost Sorted Array

解:这道题应该不难,因为只允许去掉其中一个数,我的方法是分两种情况,一种是升序,一种降序,如升序,求它的最长不降子序列>=n-1即可,比较的时候因为只去掉一个数,只需和前两个数比较应该就可以了。

  

G~Dancing Stars on Me

解:一开始也是往凸包想,但后来请教别人才知道,原来可能组成正n边形的只能是n=4的时候,因为坐标都是整数,只能有这一种情况。

  

H~partial tree

 

这题不懂。看一大牛的博客是用到prufer序列。
http://kuribohg.github.io/2015/10/20/changchun-2015-solution/

由Prufer序列可以知道任何一个长度为n−2的序列,其中每个数都不大于n,都可以代表一个合法的树。
考虑一个Prufer序列,可以把它排序,每次在后面添加一个数。
考虑正在添加第i个数,添加的数可以跟前一个数相同,这种情况下假如前面已经有k个数与这个新加的数相同,权值增加f(k+2)−f(k+1)。
否则可以自己新开一段,这种情况权值最大值就是前i−1个形成的权值最大值再加上f(2)−f(1)。
那么就可以DP了,dpi,j表示i个数,序列最后有j个数是相同的,初值dp0,0=n×f(1),转移方程通过上面的分析很容易得到。


以上是这位大牛的想法。因为prufer序列最后是n-2个点,所以会剩下一条边。所以,假如前面已经有k个数与这个新加的数相同,权值增加f(k+2)−f(k+1),我开始时以为是f(k+1)-f(k)

  

J~ Chip Factory

首先si不大,因为涉及到异或的操作,这时,我们可以把所有的si都看成是32位的二进制数。

这样,可以根所二进制数建立一棵trie树。

我们枚举si,sj,把它别从trie树中删除,之后再在trie中枚举sk,这时,求出si+sj,枚举当前位,如果是0,则应当往trie中是1的一方走,如果1不存再往0的走。如果当前位是1同样处理。再把si,sj插入回到trie树中。

这样求出最大值。

  

2015 Changchun Regional

原文:http://www.cnblogs.com/jie-dcai/p/4908988.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!