07年国庆信息学讲义朱全民test

1、规则(logic.pas)【问题描述】这是一个非常有趣的智力，它规则简单而又变化多端。在一个 m*n 的方格里进行。开始时所有的格子都是白色。的目标是通过给出的线索按要求选择一些方格涂黑。这些线索是写在每一行和每一列前面的一些数字，它告诉了你该行或者该列应该出现的几组黑色方格各有多少个。下面是一个简单的例子。在某一行中，线索给出了“2 1 4”三个数字，那么从这一行的某个位置起将依次出现两个相邻的黑色方格、若干白色方格、一个黑色方格、若干白色方格、四个连续的黑色方格，并且不再有其它的黑色方格。一种可能的情况如下图所示。你需要选择一些方格黑色，使得这些黑色方格满足所有行和所有列的要求。例如，下图

2、给出了某个谜题的一个可能的解（第二列没有数字表示这一列没有黑色方格）。 给出这样一个谜题，请打印出该问题的解。【输入格式】第一行有两个用空格隔开的正整数 m,n，他们分别表示该谜题的方格列数和行数。接下来m 行从左至右描述了谜题的纵向信息。每一行有若干个数字，这些数字表示该列从上至下将会出现的连续黑色方格数。每一行用一个数字 0 作为结束。接下来n 行从上至下描述了谜题的横向信息。每一行有若干个数字，这些数字表示该行从左至右将会出现的连续黑色方格数。每一行用一个数字 0 作为结束。【输出格式】将谜题的解打印出来。每一个方格用两个字符表示。其中，一个白色方格用“ ”（两个空格）表示，一个黑色方格

3、用“#”表示。因此，输出数据一共有 n 行，每行 2m 个字符。保证输入数据有唯一解。【输入样例】logic.in420121113010012000【输出样例】logic.out # #【数据规模】对于 30%的数据，m,n=3； 对于 50%的数据，m,n=10；对于 100%的数据，m,n=20。【时间限制】各个测试点 5s文科生的(二) Human.pas【问题背景】化学不及格的 Matrix67 无奈选择了文科。他必须硬着头皮艰难地进行着文科的学习。【问题描述】这学期的政治、历史和地理各有n 章。每一科的教学必须按章节从前往后依次进行。若干章政治、若干章历史和若干章的地理内容可以一个

4、教学阶段。年级计划将整个学期的内容分成若干个阶段进行教学。为了保证各科教学进度相同，年级规定每一个阶段包含的各科的章节数必须相同。一个阶段包含的章节越多，这个阶段所需要的研究，假如某个阶段包含政史地各 k 章，则政治学习需要花费 3k 天的也就越多。经过，历史学习需要花费 5k 天的，地理学习需要花费 2k 天的，最后还需要 4 天的综合训练。一个阶段所花费的总时间是以上四项时间的和。为了便于安排时间，学校希望每个阶段恰好需要若干阶段所需要的天数都必须是 7 的整数倍（高三是没有完成。因此，划分出的每一个天的）。那么，这学期的课程最多可以划分成多少个阶段呢？你会想到，要想划分的阶段数最多，一个

5、阶段完成一章的任务就行了（因为 31+51+21+4=14 是 7 的整数倍）。但问题没有这么简单。每个都可能有一些独立性较强的连续章节，它们具有很强的连续性，必须在一个阶段中完成。如果你已知所有不能划分在两个或两个以上的阶段中的连续章节，你还能计算出最多能安排多少个阶段吗？【输入格式】第一行有两个用空格隔开的正整数n 和 m，分别表示各科续章节的个数。的章节数和不可分割的连第二行到第 m+1 行，每行告诉了一个信息，该信息说明了哪一个的第几章到第几章必须完成。同一科目给定的章节有可能重复或有。每一行信息分为两个部分。第一部分是“Politics:”、“History:”、“Geography

