歷年題目訓(xùn)練problems

1、NOIP 模擬賽yyc題目概述題目名稱打一局嗎字符串哲學(xué)考驗(yàn)源程序文件名game.*str.*test.*輸入輸出文件名game.in/outstr.in/outtest.in/out測(cè)試點(diǎn)數(shù)目202020時(shí)間限制1s1s1s空間限制256MB512MB256MB編譯選項(xiàng)-O2 -lm -Wl,-stack=1000000000一、打一局嗎(game.*)【題目描述】Diaoyeye 作為健美先生，自然會(huì)受到很多人的，nyx 便是他們中的一位。nyx 具有自知之明，他知道 Diaoyeye 比他健美的多，和他剛正面顯然，于是要求 Diaoyeye 和他nyx 制定的。規(guī)則是這樣的：一副只有黑白

2、兩種顏色的牌，從背面看都是一樣，兩個(gè)人輪流取牌堆頂?shù)囊唬绻l先取到了黑色牌誰就獲勝。同時(shí)nyx 還請(qǐng)了pupil 來搗亂，pupil 會(huì)在兩個(gè)人取完牌后把牌堆頂?shù)囊荒米?，但是不?huì)給 nyx 和Diaoyeye，不論 pupil 這是黑色牌還是白色牌，都把它作廢。所以有可能 nyx 和Diaoyeye 都沒有抽到黑色牌，判為平局。nyx 通過一些知道了牌堆里黑色牌和白色牌的數(shù)量，然后他想知道先手獲勝概率和后手獲勝概率，然后考慮是不是快點(diǎn)投降。【輸入】輸入包括一行，兩個(gè)正整數(shù)，表示黑色牌和白色牌的數(shù)量。【輸出】輸出包括兩個(gè)整數(shù)，用空格隔開，分別表示先手獲勝的概率和后手獲勝的概率?！緲永斎?1】

3、 1 3【樣例輸出 1】 502267905 753401857【樣例解釋 1】先手取到黑色牌，先手贏。先手取到白色牌，后手取到黑色牌，后手贏。先手取到白色牌，后手取到白色牌，pupil 取到白色牌，先手取到黑色牌，先手贏。先手取到白色牌，后手取到白色牌，pupil 取到黑色牌，先手取到黑色牌，平局。 先手獲勝的概率是 0.5，取模之后是 502267905。后手獲勝概率是 0.25，取模之后是 753401857?！緲永斎?2】 3 1【樣例輸出 2】 251133953 753401857【樣例解釋 2】如果先手取到黑色牌則先手贏否則后手贏?！緮?shù)據(jù)范圍與約定】對(duì)于 20%的數(shù)據(jù)，1 =

4、, = 10。 對(duì)于 60%的數(shù)據(jù)，1 = , = 2000。對(duì)于 100%的數(shù)據(jù)，1 = , = 10000?！咎崾尽咳羰琴|(zhì)數(shù)，則1 1( )。二、字符串(str.*)【題目描述】Diaoyeye 正在研究字符串。nyx 向他問了一個(gè)問題：有一個(gè)字符串，其中不同子串的個(gè)數(shù)。Diaoyeye 顯然直接秒掉。他現(xiàn)在想問一問 nyx ，有一個(gè)字符串，從中選出兩個(gè)子串，求+可以的不同串的個(gè)數(shù)。Diaoyeye 還想知道，這么多個(gè)串中字典序最大的那一個(gè)。nyx 把這個(gè)問題扔給了你?！据斎搿恳粋€(gè)全由小寫字母【輸出】的字符串。第一行一個(gè)非負(fù)整數(shù)，表示兩個(gè)子串+可以的不同串的個(gè)數(shù)。由于可能很大，所以對(duì) 10

5、04535809 取模。第二行一個(gè)字符串，表示【樣例輸入 1】 ab【樣例輸出 1】 11bb【樣例解釋 1】的串中字典序最大的?？梢缘拇校篴，b，aa，aab，ab，aba，abab，abb，ba，bab，bb。共 11 種。字典序最大的是 bb。【樣例輸入 2】 abcaabccba【樣例輸出 2】 1428ccccba【樣例解釋 2】我有個(gè)絕妙的解釋可惜這里寫不下?！緮?shù)據(jù)范圍與約定】設(shè) = |。對(duì)于 10%的數(shù)據(jù)， = 10。對(duì)于 30%的數(shù)據(jù)， = 40。另有 20%的數(shù)據(jù)，字符串由 1 個(gè)a 字符和 1個(gè) b 字符對(duì)于 100%的數(shù)據(jù)， = = + + + 【輸入】第一行兩個(gè)正整數(shù)，意義如題。接下來行每行 2 個(gè)正整數(shù), ，表示個(gè)數(shù)對(duì)?！据敵觥恳粋€(gè)整數(shù)，意義如題?！緲永斎搿? 79 17 58 3【樣例輸出】4【數(shù)據(jù)范圍與約定】對(duì)于 20%的數(shù)據(jù)， = 50。 對(duì)于 40%的數(shù)據(jù)， = 1000。另有 20%的