Algorithmic Engagements 2010 Sweets

http://main.edu.pl/user.phtml?op=showtask&task=cuk&con=PA2010
这题目的意思是。。。有N个物品,N<=24,重量<=10^9,分成3堆。。
设3堆重分别为A,B,C且A<=B<=C,求C-A的最小值。。。
看到这个N<=24并且分成3份不难想到要折半搞了。。
考虑前N/2和后N/2个物品的两个方案,
设前N/2的物品的方案是(a1,b1,c1),

后N/2的物品的方案是(a2,b2,c2)
那么。。由于和是固定的。。只要考虑两个。。不妨考虑a和c。。
设S为所有物品和
那么a1+a2<=S-(a1+a2+c1+c2)
<=>(a1*2+c1)+(a2*2+c2)<=S
S-(a1+a2+c1+c2)<=c1+c2
<=>(a1+c1*2)+(a2+c2*2)>=S
设F(x)=ax*2+cx,G(x)=ax+cx*2,T(x)=cx-ax
也就是说F(1)+F(2)<=S,G(1)+G(2)>=S,求最小的T(1)+T(2)。。
这是个傻叉问题。。。排序降维之后直接数状数组就好了>_<。。。

POI 2010 Stage II 题解

终于搞定了Stage II >_<
下面是题解:
Antisymmetry
这个题目很容易想到枚举中间的,然后二分向两边扩展并用倍增hash快速判断。。注意到NLogN的空间会悲剧。。
我的办法是。。空间是NLogN的。。但是底数是可以变的>_<。。我把底数开到20。。需要的空间就少多了。。
虽然速度慢了。。但还好不至于MLE。
PS。我傻叉。。标程是O(N)的。。
Hamsters
这题的话相信一看到基本会想到快速幂吧。。我注意到这个问题可以转化为一个图论问题,就是n个点的图,AB两点之间的边权是B接在A后面需要新增加的长度。那么其实说白了就是求一个给定边数的最短路径。。这是一个经典问题。。套一下就可以了。。
Blocks:
首先我看到这个题目之后。。想了一会儿。。直觉告诉我贾如当前询问k,那么令C[i]=A[i]-k。。i到j这一段可以全部变得大于等于k的条件是Sum(Ci..j)>=0。。我不怎么会证明。。不过就这样吧。。
然后可以感觉到我们需要求的就是最长的和为正的子串。。
我一开始随便弄了NLogN的做法。。后来发现傻叉爆了>_<。。
看了标程之后才明白。。。把这个看成几何的问题,令Sum[i]为Ci的部分和。
考虑所有点(i,Sum[i])。其实求的就是x跨度最长的终点比起点高的线段。。
那么对于一个终点。。如果它的右上方有点。。显然那个点更优。。
起点也一样。。
所以的话。。我们可以找两条链。。都由那些右上方无点(左下方无点)的点构成。。
然后显然答案就是在两者之间。。然后扫描一条链。。另一条链上的对应点显然会单调移动。。就O(N)了。。。
Sheep
这个题目题型比较经典。。关键是如果在dp的过程中判断对角线是否违反条件的话。。显然是会悲剧的>_<
。。。。其实最关键的一点是。。合法的对角线永远是合法的,非法的永远是非法的。。
比如说一条对角线上有点。。那么显然点不会变没。。
一个对角线两边是偶数。。那么多条两边是偶数的对角线混在一起分开的区域显然也都是偶数,偶数-偶数=偶数。。
两边有一边是奇数。。那边无论怎么也分不好。。
所以预处理出所有合法的对角线。。直接dp就好了。。
Teleportation
这题目好囧。。
首先最终的结果的话。。按照与点1的距离。。当然分为6层(这个可以调整来证明)。分别是距离0到5。。
然后可以发现跟1距离为1、2的点,跟2距离为1和2的点。。层数是无法改变了。。
其他的点则可以随意+到某些层里去。。
首先发现把层1的点调到层2去。。结果不会变差,
层3调到层4也是一样。。
所以把剩下的点放到第2层或第3层。。
考虑到2、3层之间的对调。。可以发现必然是要么全放在2层,要么全放在3层。。
然后就好弄了。。

POI 2010 Stage I 题解

Guilds
傻叉题,首先如果有一个孤立点显然不行。其次把图看成树(忽略多余边),奇数层染K,偶数层染S就可以了。。
Railway
见洲妹的博客>_<
Beads
首先注意到如果枚举每个K。。那么实际上要考虑的项链总个数为N/1+N/2+…=O(NLogN)
那么枚举K的话。如果能快速计算出所有项链的Hash值来判重,还是doable的。。
那么Hash用倍增算,判重的话要考虑翻转,用两个集合搞,一个集合保存对称的串,一个保存非对称的。。
遇到对称串,放入集合,遇到非对称的就把它和它的反转一起放入集合。。
然后结果就是|对称集合|+|非对称集合|/2
Divine divisor
很容易想到因式分解之后瞎搞。。但是我用rho+miller-rabin搞了很久还是只有89分>_<。。
看了标程之后才明白,因为所有数小于10^18,那么首先用所有小于10^6的素数去除。。
那么接下来的数如果有3个质因数pqr,就矛盾了。所以只可能是p,pq,p^2这样的形式。。
然后考虑它们之间两两的最大公约数。由于所有数最多只有2个素因子,那么如果该最大公约数是某数的真因子。就肯定是素数。。
然后考虑某数可能是p^2的情况。。根号一下就可以了。。
然后剩下来的数要么是pq,要么是p。。而且两两之间要么相等要么互质。。所以可以直接拿pq去除所有数。。结果算两份就可以了。。
然后用miller-rabin判断是否是素数。。OK了。
傻叉题,对于每个数储存一个数组表示在原序列中的位置集合。。
然后一个个往下找,每次找当前位置后的第一个询问序列的当前数。。
找不到就挂了。。

