07年NOIp模拟赛by Matrix67 解题报告

2007 年 10 月 8 日 / 14 条评论

Problem 1: Matrix67的情书（二）
    大家都知道，看一个数是否能被2整除只需要看它的个位能否被2整除即可。可是你想过为什么吗？这是因为10能被2整除，因此一个数10a+b能被2整除当且仅当b能被2整除。大家也知道，看一个数能否被3整除只需要看各位数之和是否能被3整除。这又是为什么呢？答案或多或少有些类似：因为10^n-1总能被3整除。2345可以写成2*(999+1) + 3*(99+1) + 4*(9+1) + 5，展开就是2*999+3*99+4*9 + 2+3+4+5。前面带了数字9的项肯定都能被3整除了，于是要看2345能否被3整除就只需要看2+3+4+5能否被3整除了。当然，这种技巧只能在10进制下使用，不过类似的结论可以推广到任意进制。
    注意到36是4的整数倍，而ZZZ…ZZ除以7总是得555…55。也就是说，判断一个36进制数能否被4整除只需要看它的个位，而一个36进制数能被7整除当且仅当各位数之和能被7整除。如果一个数同时能被4和7整除，那么这个数就一定能被28整除。于是问题转化为，有多少个连续句子满足各位数字和是7的倍数，同时最后一个数是4的倍数。这样，我们得到了一个O(n)的算法：用P[i]表示前若干个句子除以7的余数为i有多少种情况，扫描整篇文章并不断更新P数组。当某句话的最后一个字能被4整除时，假设以这句话结尾的前缀和除以7余x，则将此时P[x]的值累加到最后的输出结果中（两个前缀的数字和除以7余数相同，则较长的前缀多出来的部分一定整除7）。
    上述算法是我出这道题的本意，但比赛后我见到了其它各种各样新奇的算法。比如有人注意到36^n mod 28总是等于8，利用这个性质也可以构造出类似的线性算法来。还有人用动态规划（或者说递推）完美地解决了这个问题。我们用f[i,j]表示以句子i结束，除以28余数为j的文本片段有多少个；处理下一句话时我们需要对每一个不同的j进行一次扫描，把f[i-1,j]加进对应的f[i,j']中。最后输出所有的f[i,0]的总和即可。这个动态规划可以用滚动数组，因此它的空间同前面的算法一样也是常数的。
    如果你完全不知道我在说什么，你可以看看和进位制、同余相关的文章。另外，我之前还曾出过一道很类似的题(VOJ1090)，你可以对比着看一看。
    另外，非常抱歉地告诉大家，这道题的最后一个数据是错的。这个数据的第一个句子是一个空句子（感谢Ai.Freedom的提醒）。很多第一题只得了90分的好同志估计都是由于我的失误造成的，这里再次表示歉意。如果去掉最前面的那个问号，输出应该是19511110。

Problem 2: 送给MM的生日礼物

我们用f[i,j,k]表示以第i行第j列的格子为右下角，边长为k的正方形是否符合要求。要想f[i,j,k]=True，首先必须满足f[i-1,j-1,k-2]为True（灰色部分满足要求）。另外，我们还需要保证图中两块蓝色区域相等，两块绿色区域相等，并且这四个区域自身还必须是对称的。由于动态规划的状态已经是三方的了，因此判断后面的这些条件必须在常数时间里完成。为此，我们可以在动态规划前进行以下6个预处理：

以同列不同行的两个格子(i,j)和(i',j)为右端点，同时向左扩展可以得到多长的相等区域
以同行不同列的两个格子(i,j)和(i,j')为最底端，同时向上扩展可以得到多长的相等区域
以格子(i,j)为中心，向左右扩展可以得到多长的对称区域
以格子(i,j)为中心，向上下扩展可以得到多长的对称区域
以两个横向相邻的格子(i,j-1)和(i,j)为中心，向左右扩展可以得到多长的对称区域
以两个纵向相邻的格子(i-1,j)和(i,j)为中心，向上下扩展可以得到多长的对称区域

上面的每个预处理都可以在三方的时间里完成，动态规划的决策降到常数级别，因此总的复杂度还是三方。

    同样地，这也只是我出这道题的本意。我事先已经想到，这道题应该还有很多其它的算法，只是没想到会有那么多。一个比较容易想到的算法是，执行与上面相同的预处理后，枚举某个格子（或某个交叉点）为中心，向外一层一层地进行扩展。虽然这样的复杂度仍然是三方的，并且与前面的算法实质相同，但它的效率显然更高，因为你可以在无法再向外扩展时停止最里面的那个循环，继续枚举下一个中心点。
    同样是枚举正方形的中心点，只使用上面的后4个预处理也可以解决这个问题。我们可以在线性的时间内找出，以某个格子（或交叉点）为中心的最大的合法正方形。假如这个最大的正方形边长为k，这相当于我们同时找到了(k+1) div 2个正方形来。至于如何找到这个最大的正方形，还是留给大家思考吧。
    Cockhorse想到了一个非常巧妙的算法，预处理结束后它可以在常数时间内判断任一个给定的小正方形是否满足题目要求。用f[i,j,k]表示，以第i行中(i,j)及其右边相邻的k-1个格子（共k个格子）来作为底边，所能得到的左右对称的矩形其最大高度是多少。则当f[i,j+1,k-2]为True且(i,j)格与(i,j+k-1)格花色相等时f[i,j,k]=f[i-1,j,k]+1（否则f[i,j,k]=0）。同样地，再用g[i,j,k]表示以(j,i)..(j+k-1,i)作为右边界，使矩形上下对称的最大宽度。这样，判断任意一个正方形是否满足题目要求，只需要检查它的底边和右边能够产生的最大对称区域是否可以覆盖该正方形即可。
    当然，这道题目还有很多其它的算法，这里就不一一列举了。

Problem 3: 流言的传播
    给定一个图，把图中所有点构成的点集叫做U，另指定一个不等于全集的子集S，那么所有一个顶点在S里另一个顶点在U-S里的边就叫做S点集的“割边”，因为去掉所有这样的边后S集将孤立出来。这道题就是需要你找出一个边集E，使得不管S集是什么，对应的割边中权值最小的那一条一定在边集E中。这样的边集肯定是存在的，比如所有边构成的集合就是一个满足条件的边集。这道题希望你找到的边集E里所含的边尽可能的少。
    一个错误的贪心法是，去掉每个点的邻接边中权值最小的那一条。这种算法显然不对，比如下面就是一个鲜活的反例：

o—–o—–o—–o
   2     3     1

    在上图中，每个点的邻接边中权值最小的不是1就是2，这样的话中间那条边就被保留了下来，于是令S集为左边两个点（或右边两个点），割边仍然一条不少。很容易想到，要想让任意S集的割边中权值最小的被去掉，首先得保证边集E连通了所有的点，否则令S等于任一连通分量，边集E里都不会包含任何一条割边。这样，边集E至少要有n-1条边。
&n
bsp;   考虑到最优解至少是n-1条边，这n-1条边必须连通所有的点，而所选边的权值都应该很小，于是想到最后的答案很可能就是最小生成树。现在假设我们已经选择了某些边，这些边形成了若干个连通分量。考虑所有连接两个不同的连通分量的边（两顶点不在同一连通分量的边）中权值最小的一条，那这条边必须要选，否则令S集为其中一个连通分量，题目条件就不能达到了。这不就是Kruskal算法吗？
    且慢，我们还没有证明，对任意一个S集，最小生成树都符合条件。证明其实很简单，假设权值最小的割边e不在最小生成树E中，添加割边e将形成一个回路。这条回路将从S集的某个点出发，经过e跑到U-S里，最后必须还要回到S集。回到S集必然要经过另一条割边e'，而显然e'>e（因为e是权值最小的割边，且题目说了没有权值相同的边），于是边集E+{e}-{e'}就成了更小的生成树。

Problem 4: 表白机器人
    第四题是整个模拟赛中最简单的题，它不需要你构造任何算法，你只需要按照题目意思进行模拟即可。和去年的NOIp一样，纯粹考编程能力的题目并没有放在第一道题的位置上。这提示大家拿到题目后要先看完所有的题，特别是看到最后一道题时千万别慌，很可能把它的衣服扒光了一看，发现它居然是一道赤裸裸的送分题。
    为了加快速度，先预处理出一个数组wall[i][j][k]，表示第i行第j列往k(1<=k<=4)方向上走是否走得通。然后枚举所有可能的命令序列，模拟机器人的行走过程，看它是否能到达终点。在模拟过程中，你需要用一个数组hash[i][j][k]表示机器人曾在序列的第k个命令后到达第i行第j列的位置，并在模拟过程中不断更新hash数组；当某一次命令后机器人还没走到右上角，而对应的hash值已经为True了，则机器人的行动将从这里开始循环，永远也到不了右上角了。
    虽然这道题不需要任何剪枝，但我还想再说一句。这道题有一个非常有趣的剪枝：命令序列的第一个指令只能是U或R，最后一个指令也只能是U或R。大家想想这是为什么。

Matrix67生日邀请赛完全题解发布

2007 年 5 月 15 日 / 4 条评论

题目在这里：http://www.matrix67.com/blog/article.asp?id=241

如果机房马上要关门了，或者你急着要和MM约会，请看简要题解：

1. 用类似于传统hanoi的递归方法可以做到3^n-1次。这显然是最多的了，因为总的状态数也只有3^n个。
2. 可以证明，竞赛图中不存在环当且仅当所有顶点的出度从小到大排列依次为0, 1, 2, … , n-1 。
3. 在最短路树上做树状DP，需要多叉转二叉。注意几种需要输出0的情况。
4. 搜索，算是练基本功了。用位运算优化，不加任何剪枝就能过。

否则，请慢慢阅读——

Problem 1: 为什么最少
    如果你还不熟悉Hanoi塔的解法，去题目中提到的那篇日志看看吧。如果你已经熟悉Hanoi塔的解法，你会立刻想到这道题的解法：依然是递归地解决。至于怎么递归，样例已经告诉我们了：把前n-1个金片从1号柱搬到3号柱，把第n片移到2号柱，又把那n-1片从3号柱搬回1号柱，再把第n片搬到3号柱，最后把那n-1个金片又搬过来，完成整个操作。
    我们下面解决三个问题：为什么这样不会重复出现状态，这样的移动步数是多少，为什么这样的操作步数是最多的。
    为什么这样不会出现重复的状态呢？因为我们假设前n-1个金片的移动过程中没有重复状态，而三次对n-1的调用时整个状态由于第n个金片的位置不同而不同。
    这样的方法获得的操作步数是多少呢？答案是3^n-1。我们可以用数学归纳法证明，n=1时步数为2显然正确，而f(n+1)=3f(n)+2=3*(3^n-1)+2=3^(n+1)-1。
    为什么这样的操作步数是最多的呢？废话，这样的操作步数当然是最多的，因为总的状态数也只有3^n个（每个金片的三种可能的位置确定了一种状态），你的移动步骤能比这个数目还多就见鬼了。

这道题有人用了math库，没有提供math库导致无法编译是我的失误，向大家道歉。

Hanoi问题的变种太多了，比如多根柱子、单向移动、双色金片等等。dd上次不是也出了一题么。

这题代码很短，我公布在下面。
program whyleast;


procedure solve(t,a,b:integer);
begin
   if t=0 then exit else
   begin
      solve(t-1,a,b);
      writeln(a,' ',2);
      solve(t-1,b,a);
      writeln(2,' ',b);
      solve(t-1,a,b);
   end;
end;

{====main====} var n,i:integer; ans:longint=1; begin assign(input,'whyleast.in'); reset(input); assign(output,'whyleast.out'); rewrite(output); readln(n); for i:=1 to n do ans:=ans*3; writeln(ans-1); solve(n,1,3); close(input); close(output); end.

Problem 2: 身高控制计划
    一个竞赛图是指任两个点之间都有一条有向边的图。竞赛图有很多奇妙的性质，比如一个竞赛图必然存在一条经过所有节点的路等等。
    下面我们证明，竞赛图中不存在环当且仅当所有顶点的出度从小到大排列依次为0, 1, 2, … , n-1 ：
    如果一个有向图的所有点出度都至少为1，那么这个图一定有环，因为在找到环之前DFS总可以找到新的节点。如果有向图无环，必然存在一个点没有出度。由于任两点之间都有有向边，那么其它所有点都要连一条边指向它，这样其它所有点的出度都至少为1了。删掉这个出度为0的点后剩下的图仍然无环，不断对剩下的图继续上面的过程就得到了我们的结论。
    现在我们的算法就很明确了，首先统计初始状态下的出度，然后设计某种数据结构完成两种操作：改变一个数（加一减一），询问所有数是否恰好为0, 1, 2, … , n-1 。
    统计初始状态下的出度方法有很多，这里介绍两个。首先对身高排序，然后对于每个人进行二分，寻找有序数列中该数的4/5和5/4各在什么地方。还有一种方法也是先排序，然后从左到右扫描整个序列，并保持两个指针始终指向4/5和5/4处。每次开始处理一个新的数时都把两个指针适当地右移直到超出了这个数的4/5或5/4为止。两种方法都是O(nlogn)。别以为第二种方法是线性的哦，线性算法之前还有一个排序呢。
    操作的处理也有不少方法。最简单的方法就是统计当前图中出度的数目有多少种。就是说，用a[i]表示出度为i的点有多少个，然后不断更新a[i]>0的有多少个。当这个数目等于n时我们就认为图中没有环（因为出度可能的取值只有从0到n-1共n种）。
    注意，由于同一条边可能被操作多次，因此需要一个Hash表（开散列）来判重。具体地说，你需要判断这条边以前被操作过奇数次还是偶数次，以决定哪边的出度要增加，哪边的出度要减小。

Problem 3: 狼的复仇

    把这个问题中所有的最短路都画出来是什么样子？它一定是一棵树！为什么？首先，图肯定是连通的，因为源点到任一个点都有一条最短路；其次，图肯定无环，因为源点到任一个点只有一条最短路（环的出现将意味着某些点有更短的路存在）。仔细想一下Dijkstra的算法过程，不难想到Dijkstra算法的实质就是在建这棵树——每一次由x节点加上边x-y扩展到y节点就记作x是y的父亲。注意观察上图中左图是如何变成右图的。这样，题目变成了这种形式：在有根树上，除根节点之外的其它节点中选择一些节点，使得这些节点和它们所有祖先的权值和最大。这是一个经典的树型动态规划模型。我们用f[i,j]表示以节点i为根节点的子树花费j个单位的材料最多可以得到多大的攻击力。令节点1的材料和攻击力都为0，那么最后输出f[1,0..k]中的最大值即可。决策分为两类，要么该位置建一个塔，要么把所有材料适当地分给儿子（自己就不需要再建了）。但这样的复杂度太高，我们需要用DP嵌套或者更巧妙的多叉转二叉来解决。
    DP嵌套理解起来更简单，它主要是解决这样一个子问题：若某个节点有m个儿子，我们需要寻找当j1+j2+…+jm等于某个定值时f[儿子1,j1]+f[儿子2,j2]+…+f[儿子m,jm]的最大值。这个子问题与我的某次模拟赛中论文课题选择那道DP题几乎是一模一样，看一看那道题就明白了。下面简单描述多叉转二叉的方法。

    如果你还不知道多叉转二叉的话，这道题是一个绝好的学习材料。一棵多叉树可以用“左儿子右兄弟”的方法转为二叉树，具体的说就是把多叉树转化为这种形式：节点的左儿子才是真正的儿子，节点的右儿子只是和它同辈的兄弟。注意看上图的左图是如何变成右图的。现在，我们的f[i,j]表示

非传统题型练习：三道交互式题目

2007 年 3 月 9 日 / 3 条评论

Problem 1: famous 谁是名人
题目来源：Matrix67根据经典问题改编

题目和测试库源码直接见http://www.matrix67.com/blog/article.asp?id=179

题解：
显然名人最多有一个。问两个还没有问过的人A和B。如果A认识B，那么A肯定不是名人；如果A不认识B，那么B肯定不是名人。总之，结果无论是什么，总有一个人要排除。由于题目说了一定有名人，那么只需要询问n-1次，每次排除一个人，剩下的肯定就是名人了。

Problem 2: meandian 中等工资
题目来源：CEOI 2006 有细节改动 (Translated by Matrix67)

问题描述
    一些公司不愿意透露员工的工资，这样可以防止工会的领导者知道员工的报酬有多低，从而避免烦人的涨工资的谈判。不过，有时公司很乐意为统计和市场目的透露一些消息。
    其中一个公司愿意回答的问题是这样的形式：“员工A、B、C、D的中等工资是多少”。四个数的“中等值”定义为中间的两个值的算术平均数。更明确的，a,b,c,d的中等值按这样的方式得到：首先对这四个数排序，然后计算排序后的第二个数x和第三个数y的平均数(x+y)/2。你的目标是通过询问一些这种形式的问题来得到员工具体的工资数。注意有一些员工的工资有可能永远不能推出（比如工资最低的那个人）即使所有可能的问题都被问过。
    该公司有N(4<=N<=100)名员工，分别用1到N标记。每个员工的工资是一个小于等于100 000的正偶数，且没有两个员工的工资相同。
    你将得到一个实现中等值的询问的库。给出四个不同的整数A,B,C,D (1<=A,B,C,D<=N)，这个函数可以返回员工A、B、C、D的中等工资。
    写一个程序访问测试库，找出所有员工准确的工资数（除了永远不能确定的以外）。你的程序最多允许询问1000次问题。

交互方法
    你将获得的测试库提供了以下三个函数或过程：
       function init:longint;
       function meandian(a,b,c,d:longint):longint;
       procedure solution(var sol:array of longint);
    Init：调用该函数不带参数。这个函数必须在程序开头调用且只能调用一次。它将返回一个整数N，即公司的员工数。
    Meandian：这个函数被调用时需要带四个参数A、B、C、D。这四个数应该是从1到N的四个不同的数（包括1和N）。它返回一个整数，是员工A、B、C、D的中等工资。
    Solution：这个函数应该在程序结尾调用。你需要用一个表示员工工资的整数数组来作为它的参数。如果某个员工的工资不能确定，数组中对应的值应该为-1。
    注意这个数组必须从0开始。也就是说员工1的工资应该在数组的0位置，员工2应该在1的位置，依此类推。

    你的源程序在声明处必须包含“uses libmean”。
    编译时，你需要把库文件和源文件放在同一个目录。

一个成功交互的例子
    下面是一个程序代码的片段。它完全不能解决我们的问题，但它可以告诉你如何使用库函数。

uses libmean;
var i, n : integer;
    arr : array[0..99] of longint;
    foo, bar, quux : integer;
begin
   n := Init;
   foo := Meandian(1, 2, 3, 4);
   bar := Meandian(4, 2, 3, 1);
   quux := Meandian(n, n-1, n-2, n-3);
   for i := 1 to n do
      arr[i-1] := 2*i;
   arr[3] := -1;
   Solution(arr);
end.

你如何测试自己的程序
    我们提供的库允许你通过标准输入读进数字N和N个偶数来测试你的程序。
    这个库将输出一个信息告诉你你的答案是否正确。它同时产生一个包含有你的程序运行的详细信息的文本文件meandian.log。
    下面的例子告诉你如何为你的程序输入数据。测试库将告诉你你的答案的正确性。
10
100 500 200 400 250 300 350 600 550 410

评分方法
    当你提交的答案与我们的正确答案相符时得10分。我们一共将有10次测试，总共100分。
    出现以下情况均不给分：
      程序提交的答案错误或没有提交答案；
      程序运行时间超过0.1秒；
      程序使用内存空间超过64M；
      程序询问次数超过1000次；
      程序崩溃或意外退出；
      错误访问库导致测试库出错；
      程序访问了其它外部文件。

数据规模
    对于30%的数据，N<=10；
    对于50%的数据，N<=50；
    对于100%的数据，N<=100。

题解：
    当时我做同步赛时，只有这道题AC了，因此对这道题情有独钟。
    如果N=4，那么显然一个都问不出来。那么N=5呢？通过下面的方法可以问出这5个人中工资排在中间的那个人是谁，并且知道他的具体工资数。假如这5个人按工资从低到高排序分别为A、B、C、D、E，那么问ABCD和ABCE将得到两个相等的小值（BC的平均数），问ACDE和BCDE将得到两个相等的大值（CD的平均数）。剩下的结果由ABDE产生，其值介于前面两者之间（BD的平均数）。换句话说，把5种问法问个遍，那么得数最大的就是CD的平均数，得数最小的是BC的平均数，剩下的那个就是BD的平均数。根据这三个式子，我们就可以算出BCD的值是什么了。但我们只知道了三个人的工资数，还不知道哪个人对应哪个人。你会发现，你不能确定B和D具体是哪个人，但C是谁我们肯定知道。C所对应的人就是问出BD的平均数的那一次询问里没有被问到的人。
    询问5个人可以问出一个人来，那么我们就不断地找5个都还不知道的人重复这个过程。我们不必真的去“找”工资还没确定的人，只需要用一个新的人来代替前一个5人组中问出来了的那个人。这样下去我们只需要不到500次就可以问出N-4个人的具体工资。这种方法不能确定工资最小的两个人和工资最大的两个人。
    事实上，我们可以证明这4个人永远不可能被问出来。假如把工资最小的两个人它们对应的工资数交换一下，你会发现所有可能问到的问题答案仍然不变，因此这两个人不能判断谁是谁。对于工资最大的两个人道理相同。

Problem 3: gf 谁是我的女友
题目来源：Matrix67根据经典问题改编

问题描述
我们学校有M个男生，N个女生（M<=N<=1000）。每个男生都在这些女生中找到了一个知己。每个男生都恰有一个女友，不同的男生有不同的女友（有N-M

非传统题型练习：三道答案提交类题目

2007 年 3 月 6 日 / 4 条评论

不少人可能为找不到非传统题型的练习题而头疼。这几天我专门发出一些用于省选集训的题目供大家参考。

Problem 1: cell 手机
题目来源：USACO Contest FEB06 Gold (Translated by Matrix67)

问题描述
    奶牛们已经开始使用手机交流了，但它们发现手机的按键设计不适合它们的蹄子。它们想设计一个新的手机，让它的按键更少，但是更大。
    它们喜欢普通手机的一个功能：词语联想。每个按键都有一些字母和它对应，打出一个单词只需要按对应的按键。因为一个按键可能对应多个字母，因此某些单词可能会发生“歧意”。不过，大多数时候这种歧意可以通过用字典判断的方法来消除。
    考虑到奶牛们在自定义一款新的手机，它们还需要用奶牛字母表替换英文字母表。神奇的是，奶牛字母表中的字母恰好是英语字母表中的前L个字母，即使顺序也一样。它们想知道如何把这些字母分配给B个按键(1<=B<=L)使得在字典中不会产生歧意的单词最多。就像普通的手机一样，他们希望每个按钮上的字母都是字母表中一段连续的字母。

    这是一个答案提交类的题目。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件cell.3.in相对应的输出文件应该为cell.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入数据
    第一行：一个整数N，表示这是第N个输入文件。
    第二行：两个用空格隔开的整数：B和L
    第三行：D，字典中的单词数(1<=D<=1000)
    第四行到第D+3行：每一行包含一个字典中的单词，用1到10个大写字母表示。这些单词按照字典序给出，并且保证没有重复。

输出数据
    第一行：字典中具有唯一的按钮序列的单词数。
    第二行到第B+1行：其中的第n行包含有第n个按钮上的字母，用大写的字母按照字典的顺序表示。所有行必须按照字典序排列，每个字母出现恰好一次。如果有多个最优解，选用第一个按键上字母最多的解。如果最优解仍然不唯一，考虑第二个按键上字母最多，依此类推。

样例输入(cell.1.in)
1
3 13
11
ALL
BALL
BELL
CALK
CALL
CELL
DILL
FILL
FILM
ILL
MILK

样例输出(cell.1.out)
7
AB
CDEFGHIJK
LM

样例说明
    第一个按键上只有AB两个字母，第二个按键上含有C到K，第三个按键上为LM。单词CELL、DILL、FILL和FILM的输入都是2233，其它7个单词的输入都是唯一的。

题解(Ctrl+A)：
这道题目……搜索，乱搞。

Problem 2: selfstr 自描述序列
题目来源：Matrix67根据经典问题改编

问题描述
    “这句话里有1个数字零，2个数字一，1个数字二，0个数字三”。

    在N(N>=2)进制中只允许0到N-1这N个数字出现。一个N位的N进制数（允许有前导0）可以由另一个同样多位的数来描述。我们定义一个N位N进制数的描述序列为：左起第i个数字为原数中数字i-1出现的次数。
    例如，在4进制中，0023的描述序列为2011，因为0023中有2个0，0个1，1个2和1个3。
    我们惊奇地发现，4进制数1210的描述序列是它本身！我们称这样的数叫做“自描述序列”。

    你需要编写程序计算出在某个进制下的自描述序列。一个进制下的自描述序列可能有很多个，你只需要给出其中一个即可。
    这是一个答案提交类的问题。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件selfstr.3.in相对应的输出文件应该为selfstr.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入格式
    输入数据只有一个正整数N

输出格式
    输出N个字符，它表示N进制下的自描述序列。在高于10的进位制下，大于9的数字请用大写字母表示。
    如果有多种可能的解，你只需要输出其中一个。
    如果该进制下无解，请输出“NONE”。

样例输入(selfstr.1.in)
4

样例输出(selfstr.1.out)
1210

题解：
这道题太有意思了！首先，你需要先算几个小数据。你会发现，算到N>=6后，渐渐有规律了：

   N   N进制下的自描述序列
   4    1210 or 2020
   5    21200
   6    NONE
   7    3211000
   8    42101000
   9    521001000

事实上，这道题目就是考你当搜索到一些解后能不能找到规律得到所有解。这里我们发现，对所有N>6，至少存在一个解为R21(0…0)1000，其中R=N-4，中间0的个数为N-7。结论显然正确。
有可能除了这个之外存在其它的解，因此我们仍然需要写一个check来核对答案。

Problem 3: relation 大小关系
题目来源：Matrix67根据经典问题改编

问题描述
    用关系“ < ”和“ = ”将3个数a、b、c依次序排列时，有13种不同的序列关系：
      a=b=c, a=b<c, a<b=c, a<b<c, a<c<b
      a=c<b, b<a=c, b<a<c, b<c<a, b=c<a
      c<a=b, c<a<b, c<b<a

    用这两种关系连接N个数有多少种不同的方案？

    这是一个答案提交类的问题。所有选手将得到10个输入数据，你只需要在你自己的计算机上计算出你的答案，然后把你的答案提交上来。与输入文件relation.x.in相对应的输出文件应该为relation.x.out，这里x表示一个1到10之间的数。

输入格式
    输入一个整数，表示N。

输出格式
    输出用小于和等于符号将N个数进行有序排列的方案数。

样例输入(relation.1.in)
3

样例输出(relation.1.out)
13

题解：
    组合数学+高精度。由于数据规模很小，我就直接搞成了答案提交类的题目。
    下面给出两种递推方法：
    Solution 1: N个数中必然存在一个最大的“等价类”，如果这个等价类里有k个数，那么剩下的数就有F(N-k)种排列方案。别忘了我们需要枚举这k个数是哪k个数。于是，F(N)
=C(N,1)F(N-1)+C(N,2)F(N-2)+C(N,3)F(N-3)+ … +C(N,N)F(0)
    Solution 2: 用F[ i, j]表示 i个数中有j 个等价类的排列方案（就是说有j-1个小于符号）。第 i个数有可能并入了F[i-1, j]中的 j个等价类中的一个，也有可能不与任何一个已有的数相等，独自成为一个等价类插入F[i-1, j-1]里产生的 j个空位中。于是，F[ i,j ]=F[i-1, j]*j + F[i-1,j-1]*j。

其它问题：
    如何用Cena评测答案提交类问题？
        见http://www.matrix67.com/blog/article.asp?id=176
    这些题的数据哪里有？
        第一题：http://ace.delos.com/FEB06，GOLD DIVISION里面的第三个
        第二题：自己写check，不需要数据
        第三题：http://www.research.att.com/~njas/sequences/b000670.txt，吓死你

Matrix67原创
转贴请注明出处