SXKDZ

Tag: NOIp2011模拟

  • COCI 2008 Junior 试题及解析

    题目
    Instrukcije
    【题目描述】
    小马克今年成为小学生。不久后她将进行她的第一次考试，其中包括数学考试。她非常认真地复习，她认为自己已经准备好了。她的哥哥通过给她提出问题并解决的方式帮助她。
    他写下许多问题，其中一个问题是由一连串整齐的数字组成，比如1个1，2个2，3个 3 等等。现在他给马克两个整数A和B；她的任务是找出由这两数描述的数列的和（从第A个数到第B个数组成的序列）。如果A是1，B是3，答案为1+2+2=5。
    写一个问题，然后计算它们的和，小马克的哥哥能够验证答案正确与否。
    【输入格式】
    仅一行，包括正整数A和B，1≤A≤B≤1000。
    【输出格式】
    输出和仅显示一行。
    【输入样例】
    [cpp]1 3[/cpp]
    【输出样例】
    [cpp]5[/cpp]

    Lagno
    【题目描述】
    Lagno（西班牙和奥赛罗）是一种二人智力游戏。游戏设有一个黑方和一个白方。游戏桌面是正方形的，包含8行8列。
    如果黑方玩家走出这样一部棋：将一枚黑子放在任一空格上，而在这个空格的八个方向（上、下、左、右和4个对角线方向）的至少一个方向上有一排白子被夹在这枚新下的黑子和其他黑子之间，任何方向，这排被新旧黑子包夹的所有的白子都要变成黑子。为这个游戏设计一个程序，计算一步棋中黑方能转变的白子数量的最大值。
    【输入格式】
    输入有8行，每行8个元素：“.”代表一个空格，“B”代表黑子，“W”代表白子。
    【输出格式】
    输出一步中黑方能吃掉白子的最大数，如果无法吃掉就输出“0”。
    【输入样例】
    [cpp]……..
    ……..
    ……..
    …BW…
    …WB…
    ……..
    ……..
    ……..[/cpp]
    【输出样例】
    [cpp]1[/cpp]

    Pjesma
    【题目描述】
    “Guess the song”是一项在克罗地亚的年轻程序员中非常流行的游戏。它是一种集技能、智慧、耐性于一体的游戏。这个游戏给玩游戏的人放音乐，游戏者的目标是竟可能快地猜这首歌的歌名。
    Mirko可能不是一个很好的程序员，但他是一个世界级的猜歌者。Mirko总是在专辑里的某首歌播放出至少一半歌词的时候猜出歌名。所有歌名的单词是唯一的（没有一个单词会出现一次或更多次）。写一个程序，给出歌名和专辑名，看看Mirko在这首歌的哪个点上（在多少个单词之后）猜出歌名。
    【输入格式】
    第一行：包含一个整数N，1≤N≤50，它是一首歌里的单词数目。N下面的每一行包含歌名的一个单词。
    第二行：包含一个整数M，1≤M≤10 000，它是专辑里的单词数目。M下面的每一行包含专辑里的一个单词。
    歌名和专辑里的所有单词由1到15个小写英文字母组成。
    注：测试数据将会使得Mirko总能从专辑里猜出歌曲名。
    【输出格式】
    输出一个数：Mirko在这首歌的哪个点上（在多少个单词之后）猜出歌名。
    【输入样例】
    [cpp]3
    sedam
    gladnih
    patuljaka
    7
    sedam
    dana
    sedam
    noci
    sedam
    gladnih
    godina[/cpp]
    【输出样例】
    [cpp]6[/cpp]

    Nikola
    【题目描述】
    Nikola现在已经成为一个游戏里的重要人物。这个游戏是由一行N个方格，N个方格用1到N的数字表示。Nikola开始是在1号位置，然后能够跳到其他的位置，Nikola的第一跳必须跳到2号位置。随后的每一跳必须满足两个条件：
    如果是向前跳，必须比前面一跳远一个方格。
    如果是向后跳，必须和前面一跳一样远。
    比如，在第一跳之后（当在2号位置时），Nikola能够跳回1号位置，或者向前跳到4号位置。
    每次他跳入一个位置，Nikola必须付费。Nikola的目标是从一号位置尽可能便宜地跳到N号位置。
    写一个程序，看看Nikola跳到N号位置时最小的花费。
    【输入格式】
    第一行：包含一个整数N，2≤N≤1000，它是位置的编号。
    第2..N+1行：第i+1行表示第i个方格的费用，是一个正整数，绝对不超过500。
    【输出格式】
    输出Nikola跳到N号位置时最小的花费。
    【输入样例】
    [cpp]8
    111
    179
    64
    78
    219
    97
    160
    40[/cpp]
    【输出样例】
    [cpp]535[/cpp]

    解析
    第一题：Instrukcije
    算法：模拟。没什么好说的。
    第二题：Lagno
    算法：枚举。从任意一个点计算到其8个方向上第一个“W”点的距离，即这个点到8个方向上能将黑子变为白字的个数。
    第三题：Nikola
    算法：动态规划。
    状态：f[i][j] 表示当前跳到第i个点，上一步跳了j步的状态。
    初始值：f = Inf, f[1][0] = 0
    答案：Min{f[n]}
    转移方程：f[i][j] = Min{f[i][j], f[i – j][j – 1] + m[i]} = Min{f[i][j], f[i + j][j] + m[i]}
    时间复杂度：O(n^2)
    第四题：Pjesma
    题意：若N个单词在M个单词表中的前i个单词出现的个数大于N的一半，则输出i的值。
    算法：字符串处理。用一个标志数组标记是否匹配过。

    数据和标程
    数据：

    COCI2008普及组数据 (0 downloads )
    。
    标程：
    COCI2008普及组标程 (0 downloads )
    。

    版权
    题目、数据版权为COCI所有，题解、标程版权归Mr.SXKDZ所有，转载请注明出处！

  • 冲刺NOIp2011模拟题（三）

    袁绍的刁难(recruitment.c/cpp/pas, 1s, 128M)

    [题目描述]

    黄巾之乱后，郭嘉到了袁绍的统辖地区，结果袁绍想给我们的郭嘉大大一个下马威，且正值他招募将领的时候，于是乎，袁绍就让郭嘉大大去替他招募将领。
    这时候有很多很多的将领到袁绍处报到，每个将领的编号依次为1、2、3……N，第i个将领的武力值为3^(i-1)。
    袁绍需要我们的郭嘉大大招纳任意个将领，而郭嘉选中的将领有一个“总武力值”为各个将领的武力值之和。例如：郭嘉这一次招募了第一个将领和第三个将领，那么“总武力值”为1+9=10。
    袁绍想知道，他可以获得的第k大的“总武力值”是多少，请你帮助我们的郭嘉大大告诉袁绍这个第k大的“总武力值”。

    [输入格式]

    输入数据包含n+1行，第一行读入n(n≤100)。以下n行每行包含一个k。

    [输出格式]

    输出包含n行，每行输出一个对应的结果。

    [输入样例]

    1
    7

    [输出样例]
    13

    [样例说明]

    郭嘉能够拿到的总武力值从小到大为1、3、4、9、10、12、13……所以第7大的总武力值是13。

    [数据范围]

    对于50%的数据，有k≤5000。
    对于100%的数据，有k≤2^31-1。

    游历的路线(lines.pas/c/cpp, 1s, 128Ms)

    [题目描述]

    我们的郭嘉大大经过一段时间发现了袁绍这个人干大事而惜身，见小利而忘义，又逢曹操在招兵买马，决定逃离袁绍去投曹操，而我们的曹操在第M天招募良材，我们的郭嘉大大既不能早去，也不能晚去，于是乎，他就趁着这一段时间到其他的城市游历一番，而每两个城市之间只能坐马车来往，由于我们的郭嘉大大很贪钱，他想用最少的费用，所以需要我们帮他求出这一个最小的费用。

    [输入格式]

    第一行包含两个数n，m， 表示有n个城市，和m天后曹操招纳良材。城市一就是郭嘉所在的城市，城市n就是曹操处。接下来n * (n – 1)行描述马车乘坐表。第2到第n行就是描述的城市1到2… n的马车乘坐表，第n + 1到第2n – 1行描述的城市2到城市1，3..n的马车乘坐表……对每一行，首先有一个数T，表示城市I到城市J的马车以T为周期，接下来有T个数，表示每天的马车的价格，如果价格为0则表示没有马车可坐。（n <= 100, m <= 200, T <= 20， Price <= 50000）

    [输出格式]

    如果存在这样的路线使郭嘉第m天到达曹操处，则输出最少的费用，否则输出0！

    [输入样例]

    3 5
    2 130 150
    3 75 0 80
    2 110 100
    4 60 70 60 50
    3 0 135 140
    2 70 80

    [输出样例]

    355

    老师的询问(baffles.c/cpp/pas, 1s, 128M)

    [题目描述]

    东汉末年，颖川书院，有一日老夫子给他的学生出了一道问题，书院中有一口清澈见底的池塘（什么都看得见），老夫子要吃鱼，池塘里有很多很多鱼，而池塘是一个n*m的矩形，他希望放置最少的挡板，将池塘分成很多个矩形（包括正方形），使得每个矩形里有且只有一条鱼，而作为老夫子学生的郭嘉很想完成这个任务，所以他把这个任务交给了你，希望你能很快地解决问题。
    例如n=4，m=3时的一种情况（0表示小方格内无鱼，1表示有鱼）：
    0 1 0
    0 0 0
    1 0 1
    0 0 0
    可以这么分：
    0 1 0
    0 0 0
    – – –
    1|0 1
    0|0 0
    由于池塘边框不需要放置挡板，所以这个分割方案所需的挡板总长度为5。

    [输入数据]

    第一行有两个整数n和m（1≤n,m≤32），描述池塘规模。接下来的n行，每行有m个数字（非“0”即“1”）。每两个数字之间用空格隔开。

    [输出数据]

    对于每组输入数据，输出一行：一个数字，所需挡板的最短总长度。

    [输入样例]

    4 3
    0 1 0
    0 0 0
    1 0 1
    0 0 0

    [输出样例]

    5

    游历的路线(lines.pas/c/cpp, 1s, 128Ms)

    [题目描述]

    我们的郭嘉大大在曹操这过得逍遥自在，但是有一天曹操给了他一个任务，在建邺城内有N（N现在曹操要发布一个假消息，需要传达给所有奸细，而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息，问我们至少要传给几个奸细。

    [输入格式]

    输入文件的第一行为N，第二行至第N+1行为N*N的矩阵（若第I行第J列为1，则奸细I能将消息直接传递给奸细J，若第I行第J列为0，则奸细I不能将消息直接传递给奸细J）。

    [输出格式]

    输出文件只有一行：即我们的郭嘉大大首先至少要传递的奸细个数。

    [输入样例]

    8
    0 0 1 0 0 0 0 0
    1 0 0 1 0 0 0 0
    0 1 0 1 1 0 0 0
    0 0 0 0 0 1 0 0
    0 0 0 1 0 0 0 0
    0 0 0 1 0 0 0 0
    0 0 0 1 0 0 0 1
    0 0 0 0 0 0 1 0

    [输出样例]

    2

  • 冲刺NOIp2011模拟题（二）

    一、数列（sequence.pas/c/cpp, 1s,128M）

    【问题描述】
    一个数列定义如下：f(1)=1，f(2)=1，f(n)=(A*f(n-1)+B*f(n-2))%7。给定A, B和n的值，要求计算f(n)的值。
    【输入格式】
    输入文件sequence.in仅一行，包含3个整数A, B和n，其中（1<=A, B<=1000，1<=n<=100,000,000）。
    【输出格式】
    输出文件sequence.out仅一行，一个整数，即f(n)的值。
    【输入样例1】
    1 1 3
    【输出样例1】
    2
    【输入样例2】
    1 2 10
    【输出样例2】
    5
    【数据规模】
    20%的数据：n<=1000；
    40%的数据：n<=100,000；
    100%的数据：n<=100,000,000；
     
    二、最长路（path.pas/c/cpp, 1s,128M）
    【问题描述】
    设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当<i,j>为G的一条边时有i<j。设w(i,j)为边<i,j>的长度，请设计算法，计算图G中<1,n>间的最长路径。
    【输入格式】
    输入文件path.in的第一行有两个整数n和m，表示有n个顶点和m条边，其中2<=n<=1500，m<=50000；接下来m行中每行输入3个整数a, b, v表示从a点到b点有条边，边的长度为v。
    【输出格式】
    输出文件path.out，一个整数，即1到n之间的最长路径。如果1到n之间没连通，输出-1。
    【输入样例1】
    2 1
    1 2 1
    【输出样例1】
    1
    【输入样例2】
    2 0
    【输出样例2】
    -1
    【数据规模】
    20%的数据：n<=100, m<=1000；
    40%的数据：n<=1000, m<=10000；
    100%的数据：n<=1500, m<=50000；
     
    3．木棍（wooden.cpp/pas/c, 1s,128M）
    【问题描述】
    有n根木棍，每根的长度L和重量W已知。这些木棍将被一台机器一根一根地加工。机器需要一些启动时间来做准备工作，启时间与木棍被加工的具体情况有关。启动时间遵循以下规则：
    1．  加工第一根木棍的启动时间为1分钟。
    2．  加工完长度为L[i]，重量为W[i]的木棍后，紧跟着加工长度为L[i+1]，重量为W[i+1]的木棍，若L[i]<=L[i+1]且W[i]<=W[i+1]，则加工木棍i+1时，不需要启动时间。例如：有5根木棍，它们的长度和重量为(9,4),(2,5),(1,2),(5,3),(4,1)，则最小启动时间为2分钟（加工序列为(4,1),(5,3),(9,4),(1,2),(2,5)）。
    【输入格式】
    输入文件wooden.in的第一行是一个整数n（1<=n<=5000）,表示木棍的数量。第二行2*n个整数，L1,W1,L2,W2,……,Ln,Wn（1<=Li,Wi<=10000），为各木棍的长度和重量，这2*n个整数以若干个空格分隔。
    【输出格式】
    输出文件wooden.out仅一行一个整数，即最小总启动时间。
    【样例输入1】
    5
    4 9 5 2 2 1 3 5 1 4
    【样例输出1】
    2
    【样例输入2】
    3
    2 2 1 1 2 2
    【样例输出2】
    1
     
    四、括号匹配（bracket.pas/c/cpp, 1s,128M）
    【问题描述】
    定义如下括号匹配序列：
    1．  空序列是匹配序列；
    2．  如果S是匹配序列，那么(S),[S],{S}和<S>也是匹配序列；
    3．  如果A和B都是匹配序列，那么AB也是匹配序列。
    例如，下面的字符串都是匹配序列：
    ()，[]，(())，([])，()[]，/em>()[()]，{{}}<>，([]<>{{}})，<<{}>>

    而以下几个则不是：

    (，[，]，)(，())，([()，<<，{(})，<{}>)
    序列中可能包含通配符，含义如下：
    /表示任意1个左括号
    #表示任意2个左括号
    @表示任意4个左括号
    ?表示任意8个左括号
    \表示任意1个右括号
    *表示任意2个右括号
    &表示任意4个右括号
    !表示任意8个右括号
    现在，给你一些由“(”、“)”、“[”、 “]”、 “{”、“}”、“<”、“>”和通配符构成的序列。你要做的是判断该序列是否为匹配序列。
    【输入格式】
    第一行：一个正整数N，表示测试数据组数；
    接下来N行：每行一个括号序列(长度不超过L)。
    【输出格式】
    共N行：对于每一个括号序列，判断其是否匹配。
    对于不匹配的序列，直接输出FALSE。
    对于匹配的序列，输出用单一空格隔开的3个信息：
    第一个信息为TRUE；
    第二个信息为括号的最大深度(层数)；
    第三个信息为达到最大深度的次数。
    【样例输入】
    3
    {()}@<>{})))>
    ([})
    ?\\\\\\\]
    【样例输出】
    TRUE 5 2
    FALSE
    TRUE 8 1
    【样例解释】
    对于第一组数据，@相当于<(((，是匹配的，括号的最大深度为5，该深度出现了2次。
    对于第二组数据，[和}不匹配。
    第三组数据想要说明的是通配符间可以匹配。
    【数据规模】
    对于20%的数据：N=1，0<L<=20；
    对于60%的数据：0<N<=5，0<L<=2E+3；
    对于100%的数据：0<N<=10，0<L<=2E+6；

    对于40%的数据：序列中没有通配符。

     

  • 冲刺NOIp2011模拟题（一）

    一、报数

    【题目描述】
    CG同学又弄到一批新牛，新牛到了农场后，首先学习汉语，数的朗读成为新牛的难题。朗读绝对值小于10亿的数。
    新牛们知道汉语中有如下的朗读规则：
    1、首先读符号位，然后读整数部分。整数部分之后可能出现小数点，如果有小数部分则小数点一定出现，并且读出小数点之后读小数部分。
    2、符号位的读法是：
    （1）正数，不论正号“+”是否出现，都不必读出符号位；
    （2）负数最左边的符号是“-”读成“负”（以“F”来表示“负”）。
    3、整数部分的读法是：
    （1）如果整数部分不存在或整数部分全为零则直接读成“零”（以“0”来表示“零”）；
    （2）否则从整数部分中最左边的非零数字开始读起，然后以十，百，千，万，亿（分别以“S”,“B”,“Q”“W”,“Y”来表示）等数量单位来拼读整数部分。
    4、整数部分中：
    （1）每一个非零数字都必须结合各个相应的数量单位读出来。
    （2）每一段连续的“零”只能读成一个“零”，但是某一段连续的“零”的左侧或者右侧不存在非零数字（这里只考虑整数部分）则这一段“零”不应该读出来。
    5、如果有小数部分，则首先读“点”（以“D”来表示“点”），然后从左至右有顺序的读出各个小数位。在读小数部分的时候不可以使用十，百，千，万，亿等数量单位；但是小数部分的每一个数字都要读出来，连续的零不可以读成一个零，而应该分别读出。
    6、如果数中有小数点而没有小数部分，则不应该把小数点读出来。
    例如：
    -0020030004.567应该读成“F2Q03W04D567”，000.89应该读成“0D89”。
    请你编写程序帮助新牛把给定的数正确地读出来。

    【输入数据】
    输入文件仅一行，存放了一个数（不超过50个字符），其绝对值小于10亿。
    【输出数据】
    输出文件仅一行，输出这个数的正确读法。

    【样例输入】
    -0020030004.567
    【样例输出】
    F2Q03W04D567

    二、跑步

    【题目描述】
    新牛到部队，CG要求它们每天早上搞晨跑，从A农场跑到B农场。从A农场到B农场中有n-2个路口，分别标上号，A农场为1号，B农场为n号，路口分别为2…n-1号，从A 农场到B农场有很多条路径可以到达，而CG发现有的路口是必须经过的，即每条路径都经过的路口，CG要把它们记录下来，这样CG就可以先到那个路口，观察新牛们有没有偷懒，而你的任务就是找出所有必经路口。

    【输入数据】
    第一行两个用空格隔开的整数n（3≤n≤2000）和e（1≤e≤8000）。
    接下来从第2到第e+1行，每行两个用空格隔开的整数p和q，表示路口p和q之间有路径直达。
    输入数据保证必经路口一定存在，并且每个路口都和A农场、B农场相连通。
    【输出数据】
    第一行一个整数m，表示必经路口的数目。
    第二行按从小到大的顺序依次输出每个必经路口的编号，每两个数之间用一个空格隔开。
    注意：不包括起点和终点。

    【样例输入】
    6 6
    1 2
    2 4
    2 3
    3 5
    4 5
    5 6
    【样例输出】
    2
    2 5

    三、装备运输

    【题目描述】德国放松对英国的进攻后，把矛头指向了东边――苏联。
    1943年初，东线的战斗进行到白热化阶段。据可靠情报，90余万德国军队在库尔斯克准备发动浩大攻势。因此，朱可夫元帅要求你立即从远东的军工厂运输大量装备支援库尔斯克前线。
    列车司机告诉你，一趟列车最多可以容纳V体积的武器装备，但是你可能不能装满，因为列车承受不了那么大的重量，一趟列车最多可以承载G单位的重量。同时，军工厂仓库提供给你一份装备清单，详细记录了每件装备的体积、重量和火力。为了有效支援朱可夫元帅，你要找到一种方案，使得总火力值最大。

    【输入数据】
    第一行：V和G表示最大重量和体积。
    第二行：N表示仓库有N件装备。
    第三行到N+2行：每行3个数Ti Vi Gi表示各装备的火力值、体积和重量。
    【输出数据】
    输出一个数，表示可能获得的最大火力值。

    【样例输入】
    6 5
    4
    10 2 2
    20 3 2
    40 4 3
    30 3 3
    【样例输出】
    50

    【数据范围】
    对于50%的数据，V,G,N≤100；
    对于100%的数据，V,G,N≤400；

    四、翻转游戏

    【问题描述】
    翻转游戏是在一个4格*4格的长方形上进行的，在长方形的16个格上每个格子都放着一个双面的物件。每个物件的两个面，一面是白色的，另一面是黑色，每个物件要么白色朝上，要么黑色朝上，每一轮你只能翻3至5个物件，从而由黑到白地改变这些物件上面的颜色，反之亦然。每一轮被选择翻转的物件遵循以下规则：

    • 从16个物件中任选一个。
    • 翻转所选择的物件的同时，所有与它相邻的左方物件、右方物件、上方物件和下方物件（如果有的话），都要跟着翻转。

    以下为例：
    bwbw
    wwww
    bbwb
    bwwb
    这里“b”表示该格子放的物件黑色面朝上，“w”表示该格子放的物件白色朝上。如果我们选择翻转第三行的第一个物件（如下图所示），那么格子状态将变为：

    bwbw
    bwww
    wwwb
    wwwb
    游戏的目标是翻转到所有的物件白色朝上或黑色朝上。你的任务就是写一个程序求最少的翻转次数来实现这一目标。
    【输入格式】
    输入文件flip.in包含4行，每行4个字符，每个字符“w”或“b”表示游戏开始时格子上物件的状态。
    【输出格式】
    输出文件flip.out仅一个整数，即从给定状态到实现这一任务的最少翻转次数。如果给定的状态已经实现了目标就输出0，如果不可能实现目标就输出“Impossible”。
    【输入样例】
    bwwb
    bbwb
    bwwb
    bwww
    【输出样例】
    4

    题解在这里。