信息学初赛问题求解解题

信息学初赛问题求解部份（14-18）（第十四届）书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的把这4本书摆在书架上，知足所有黑皮的书都排在一路的摆法种。知足A必需比C靠左，所有红皮的书要摆在一路，所有黑皮的书要摆放在一路，共有 种摆法。解:一、分析（1）CDAB (2)CDBA (3)ACDB (4)BCDA (5)ABCD (6)BACD(7)DCAB (8)DCBA (9)ADCB (10)BDCA (11)ABDC二、分析(1)ABCD （2）BACD (3)ABDC (4)BADC有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距如下表所示，那么城市1到城市6的最短距离为 7 。城市1城市2城市3城市4城市56城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920解：(1->2->5->6)12，5，62+3+2=7.是距离最短的。（第十五届）小陈现有2个任务A，B要完成，每一个任务别离有假设干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。可是若是情愿，他能够在做完手中任务的当前步骤后，切换至另一例如……a2->b2->a3->b3……a2->b3->a3->b2……是不合法的。Bb1A，其他的都忘了。使计算小陈饭前已做的可能的任务步骤序列共有 种解法一：ABa3014102035a201361015a101234501b11b21b31b41b5a3解法二：排列组合+加法原理B任务中的b1必然做，而且确信是第一个做的。除b1外第一类：完成A任务 只有1种。第二类：完成A任务和b2 有C(4,1)=4种。第三类：完成A任务和b二、b3 有C(5,2)=10种第四类：完成A任务和b二、b3、b4 有C(6,3)=20种Abb3、b4、b5C(7,4)=351+4+10+20+35=70。1.a:=1;2.b:=a;3.d:=-a;4.e:=a+d;5.c:=2*d;6.f:=b+e-d;7.g:=a*f+c;此刻要把这段程序分派到假设干台（数量充沛）用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通信，互换一些中间结果。假设每台PC每单位时刻能够执行一个语句，且通信花费的时刻不计。那么这段程序最快能够在 单位时刻内执行完毕。注意：任意中间结果只有某台PC上已经取得，才能够被其他PC引用。例如假设语句4和6被别离分派到两台PC上执行，那么因为语句6需要引用语句4的计算结果，语句6必需在语句4以后执行。1，2345，6，7。（第十六届）1、LZW编码是一种自适应词典编码。在编码的进程中，开始时只有一部基础构造元素的编码词典，若是在编码的进程中碰到一个新的词条，那么该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。举例说明，考虑一个待编码的信息串：“xyxyyyyxyx”。初始词典只有3个条款，第一个为x,编码为1；第二个为y，编码为2；第三个为空格，编码为3；于是串“xyx”的编码为1-2-1（其中-为编码分隔符），加上后面的一个空格确实是1-2-1-3。但由于有了一个空格，咱们就明白前面的“xyx”是一个单词，而由于该单词没有在词典中，咱们就能够够自适应的把那个词条添加到词典里，编码为4，然后依照新的词典对后继信息进行编码，以此类推。于是，最后取得编码：。此刻已知初始词典的3个条款如上述，那么信息串“yyxyxxyyxyxyxxx的编码是解：2-2-1-2-3--1-3-5-3-6（或2236）2、队列快照是指在某一时刻队列中的元素组成的有序序列。现有3个正整数元依次入队、出队。已知它们的和为8，那么共有 种可能的不同的队列照（不同队列的相同快照只计一次）。例如，"51"、"422"、""都是可能的队列快照；而"7"不是可能的队列快照，因为剩下的2个正整数的和不可能是1。解：49（第十七届）1每份考卷都有一个8位二进制序列号当且仅当一个序列号含有偶数个1时，它才是有效的。例如01010011都是有效的序列号，而不是。那么有效的序列号共有 个解：这是个排列组合问题中的组合问题。8个二进制各不干与，且只有2当选择即0或1，知足题意的序列号序列号中有0个1的有1个，序列号中有2个1的有28个，4个1的有70个，6个1的有28个，8个1的有1个。取得：1+28+70+28+1=1282、概念字符串的大体操作为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。将字符串A变成字符串B的最少操作步数，称为字符串A到字符串B的编辑距离。字符串"ABCDEFG"到字符串"BADECG"的编辑距离为 。解：编辑距离为3ABCDEFG删除A 得出BCDEFG(A→)BCDEFG将C替换成A 得出BADEFGBADEFG将F替换成C 得出BADECG(F→C)（第十八届）1、若是平面上任取n个整点（横纵坐标都是整数），其中必然存在两个点，它连线的中点也是整点，那么n至少是 。解：5想象横纵交织的网格纸，就像棋盘那样的，每一个横纵线交点确实是一个整点。如以下图：任意三个点若是共线，即处在水平，竖直，或对角线上，那么其中定存在两个点知足连线中点是整点。若是n=2，取两个持续的整点，那么连线中点不是整点。若是n=3，取水平两个持续的点，垂直也两个持续的点，组成三角形。那么连线中点不是整点。若是n=4，取四个整点组成一个正方形，那么连线中点不是整点。而取5个点的话，必然有两个点的连线中点是整点。2、在NOI期间，主办单位为了欢迎来自各国的选手，举行了盛大的晚宴。在第十八桌，有5名大陆选手和5名港澳选手一起进膳。为了增进交流，他们决定相隔就坐，即每一个大陆选手左右旁都是港澳选手，每一个港澳选手左右旁都是大陆选手。那么，这一桌一共种不同的就坐方案。注：若是在两个方案中，一个选手左右相邻的选手相同，那么视为同一种方案。解1：288011054410*5*4*4*3*3*2*2*1*1。这其中有重复的，同一种坐法，能够绕着桌子走一圈，确实是上一个人坐到下一个人的位置，串一下，如此所有坐法就算重复了10105*4*4*3*3*2*2*1*1。解2：28805然后再安排五个港澳选手，是一起进膳应该只有55P（5，5）种坐法，然后相乘。可到那个地址并非是就终止了，因为那个地址面包括了重复的，可是重复的情形超级极端，“每一个选手左侧相邻的选手均相同”，每一种方案，每一个人都往左或往右移动一个位子，两个位子，三个位子……跟原先的仍是一样的方案，也确实是说每十种方案里一共有5种是重复的。因此要去除重复，除以5。因此应该是P（5，5）*P（5，5）/5。附：排列组合原理一、加法原理与乘法原理一、加法原理：nm1种不同的方式，m2nmn那么完成这件事共有N=m1+m2+...+mn种不同的方式。二、乘法原理：做一件情形，完成它需要分成nm1m2nmn有N=m1*m2*...*mn种不同的方式。完成”，乘法原理是“分步完成”。二、排列与组合的概念与计算公式一、排列及计算公式nm(1≤m≤n)nmnm(m≤n)素的所有