由于题目的版权问题, 这里并不会出现题目描述, 请通过其他渠道获取题目描述.

合唱队 Chorus

很容易的区间DP, 设 分别表示当前状态为区间 , 最后一个放的元素在区间的左侧和右侧的方案数. 时间复杂度 .

平面图判定 Planar

判定存在 Hamilton 回路的平面图, 实际上就是判定能否把区间(边)分成两个集合, 使得每个集合内的元素互不相交(但可以严格包含).

这道题其实是有 的解法的, 但是这道题的点数过少, 也有很方便的解法. 根据欧拉定理, 平面图的边数 和点数 满足 . 那我们可以把边数的规模降低, 然后可以用 的染色解决此题.

物品调度 Fsk

假设我们已经知道了终止状态, 如何求得最小步数呢. 我们可以用 的时间求出这个置换的每个循环. 对于每个长度大于1的循环, 若其中含有0元素, 那么最少需 步, 否则需要 步.

现在的问题是如何求出终止状态, 观察题意发现, 每个元素的终止状态是放在 之后第一个非空的模 剩余系中, 并且放在这个模 剩余系中当前位置的下一个可行位置, 因此我们可以用链表/平衡树维护每个模 剩余系的情况以及每个模 剩余系内部的情况. 可以做到 的复杂度.

公交线路 Bus

我们可以用每辆车到一个点的距离集合来表示一个状态, 由于不能有空位以及车之间没有区别, 实际状态集合的最多只有 个之少.

我们可以用矩阵乘法来优化转移, 复杂度最多为 .

取石子游戏 Stone

解法未知.

城市建设 City

解法未知.

弹飞绵羊 Bounce

首先这道题只能往后跳, 所以我们用块状链表维护每个点在块内和块外的情况即可用 的时间解决此题.

正解之一是利用括号序列, 每次操作都是把一棵子树砍下并且接在某个结点上, 那么我们可以维护括号序列整段移动来完成这个操作. 同时为了回答询问我们需要知道每个左括号的左边有几个未匹配的左括号, Splay 可以维护这个值, 时间复杂度 .

矩阵 Matrix

设给定的矩阵是 , 原矩阵是 , 另设 矩阵, 其中:

的第一行和第一列均是0, 且 .

同时满足 . 证明在此(外链打开请谨慎).

那么我们搜索 的第一行, 在枚举 时检查第 列并更新第一列的可行集合来剪枝. 这样就可以通过这道题了.

看到Terence 老师在他的博客上写过一篇文章, “Does one have to be a genius to do maths”, Zhiqiang 老师评论说“他写这种文章是站着说话不腰疼.”

的确, 对于Terence老师这种12岁就获得国际数奥金牌的人来说, 天赋毫无疑问是他走向成功的一个因素. 但是, Terence老师下面这段话却发人深省:

In some cases, an abundance of raw talent may end up (somewhat perversely) to actually be harmful for one’s long-term mathematical development; if solutions to problems come too easily, for instance, one may not put as much energy into working hard, asking dumb questions, or increasing one’s range, and thus may eventually cause one’s skills to stagnate. Also, if one is accustomed to easy success, one may not develop the patience necessary to deal with truly difficult problems. Talent is important, of course; but how one develops and nurtures it is even more so.

对应的译文: (来自LiuXiaochuan老师)

有的时候，大量的灵感和才智反而对长期的数学发展有害，试想如果在早期问题解决的太容易，一个人可能就不会刻苦努力，不会问一些“傻”的问题，不会尝试去扩展自己的领域，这样迟早造成灵感的枯竭。而且，如果一个人习惯了不大费时费力的小聪明，他就不能拥有解决真正困难的大问题所需要耐心，和坚韧的性格。聪明才智自然重要，但是如何发展和培养显然更加的重要。

反过来想自己, 即使在创新能力要求极强的信息学中, 原来最重要的不是自己的那些灵光一闪的新点子, 而是严谨踏实的学术作风.

以下是我的NOIp 2009 (提高组) 解题报告.

第一题(潜伏者, spy): 略.

第二题(Hankson 的趣味题, son):

Gcd(x,a0)=a1, Gcd(x,b0)=xb0/b1

设f(a,b) 代表b这个质因子在a中有多少个.

对于a0的任意质因子t, 若f(a0,t)=f(a1,t) 则只需保证f(x,t)≥f(a1,t), 否则f(x,t)=f(a1,t)

对于b1的任意质因子t, 若f(b1,t)=f(b0,t) 则只需保证0≤f(x,t)≤f(b1,t), 否则f(x,t)=f(b1,t)

