Beyond the Void

NOI2001的题目是[反正切函数的应用][聪明的打字员][陨石的秘密][食物链][炮兵阵地][方程的解数]。

其中[反正切函数的应用][聪明的打字员]较为简单，[陨石的秘密][食物链][炮兵阵地][方程的解数]稍有难度。

[反正切函数的应用]是一个求函数最值的问题，要配合数学知识解决。[聪明的打字员]是广度优先搜索问题。[陨石的秘密]是一个树形动态规划的问题，需要仔细思考。[食物链]用到了并差集。[  炮兵阵地]是个不易看出的动态规划问题。[方程的解数]是搜索问题，需要用哈希表来优化。

Read the rest of this entry »

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

==1002==
首先把单词按照规则替换为数字序列，构图，把电话号码的每一位作为一个顶点。增加一个0号顶点。

如果一个单词的数字序列能够匹配电话号码的A到B位，那么我们就在第A-1个顶点和第B+1个顶点上连接一条边，记录形成该边的单词。

求从0号顶点到N号顶点的最短路径，由于是无权图，直接宽搜即可。找到一条从0到N的最短路径，按照最短路径上的边对应的单词输出。

==1005==
动态规划，
F[i,j]为前i个石头分为两堆，重量差值为j的状态是否存在

F[i,j]= or
*{
**F[i-1,j-W[i]] (j-W[i]>=0) 两堆差值扩大
**F[i-1,W[i]+j] (W[i]+j< =MAX) 两堆差值减少但不超越
**F[i-1,W[i]-j] (W[i]-j>=0) 较少一堆超越较多一堆
*}

目标结果就是
Ans=i (F[N,i]=true 且 i最小)

==1018==
明显的树形动态规划。首先是建立二叉树，由于上下不确定，我是先以邻接矩阵的方式读取了二叉树，然后以O(N^2)从1号节点开始遍历建立了二叉树。

状态设定
F[i,j]为 在以节点i为根的子树中，保留数量为j的树枝时，留下的最大的苹果数量。
i.left表示i的左子树，i.right表示i的右子树，
i.lv表示i连接左子树的边的权值，i.rv表示i连接右子树的边的权值

状态转移方程
F[i,j]=Max
{
F[i.left,j-1] + i.lv
F[i.right,j-1] + i.rv
F[i.left,k] + F[i.right.j-k-2] + i.lv + i.rv (k=0..j-2)
}

边界条件
F[i,0]=0;

目标解
Ans=F[N,Q]

==1021==

哈希或二分查找。由于数据范围不大，仅仅在2字节整型范围内，我用的是哈希。

由于C++开下标为负的数组还要指针运算，不太方便，我把读入的每一个数都加上了40000。

读入第一组数的时候，每个数a增加40000，设定Hash[a]=true。
读入第二组数，对于每个数a增加40000，如果Hash[90000-a]，则有可以配对的，输出YES。
如果找不到配对的，输出NO。

==1023==
博弈论，数学问题。

首先，假如我们一共有L+1个Button，那么先取者无论怎么取都会输。相似的，假如我们有q*(L+1)个扣子(q是正整数)，则先取者是必败的，也就是后取着是必胜的。

所以对这道题给定的K个Button，我们只需枚举最小的L(2< =L<=K)，使得K能整除(L+1)，后取着一定是必胜的。不存在没有必胜策略！

==1029==
动态规划或者最短路径。

看到这道题我马上就想到了最短路径，但是为了练习动态规划，我还是写了动态规划。

最短路径的方法：

首先把每个房间看成一个顶点，另外建立两个顶点，分表表示起始点和目标点。按照题中所给的三个规则，在顶点之间建立有向边，有向边(a,b)边权为b房间的费用。连接起始点和第一层楼所有顶点，以及顶层楼所有顶点和目标点。求从起始点到目标点的一条最短路径，最后输出路径上的每个点的位置。可能超时，注意优化。推荐使用SPFA算法。

动态规划的方法：

状态设定
F[i,j]表示到达第i层第j个官员的最小费用。

状态转移方程
F[i,j]=Min
{
F[i-1,j]
F[i,j-1]
F[i,j+1]
} + Cost[i,j]

边界条件
F[1,i]=Cost[1,i]

目标结果
Min{F[N,i]} 从第一层到(N,i)点的路径就是结果。

在状态转移的过程中，对于每层要正向和逆向各扫描一边，分别处理F[i,j-1]和F[i,j+1]，避免后效性。

注意，题上给的数据范围是不对的，我按M最大为100提交时，一直在第6组数据出错，改成和N一样最大为500就过了。

以下是程序
Read the rest of this entry »

Read the rest of this entry »

常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。

常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。

其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。

经过比较，得出以上平均得分。平均数为平方平均数。可以发现，BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算法本质是相似的。

在信息修竞赛中，要本着易于编码调试的原则，个人认为BKDRHash是最适合记忆和使用的。

BYVoid原创，欢迎建议、交流、批评和指正。

附：各种哈希函数的C语言程序代码
Read the rest of this entry »