《信息学模拟赛试题》由会员分享，可在线阅读，更多相关《信息学模拟赛试题（4页珍藏版）》请在金锄头文库上搜索。
1、1.房子 (room.cpp)题目描述：lzq最近得到了面积为n*m的一大块土地（高兴INGa），他想在这块土地上建造一所房子, 这个房子必须是正方形的。但是，这块土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。这些瑕疵十 分恶心，以至于根本不能在上面盖一砖一瓦。他希望找到一块最大的正方形无瑕疵土地来盖房子。不过，这并不是什么难题，lzq在10分钟内就轻松解决了这个问题。 现在，您也来试试吧。输入格式：输入文件第一行为两个整数n,m （1v=n,mv=1000），接下来n行，每行m个数字，用空格隔 开。 0表示该块土地有瑕疵， 1表示该块土地完好。输出格式： 一个整数，最大正方形的边
2、长。输入样例：4 40 1 1 11 1 1 00 1 1 01 1 0 1输出样例：22单词编码（word.cpp ）题目背景有n种不同的单词，从1到n进行编号。其中第i种单词出现的总次数为wi , lzq想要用k 进制串 si 来替换第 i 种单词，使得其满足如下要求：对于任意的1 i, j n ，i / j，都有：si不是sj的前缀现在lzq想要知道，如何选择si，才能使替换以后得到的新的文章长度最小。在确保总长度最小的 情况下， lzq 还想知道最长的 si 的最短长度是多少？一个字符串被称为k进制字符串，当且仅当它的每个字符是0到k-1之间（包括0和k-1 ）的 整数。字符串strl
3、被称为字符串str2的前缀，当且仅当：存在1 t m，使得strl = str21.t。其中，m 是字符串str2的长度，str21.t表示str2的前t个字符组成的字符串。输入输出格式输入格式：输入的第1行包含2个正整数n, k，中间用单个空格隔开，表示共有n种单词，需要使用k进制字 符串进行替换。接下来n行，第i + 1行包含1个非负整数wi，表示第i种单词的出现次数。输出格式：输出包括 2 行。第 1行输出 1个整数，为文章经过重新编码以后的最短长度。第2行输出1个整数，为保证最短总长度的情况下，最长字符串si的最短长度。输入输出样例输入样例#1：输出样例#1：12输入样例# :输出样例
4、#2：说明【样例说明 1】用 X(k) 表示 X 是以 k 进制表示的字符串。一种最优方案：令 00(2) 替换第 1 种单词， 01(2) 替换第 2 种单词， 10(2) 替换第 3 种单词，11(2) 替换第 4 种单词。在这种方案下，编码以后的最短长度为：1 X 2 + 1 X 2 + 2 X 2 + 2 X 2 = 12最长字符串si的长度为2。一种非最优方案：令 000(2)替换第 1种单词，001(2)替换第 2种单词，01(2)替换第 3种单词，1(2) 替换第 4 种单词。在这种方案下，编码以后的最短长度为：1 X 3 + 1 X 3 + 2 X 2 + 2 X 1 = 12
5、最长字符串si的长度为3。与最优方案相比，文章的长度相同，但是最长字符串的长度更长一些。【样例说明 2】一种最优方案：令 000(3)替换第 1种单词， 001(3)替换第 2种单词， 01(3)替换第 3种单词， 02(3) 替换第 4 种单词， 1(3) 替换第 5 种单词， 2(3)替换第 6种单词。数据范围：n=100000,k=9【提示】选手请注意使用 64 位整数进行输入输出、 存储和计算。3不知道取什么题目的大水题(fire.cpp )题目描述lzq刚进高中，在军训的时候，由于lzq吃苦耐劳，很快得到了教官的赏识，成为了小教官”。在军训结束的那天晚上，lzq被 命令组织同学们进行
6、篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1, 2, .，n的顺序坐成一圈，而实 际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在 lzq 面前的一大难题。lzq 可向同学们下达命令，每一个命令的形式如下：(b1, b2,. bm -1, bm)这里m的值是由lzq决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是bl，b2, . bm的这m个同学的 位置。要求bl换到b2的位置上，b2换到b3的位置上，.，要求bm换到bl的位置上。执行每个命令都需要一些代价。 我们假定如果一个命令要移动m个人的位置，那么这
7、个命令的代价就是m。我们需要lzq用最少的总代价实现同学们的意愿, 你能帮助lzq吗？输入输出格式输入格式：输入文件fire.in的第一行是一个整数n(3 = n = 50000)，表示一共有n个同学。其后n行每行包括两个不同的正整数, 以一个空格隔开，分别表示编号是1的同学最希望相邻的两个同学的编号，编号是2的同学最希望相邻的两个同学的编 号，编号是n的同学最希望相邻的两个同学的编号。输出格式：输出文件fire.out包括一行，这一行只包含一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输 出-1。输入输出样例输入样例#1：输出样例#1：说明对于30%的数据，n = 1000；对于全部的数据， n = 50000。