6、:”三个字符串中的一个；第二部分是用“-”连接的两个数字 x,y(1=xy=n)，表示该行第一部分所示的从第 x 章到第 y 章具有连续性。第二部分紧接在第一部分后面，没有任何符号分隔。【数据规模】对于 30%的数据，n,m=10； 对于 50%的数据，n,m=1000；对于 100%的数据，n,m=100 000。【输出格式】一个正整数，表示按照学校和年级的种种要求（见下）最多可以安排的阶段个数。如果没有符合条件的安排方案，请输出-1。【注意】：以下三个要求需要同时考虑。每一个阶段包含的各科章数相同；按时间函数计算出的各阶段所需天数必须是 7 的倍数；3.给出的任续章节都不能被分割开来。【输

7、入样例 1】Human.in8 3Politics:1-2 History:5-6Politics:1-4【输出样例 1】Human.out3【输入样例 2】Human.in4 2Geography:1-3 History:2-4【输出样例 2】Human.out-1【样例说明】最多可以安排三个阶段，具体方案如下：第一阶段完成各科第 1-6 章的课程第二阶段完成各科第 7 章的课程第三阶段完成各科第 8 章的课程Matrix67 的情书(Lovelettas)【问题背景】曾经使用过这样一种加密术：对于明文中的每个字母，会用它后面的第 t 个字母代替。例如，当 t=3 时，字母 A 将变成 C，

8、字母 B 将变成 D，字母 Y将变成 A，字母 Z 将变成 B（假设字母表是循环的）。这样一来，字母表：将变成：明文： I Love You密文： K Nqxg AqwA B C D E F G H I J K L M N O P C D E F G H I J K L M N O P Q R将加密为QSRTSUT U V W X Y ZV W X Y Z A B如此一来，需要传达的信息在外人看来就如同天书了。加上变得更加难以捉摸。会不时更换t 的值，使得后人称这种加密方法为“移位”【问题描述】有消息称：Matrix67 找到了自己的 Miss Right，正准备自己人生的第一次表白。Matr

9、ix67 已经写好了情书，但为了避免其它人截获，他打算采用加密。的移位进行你通过某种获知了 Matrix67 的。为了打探 Matrix67 的私密，你冒着生命终于搞到了这封情书。原以为可以轻易将情书，结果竟然发现聪明的 Matrix67 并没有直接写出加密用的 t 值，而是在那粉红色的信纸背面写着“t=你的幸运数字”。就这么放弃了吗？一个高智商的 OIer，你决不轻言放弃。你需要编写一个解密程序，在不知道 t 值的情况下将原文打印出来。【输入格式】输入一段文字。文字中可能包含字母、数字、标点符号、空格、回车、制表符等各种符号，其中只有字母被加理过。加密后的字母其大小写不变。【输出格式】你的程

10、序需要在不知道 t 值的情况下输入文件并输出明文。的明文保证是成章的英文段落，没有语法和单词拼写错误。【输入样例】Loveletter.inK YKNN UJQY AQWAgu, K co uvknn cocbgf vjcv K jcxg aqw. Kvu uvknn jctf vq wpfgtuvcpf jqy aqw ejqug og. Jqy chvgt lwuv qpg ujqtv eqpxgtucvkqp aqw mpgy K ycu ogcpv hqt aqw. Dwv pqy Kmpqy vjg vtwvj qh aqwt eqpxkevkqp. Kxg pgxgt dggp y

11、kvj uqogqpg yjq uwkvgf og uqrgthgevna. Aqw uegf og ykvj aqwt ugza dqfa cpf uvtqpi urktkv, cpf aqwxg mgrvog ykvj aqwt vgpfgt jgctv. K mpqy aqw vjcv K ecpv jcxg aqw eqorngvgna cpf ocadgpqv gxgp hqt owej nqpigt. Dwv Ko uvknn jcrra. C rctv qh aqw jcu dgeqog rctv qh og cpf vjcv ku gpqwij.Aqwnn ncwij yjgp