SGU 366. Computer Game

http://acm.sgu.ru/problem.php?contest=0&problem=366
这题的意思就是每个东西有2个分量a和b,从N个东西里选K个东西,让这些东西的a分量之和A和b分量之和B,|A-B|最小,在此前提下A+B最大
N<=60000,K<=20,0<=a,b<=50
首先dp的话,要记录当前A-B为t的之后,A+B的最大值。。
暴力DP显然会挂。。优化了半天。。时间在SGU上居然第三: )
首先可以注意到对每个东西(a,b)可以用(a-b,a+b)来表示它,而由于最多选K个东西,所以当相同a-b的东西超过K个的时候。。显然除了a+b最大的那K个之外就没用了。。
所以总过最多也只有20*100=2000个东西。。
然后就差不多了。。Dp一下就可以了。。

[Shoi2007]Bookcase 书柜的尺寸

[Shoi2007]Bookcase 书柜的尺寸

Time Limit:5000MS  Memory Limit:65536K
Total Submit:21 Accepted:7
Case Time Limit:1000MS

Description

Tom不喜欢那种一字长龙式的大书架,他只想要一个小书柜来存放他的系列工具书。Tom打算把书柜放在桌子的后面,这样需要查书的时候就可以不用起身离开 了。显然,这种书柜不能太大,Tom希望它的体积越小越好。另外,出于他的审美要求,他只想要一个三层的书柜。为了物尽其用,Tom规定每层必须至少放一 本书。现在的问题是,Tom怎么分配他的工具书,才能让木匠造出最小的书柜来呢?
Tom很快意识到这是一个数学问题。每本书都有自己的高度hi和厚度ti。我们需要求的是一个分配方案,也就是要求把所有的书分配在S1、S2和 S3三个非空集合里面的一个,不重复也不遗漏,那么,很明显,书柜正面表面积(S)的计算公式就是:

由于书柜的深度是固定的(显然,它应该等于那本最宽的书的长度),所以要求书柜的体积最小就是要求S最小。Tom离答案只有一步之遥了。不过很遗 憾,Tom并不擅长于编程,于是他邀请你来帮助他解决这个问题。

Input

文件的第一行只有一个整数n(3≤n≤70),代表书本的本数。接下来有n行,每行有两个整数hi和ti,代表每本书的高度和厚度,我们保证 150≤hi≤300,5≤ti≤30。

Output

只有一行,即输出最小的S。

Sample Input

4
220 29
195 20
200 9
180 30

Sample Output

18000

Source

Day2

哎。。回到正常状态了。。开始写解题报告>_<。。。
反正我现在感觉题目神马做多少都是浮云。。。也就那么几个核心思想>_<。。
首先这题自然要dp。。暴力dp记录每层显然不可能>_<。。dp自然需要一个序。。宽度显然不能为我们提供序>_<。。因为对于宽度的操作是和。。而和这玩意是对称的。。。
所以要找一个序。。。
1)Dp要有序。。。寻找序。。
2)神马是序呢。。一般来说是要先决定最重要的>_<。。而高度大的显然比较重要,所以按高度排序。。
那么状态就出来了。。Dp[i][w1][w2]表示前i个柜子,第一个层宽度和w1,第二个层宽度和w2。。
那么第三个层的宽度和也就是可以算出来。。
表示神马呢?表示三层每层最大值的最小和。
考虑第i个放入w1。。如果w1为0。那么由于后面的都比现在的小,第一层最大值就是第i个的高度。。
如果w1不为0.那么对最大值就没有影响。。
就可以做了>_<。。常数要优化一下。。。

NORP。。。

NOIP果断悲剧。。。。
哎。。。最后一题我以为是搜索题>_<。。结果是DP。。。
我一通乱搜>_<。。死定了。。。
然后第二题我似乎常数写的好大啊。。。似乎要TLE  >_<。。。
哎。。。这次的题目太xx。。。大家都要400了。。就我要爆0 >_<。。。求鄙视 T_T。。。
哎。。最后春哥还是保佑我了。。。第二题虽然常数很大在我的机子上测各种TLE。。但是测评机非常强大还是让我A了。。。最后一题不知道怎么的在Windows上怎么测都70分测评机上却80囧。。。
我后来搞到了数据和程序发现还真这样。。。。。这。。我写的是确定性的卡时搜索啊真囧。。。
还有就是我还剩1个小时的时候发现第一题写错了囧。。幸好改过来了T_T
哎。。。太弱了。。球鄙视

Page 1 of 212