由于x的所有因子都是b1的子集, 所以我们只需对b1的质因子按如上方法逐个检查这个质因子在x里面的取值范围(若为空则说明无解), 并按照乘法原理统计即可.

关于分解质因子: 由于b1不会超过2*10^9, 大于50000的质因子不会超过1个, 所以我们只要打出50000以内的素数表即可, 若最后除剩的b1仍未除尽, 说明此时b1一定是一个大于50000的素数.

第三题(最优贸易, trade):

做法1:

设Low[i]为从1到i当前所有路径中最便宜的价格. Profit[i]为从1到i当前所有路径中最大获利. 初始时Low[1]=P[1], Low[2..n]=infinity, Profit[1..n]=0.

那么我们可以从1开始广搜, 要注意一个点有可能多次被更新.

从i可以更新到j的条件是:

1. 存在有向/无向边(i,j)

2. Low[j]>Low[i] 或 Profit[j]<Profit[i]

做法2:

首先考虑没有环的情况, 此时1,n之间要么无法连通, 要么只存在一些单向的无环路径. 对于每一条路径, 由于不能”回头”, 走到某个点i的极优获利显然是i的费用-路径上此点之前的点的最小费用, 而此路径的最大获利便是取获利最大的点.

但是还有很多数据是有环的, 也就是对于有些点对(a,b), 在a走到b之后, b仍然可以走回到a. 在图论中, 我们把点集V, 其中任意两个点可以互达, 叫做强连通分量.

由于强连通分量中的点可以互相到达, 所以在一个强连通中的最大获利就是强连通中最贵的-最便宜的. 我们把所有强连通分量求出来缩为两个点之后. 1与n之间只存在一些无环路径, 对于这些单向的无环路径我们只需要扫描一遍便可求出最大获利.

强连通缩为两个点的具体做法: 把一个强连通缩为a,b 两个点, 连(a,b)边, a的费用为强连通中最便宜的, b的费用为强连通中最贵的. 把指向强连通中任何一个点的所有边改为指向a, 把强连通中任何一点指向强连通外部的边改为由b指出. 这样构出来的保证与原图等价.

第四题(靶形数独, sudoku): 很直白的搜索, 由于数独是NP-H问题, 所以我们肯定只能用搜索, 那么关键就在于剪枝了, 我们发现, 对于每个格子都有一个取值范围, 这个范围由其横行/纵行/小九宫格中已填的数决定, 那么无疑我们每次搜索选取值范围最小的格子搜是比较优的.

大家都知道正常的Nim游戏是取完最后一个赢. 必胜态是各堆石子异或值不为0. 现在来看看几个有意思的变种.

变种1: 取到最后一个石子的人输.
首先明确奇数个1是必败态, 偶数个1是必胜态. 这与正常的Nim不一致.
若只有一堆的个数大于1, 那么现在可以控制全场的1个数的奇偶性, 所以是必胜的. 这与正常的Nim一致.
若不止一堆的个数大于1, 由于不能转移到全是1的状态, (可能可以转移到仅有一堆大于1的状态, 但此状态与正常Nim一致), 所有当前可以转移到的状态的胜负性都是与正常的Nim一致的, 所以当前状态的胜负性与正常的Nim也是一致的.
综上, 除了全是1的状态胜负性跟正常的Nim不一致, 其余的状态胜负性与正常的Nim一致.

变种2: 只能从最左或最右的一堆中取, 取到最后一个的赢.
对于 [L,X,R] 状态, 若其是必败状态, 那么|L-R|<=1.
证明: 设[L,X,R]是必败态且R<L-1, 那么, 对于任何的1<=L’<L, [L',X,R]是必胜态. 那么对于每个L’, 都存在R’<R使得[L',X,R']是必败态, 显然不会出现[a,X,b]和[a',X,b]同为必败态的情况, 但L’有L-1个取值, R’却没有L-1个取值, 所以对于任意必败态[L,X,R], 都有|L-R|1则是必胜态, 否则, 由[X]的胜负性以及L-R的值可以推导出[L,X,R]的胜负性.

假如Alice和Bob需要经过一个不可靠媒介传送一条消息, 他们大概会把这条消息加密, 而普遍使用的字母移位法(凯撒加密法)太容易被破解, 所以他们可能会考虑使用更加安全的加密法.

在上个世纪70年代被麻省理工学院的三位教授发明的RSA加密算法就是一个足够安全的加密法, 当今互联网的SSL安全连接协议的重要加密算法就包括了RSA加密算法. 连接到你的网上银行, 查看这个安全连接的证书, 证书上很可能写的就是“RSA加密”.

当然, RSA被广泛使用的原因还有一个, 那就是它的加密钥匙是公开的, 也就是说, 任何人都可以使用公开的密钥给消息加密, 却无法给刚加密的消息解密.

