题目大意是给出n组包含2个关键字的元素，求同时满足第一个关键字递增和第二个关键字递减的序列的最长长度以及输出其中一个满足条件的序列。
对于要求两个关键字同时分别满足不降/不升，我们可以先对一个关键字进行排序，则实际上只需对另一个关键字进行DP即可求解。由于n<=1000所以用O(n^2)的DP就可以AC了。不过实际上用O(nlogn)的DP也是可以做的，只是因为存在相同数字的情况不能直接顺推，需要对序列求反（即对排序关键字的条件取反），利用一个数组记录下更新序列过程中更新的每一个元素在序列中的前一个元素，最后倒推出整个合法的序列。
3002145 2008-07-24 15:07:51 Accepted 1108 FPC 00:00.00 412K IwfWcf@LZOI
题目大意是给出m本书的书页，要求让k个扫描员来扫描，每个扫描员最少要扫描一本书，求使扫描书页最多的那个扫描员扫描的书页最少的方案，如果有多种方案则输出前面的扫描员扫描的书本较少的方案。
这是一道非常经典的DP题，DP的做法可以参见方奇2000年的国家集训队论文。但对于大数据而言这题更加好的做法是参数搜索，可以将时间复杂度降至O(mlogt)，其中t为复制书稿的最大可能页数和最小可能页数之差。简单地说参数搜索就是利用二分查找来逼近确定一个最优参数值使其能够满足题目条件，就本题而言这一参数值就是扫描书页最多的那个扫描员扫描的书页最少的页数需要使得所需的扫描员不超过m。下界显然是书页数最大的那本书的书页，上界则是第k本到最后一本书的书页数之和。
2997140 2008-07-22 19:03:04 Accepted 2002 FPC 00:00.17 404K IwfWcf@LZOI
题目大意是求出a<=200的所有a^3=b^3+c^3+d^3的组合，其中b<c<d。
很容易想到暴力的4重循环枚举做法，时限是10s，我估计应该是可以AC的。但次方是递增的，因此很容易想到最后一重循环可以用二分查找代替。具体做法是先预处理出2到200的次方用一个数组记录，然后按递增顺序枚举a、b、c，有一个很显而易见的剪枝是如果算出的d的次方比c的次方要小可以直接break，然后二分查找d的值，如果能够找到就输出这种组合。其实还可以进一步优化，次方和的组合总共只有20100种，算出再后排序就可以改成两重循环+二分查找了，但还要注意处理第一个数相同而第二三个数不同的情况。不过这题的输出数据只有一个，所以有一个最强优化--打表……
2993787 2008-07-21 16:03:27 Accepted 1331 FPC 00:00.09 412K IwfWcf
博文
所有评论
