Beyond the Void

我的计划就从NOI1997开始。NOI1997一共有6道题，分别是[卫星覆盖][积木游戏][竞赛排名][最佳游览][最优乘车][文件匹配]。这一年的6个题难易分布均衡，做完后收获不小。

其中[竞赛排名]和[最佳游览]是两个最简单的题，但是往往细节是容易忽视的。[积木游戏]和[最优乘车]难度属于中等，分别是动态规划和构造最短路径解题。[卫星覆盖]和[文件匹配]属于较难题，用到了[卫星覆盖]离散化或者立体切割的方法，而[文件匹配]是搜索中的难题，需要很多的优化。

做这些题我花了4天的时间，进度还算正常，希望能继续保持下去。今后做题的宗旨是“不求多，不求快，但求精”。

Read the rest of this entry »

动态规划，设F[i,j]为范围1..i的集合元素之和大于等于j，不含连续自然数的集合个数

由于可能存在空集的情况，即计算过程中出现了k=-1，这是很不方便的，所以我修改了定义，把大于k方便的改成了大于等于k＋1。N=100，K=400时，结果是很大的，要使用高精度。

状态转移方程

F[i,j]= Sum
{
F[i-1,j], (包含第i个元素)
F[i-2,j-i] (不包含第i个元素，j-i若小于0则为F[i-2,0])
}

边界条件

F[1,0]=2 //Ø,{1}
F[1,1]=1 //{1}
F[2,0]=3 //Ø,{1},{2}
F[2,1]=2 //{1},{2}
F[2,2]=1 //{2}

目标结果

F[N,K+1]

Read the rest of this entry »

标准的广度优先搜索，哈希判重。由于无法估计状态数，需要用链队列存储搜索状态。把初始状态加入队列，然后取出队列中的首元素，对其状态进行扩展。判断不能有重复，否则是多余的。如果当前扩展到的状态三种钱币的数目都大于等于目标状态，则找到了解，输出交易的次数。另外，为防止重复按照某些规则交易使钱币数目无意义地增长，人为规定每种钱币的数目不能超过目标状态的若干倍（比如10倍即可）。
Read the rest of this entry »

O(N^3)的枚举是无法忍受的，这道题可以从反面考虑。单色三角形的个数就是全部的三角形的个数减去不同色三角形的个数。

在一个不同色的三角形中，显然有两个顶点，每个顶点连着这个三角形内的不同颜色的两条边。一个顶点出发有N-1条边，如果顶点i连接着D[i]条红边，那么它一定连接着(N-1-D[i])条黑边，这个顶点在D[i]*(N-1-D[i])个不同色三角形内。而一个顶点在一个三角形内被计算了两次，所以整个图中一共有
Sum{ D[i]*(N-1-D[i])/2 | i=1..N }个不同色三角形。

由于一共有C(N,3)个三角形，所以结果就是

C(N,3) – Sum{ D[i]*(N-1-D[i])/2 | i=1..N }
Read the rest of this entry »

提供一个没有优化的O(N^2)的动态规划解法。首先对所有的演讲时间区间按结束时间从小到大排序，然后设定状态。

S[i].l和S[i].r分别表示第i个演讲的开始和结束时间。
F[i]为进行第i个演讲时已经使用了的最大的时间

状态转移方程
F[i] = Max{ F[j] | S[j].r < =S[i].l } + S[i].r - S[i].l

结果
Max { F[i] }

Read the rest of this entry »