一觉起来到公司做SRM，总感觉没有亲临现场做的时候那么紧张激动了，脑子不会那么迟钝，当然也缺少了些许的灵感。这次的1000又是图论，神奇的没有人过，于是继续果断放弃，要允许自己菜，嗯。
1. 250P Inequalities
给出N<=50个诸如”X op Number”的式子，其中op包括大于，大于等于，等于，小于，小于等于五种，而Number是0-1000的整数。问这些式子最多同时能满足几个。
这题想复杂了，对于250，我还是会先相当枚举的，但是我居然觉得得枚举区间，那就是1000^2了，再乘个50怕是吃不消。于是又想了下，其实每个等/不等式就是一个区间，所以题目问的就是被这些区间覆盖次数最多的点。这个是个挺经典的问题了，具体就是每个区间的开始和结束放到同一个数组里，然后按照坐标排序，接着扫描一遍加加减减就可以了。当然这里区间的转化要利用到数字是0-1000的这个条件，对于大于小于的不等式，下限和上线分别取负数和10000就可以了。同时为了方便处理小于和大于号，直接把所有的数乘以2即可~
2. 500P NumberPyramids
15 6 9 3 3 6 2 1 2 4
如上所示的数字金字塔，最底层有N<=1,000,000个正整数，然后往上每层少一个数，每个数都是下方两个数的和，问最底层N个数而最上面的数为T<=1,000,000的数字金字塔方案有多少个。
首先拿纸笔稍微推一下，假设最下面这层N个数分别为a0, a1, … aN-1，那么最上面的数等于C(N-1, 0) * a0 + C(N-1, 1) * a1 + … + C(N-1, N-1) * aN-1。由于这N个数都是正整数，至少为1，所以当底层的数个数为N时，最顶层的数至少为2N-1。由于T<=1,000,000，我们可以推出，最底层的数最多只能有20个。
好的，现在问题就转化为，有N个东东，其价值分别为C(N-1, 0), C(N-1, 1), … C(N-1, N-1)，每种至少选一个，其价值总和刚好为T。因为至少选一个，那先从T里分别减掉每个的价值，最后就转化成一个简单的N个物品的多重背包，复杂度为N*1,000,000，可以接受。
由FireStats提供支持
Hang Hang
2010/01/20 at 11:48 上午
sf一个，史上最偷懒的一次小结- -
[回复]
notonlysuccess 回复:
一月 20th, 2010 at 4:20 下午
比我的不偷懒
[回复]
daxia
2010/01/20 at 12:09 下午
板凳，ym hh来了
[回复]
Navi
2010/01/20 at 9:46 下午
ym半夜的都做的
[回复]
Hang Hang 回复:
一月 20th, 2010 at 11:47 下午
这次显然没做……
[回复]
daxia
2010/01/20 at 11:47 下午
srm都是这个时间吧
[回复]
ACong
2010/01/21 at 9:13 上午
我觉得250那道可以用这样的方法，来自于之前师父UVA报告中的一种方法，不知道师父觉得如何：
int array[1000];
memset(array,0,sizeof(array));
while(读入一个不等式){
int i=0;
if(是小于)
for(i=0;i<Number;i++)
array[i] += 1;
elif(是小于等于)
for(i=0;i=Number;i–)
array[i] += 1;
elif(是大于)
for(i=1000;i>Number;i–)
array[i] += 1;
}
遍历array,输出最大的数字应该就是答案了吧？
[回复]
katie
2010/01/29 at 10:37 下午
HH该写新文章了~
[回复]
Hang Hang 回复:
一月 29th, 2010 at 11:19 下午
嗯。。。最近偷懒了，呵呵，而且又没比赛。
PS，等看完神话了想写一篇。。
[回复]
katie 回复:
一月 30th, 2010 at 4:41 下午
写观后感~？
[回复]
Hang Hang 回复:
一月 30th, 2010 at 6:30 下午
嗯
[回复]
死肥羊
2010/01/30 at 7:40 下午
死肥羊来了~大大地仰慕一下~
[回复]
Hang Hang 回复:
一月 30th, 2010 at 10:00 下午
热烈欢迎肥羊dd～～加油～
[回复]
Ascorpior
2010/07/18 at 8:28 下午
YM HH，500p 的转一下，TC的题目很经典，HH的题解更精辟
[回复]