12、 K uca vjku, dwv K ftgco cdqwv aqw gxgta pkijv. Rtqdcdna dgecwug K ecpv ugg aqw qhvgp gpqwij. Dwv yjgp Ko cycmg K mpqy vjcv aqw ctg vjg hwtvjguv vjkpi htqo c ftgco. Uqogvkogu K kocikpg vjcv aqw ctg dwknv htqo uqnkf tqem: c oqxkpiuvcvwg cpf cp kpfguvtwevkdng jwocp dgkpi. Aqw cduqnwvgna eqpvckp aqwtug

13、nh cpf vjgpcickej oqtg vjcp aqwtugnh. Aqwt eqphkfgpeg ku eqpuwokpi cpf aqwt rgturgevkxgku jwig. Aqw jcxg pq rnceg kp aqwt nkhg hqtqwua qt eqornckpvu. Oa htkgpfu uggouqn kp eqorctkuqp, ykvj vjgkt rtqdngou cnycau urknnkpi qxgt qpvq gxgtaqpg gnug.K ycpv aqw vq mpqy jqy owej aqwxg qrgpgf oa gagu cpf jgn

14、rgf og vtwna ugg oaugnh.Wpvkn pqy, ohg jcu dggp cp wpfgekfgf dcem-cpf-hqtvj, cpf pqy K mpqy vjcv Kxgycuvgf vowej vkog. Dwv pqy oa fktgevkqp uggou engct, cpf K jcxg eqphkfgpeg kpoa hwvwtg. Vjg rcuv fqgupv ugq ocvvgt cpaoqtg. Aqwxg ocfg og ugg rquukdknkvkguK yqwnf pgxgt jcxg kocikpgf dghqtg.Agu, K ycp

15、v vq rngcug aqw. Dwv kvu vjtqwij rngcukpi aqw vjcv Knn dgeqogvvgtcpf uvtqpigt rgtuqp. Vjgtg ku pqvjkpi K ycpv oqtg vjcp vq vtcpuhqto oaugnh vjtqwijaqw. Aqwngpig og vq itqy dgaqpf oaugnh cpf ngcxg oa ygcmgt ugnh dgjkpf. K yknnujqy aqw jqy dgcwvkhwn K ecp dg, cpf K yknn ujqy aqw jqy dtknnkcpv K ecp dg

16、eqog.Vjku yca, K mpqy Knn cnycau jcxg aqwt nqxg.Hqtgxgt aqwtu,Ocvtkz67【输出样例】Loveletter.outI WILL SHOW YOUYes, I am still amazedt I have you. Its still hard to understand how you choseme. How after just one short conversation you knew I was meant for you. But now Iknow the truth of your conviction. I

17、ve never been with someho suited me soperfectly. You seduced me with your sexy body and strong spirit, and youve keptme with your tender heart. I know yout I canve you compley and maybee part of menot even for much longer. But Im still happy. A part of you hasandt is enough.Youll laugh when I say th

18、is, but I dream about you every night. Probably becauseI cant see you often enough. But when Im awake I knowt you are the furthestthing from a dream. Sometimes I imaginet you are built from solid rock: a movingsue and an indestructible human being. You absoluy contain yourself and thenagauoren yours

19、elf. Your confidence is consuming and youris huge. You have no place in your life for jealousy or complas. My friends seemso small in comparison, with their problems always spilliner onto everyone else.I want you to know how much youve opened my eyes and helped me truly see myself.Until now, my life

20、 has been an undecided back-and-forth, and now I knowt Ivewasted too much time. But now my direction seems clear, and I have confidence inmy future. The past doesnt seem to matter anymore. Youve made me seeI would never have imagined before.sibilitiesYes, I want to please you. But its through pleasi

21、ng yout Ille a betterand strongerson. There is nothing I want moren to transform myself throughyou. You challenge me to growmyself and leave my weaker self behind. I willshow you how beautiful I can be, and I will show you how brilliThis way, I know Ill always have your love.ane.Forever yours,Matrix67座位的争执 (seat.pas)【问题描述】还记得 Matrix67 的“非常男女”计划吗？由 Matrix67 策划的学校大型男女配对活动将在大礼堂隆重举行，学校里许多人即将前来捧场。大礼堂一共有n 个座位，为了方便管理，Matrix