Read more…

网络流是图论中相当重要的一部分，也是计算机科学中比较难掌握的一类知识，在这我就给各位讲一讲网络流的有关知识。要注意的是，网络上，包括很多书籍中关于网络流的名词很容易被理解错，为了方便大家理解，我在这里对很多名词作了详尽解释。

Read more…

冬令营17日

首先说一下，今天的内容是我目前为止的收获最大的，因为今天的内容很多都涉及到了数学，还有就是晚上论文答辩的时候，吴文虎教授特别提到了一些有关信息学前景以及有关我们学习信息学的目的的问题，吴教授的发言我应该会在冬令营录像发下来之后录进电脑。

上午

内容: 信息学竞赛中的数学建模初探

授课: 李学武, TGC

李学武教授我仰慕很久了，因为李教授在数学理论方面建树颇丰，很有研究。今天听他的讲课更是深有感触。其实学信息学，数学是最重要而且密不可分的模块，不，不是模块，信息学就是数学的一部分，信息学研究的用强大的计算速度解决数学问题，其中有求解的，也有证明的，关于机器证明的那一部分，今年的集训队论文有人提到了，还不够彻底，我记得有一套书叫做《好玩的数学》中有一章就是讲的机器证明，很经典。这部分我以后再谈。

李教授讲的就是有一本数学名著《具体数学》中的一些经典问题，这里我提一下比较重要的部分。

递推关系与求和: 引入是 Josephus (约瑟夫)问题，我们已经知道，关于约瑟夫问题，有模拟的方法可解，但是，有没有更好的方法呢？答案是肯定的，我们观察每次报数出圈，有当前为偶数号的一部分人出圈，接下来，又是新一轮的报数出圈，而且有一部分人成了新的偶数号，我们不难发现，整个出圈的过程，就是一个递归的过程，好，那么我们定义 J(n) 为在有 n 个人的圈上，最后剩下来的人是几号。易得出如下三个递归定义的表达式：

(1)    J(1)=1

(2)    J(2n)=2J(n)-1

(3)    J(2n+1)=2J(n)+1

其中 n 为正整数。

然后我们易得出一个闭形式 (closed form) 的表达式: J(2^m +l)=2l+1.

我们来看一下能不能再化简，我们把 n 化为一个 m 位二进制数，第一位为 B1，最后一位为 Bm，那么我们从那个闭形式表达式惊异地发现，每一次 J(n) 操作，只是把 n 这个二进制数的第一非零位 B1 ，移到 Bm 之后！多么神奇的性质啊！（原因请自己推导）那么，在进行多次 J(n) 操作之后，在进行 J(n) 操作值就会不变了，原因是 n 的所有二进制位都变成 1 了，我们把这样的值叫做“不动点”，这个概念在复合函数中经常提到。多次调用这个函数，不动点会出现在原 n 二进制数中 1 的个数 k 次以下（因为尾部可能有连续的 1），而不动点的值就是 2^(k+1)-1.

我们再把刚刚那些递归定义的式子拓展一下：

(1)    f(1)=α

(2)    f(2n)=2f(n)+β

(3)    f(2n+1)=2f(n)+γ

我们再来尝试用闭形式来描述这些递推式。

观察后知，我们把这个函数写成 f(n)= A(n)α+B(n)β+C(n)γ.

我们列表发现，A(n)事实上是等于 trunc(log n), 而 B(n) 呢，则在 A(n) 不变的周期中随着 n 的增加而从 A(n)-1 递减到 0, C(n) 则恰好相反，在 A(n) 不变的周期中随着 n 的增加而从 0 递增到 A(n)-1. 这些结论，事实上可以由归纳法证明。

接下来，李教授讲了一些关于 sigma 式的化简，由于过于简单，我在这里就不再叙述了。但是李教授提出的思想却是相当好的：

递归<–>求和

  |      |

  >闭形式<

在有诸多表达式形式的情况下，我们要熟练掌握表达式的转化，这样我们才能高效地分析问题，从而解决问题。但这又需要我们有相当扎实的数学理论功底，以前对于名言“数学是无穷的科学”的理解一直停留在“数学题是做不完”的层面(哈哈！)，而我们现在发现，数学的代数变换，几何变换，以及数形结合还有最新的机器解题（信息学）等方面的探索是无穷无尽的，数学是最基础的自然科学，它的发展推动着整个科学界的发展。

下午是 TSU 的周源同学讲随机化算法，由于牵扯到很多概率的知识，我留到以后再讲；晚上答辩时吴文虎教授的讲话，我准备单独地写一篇文章，就不在这里写了。