这是NOI计划的第二份题解。NOI1998的6道题是[个人所得税][免费馅饼][围巾裁剪][SERNET模拟][软件安装盘][并行计算],相对于NOI1997要稍难一些,不过还都是可以接受的。
[个人所得税]是一个...
|
|||||
|
这是NOI计划的第二份题解。NOI1998的6道题是[个人所得税][免费馅饼][围巾裁剪][SERNET模拟][软件安装盘][并行计算],相对于NOI1997要稍难一些,不过还都是可以接受的。 [个人所得税]是一个... 很明显,这个题是求连通块的个数。关键在于正确判断两个矩形相交。 我们知道,在一维的数轴上,两个区间[a,b] [c,d] (a<=b),这两个区间相交的充分必要条件是c<=b。对于题中所述... 求连通块,由于数据范围过大,需要离散化,把10000压缩成2500。然后在指定区域内求出连通块的个数,BFS会有一点超时,需要用并查集优化。 ...从描述中看出,非前缀且权值和最小,于是我想到了哈夫曼编码。类似的,对于这道题,我们可以考虑建立一个k叉树,这个树的每个叶节点代表一个字符串,只须找出最小的n个叶节点的权值... 这道题的解决方法隐藏得很深,不经过严密的数学推理分析是很难想到正确方法的。 注意到题上的一个看似无关紧要的条件,“不包括三角形”,这是一个突破口。由这个条件,我们可... 二维费用01背包问题,动态规划,但是要注意边界条件。 状态设定 F[i,j,k] 前i个瓶,氧为j,氮为k的最小重量 状态转移方程 F[i,j,k]=Min 这是合并等价类问题,由于每个未知量有多位,每位对应0或1,我们先把字母串按照展开拆开。例如样例可以展开成 1,b1,b2,a1,a2,a3,a4,d1,d2,d3,d4, 1 对于...
|
|||||
|
Copyright © 2010 Beyond the Void - All Rights Reserved
|
|||||