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

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

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原创
转贴请注明出处

发表评论

10  ×  1  =