疊甲

今天從凌晨 \(0\) 點 \(00\) 分 一直盯著電腦屏幕到現在

要瞎了\(.jpg\)

賽后總結先咕一段時間吧

眼睛實在是不想再看任何電子顯示屏了

QAQ

NOIP模擬賽

題目名稱	上升序列	樹上標記	發送消息	猜數
題目類型	傳統型	傳統型	傳統型	傳統型
目錄	inc	mark	message	guess
可執行文件名	inc.cpp	mark.cpp	message.cpp	guess.cpp
輸入文件名	inc.in	mark.in	message.in	guess.in
輸出文件名	inc.out	mark.out	message.out	guess.out
每個測試點時限	2.0秒	2.0秒	4.0秒	2.0秒
內存限制	512MB	512MB	512MB	512MB
子任務數目	10	20	10	10
測試點是否等分	是	是	是	是

T1 上升序列（inc）

題目描述

藤坦坦和藤茵茵在玩一個這樣的猜數：有 $ n $ 張卡片排成一排，第 $ i $ 張卡片的正面寫著 $ a_i $，背面寫著 $ b_i $。藤坦坦可以任意翻轉這些卡片，讓任何一面朝上（但是卡片之間的順序不能換）。

藤坦坦操作完之后，藤茵茵需要按照從前往后的順序拿取其中一些卡片，但需要保證，每拿取一張卡片，朝上的這一面上的數字要比上一張卡片大。

現在，兩人想知道應該如何配合，能讓藤茵茵拿到盡可能多的卡片。

輸入格式

從文件 inc.in 中讀取數據
輸入的第一行一個整數 $ n $。
輸入的第二行 $ n $ 個整數，第 $ i $ 個整數為 $ a_i $。
輸入的第三行 $ n $ 個整數，第 $ i $ 個整數為 $ b_i $。

輸出格式

輸出到文件 inc.out 中
輸出一行一個整數，表示藤茵茵最多能拿到的卡片數

輸入樣例 1

10
2 6 6 7 5 3 8 1 10 3
7 7 2 1 2 5 4 2 4 10

輸出樣例 1

5

樣例 1 解釋

最優策略是，藤坦坦選擇正面朝上的數字為：2 6 6 1 2 5 8 1 10 3
然后藤茵茵從前往后依次選擇：1,2,5,8,10

輸入樣例 2

見下發文件 sample_inc2.in

輸出樣例 2

見下發文件 sample_inc2.out

數據范圍與約定

• 對于 20% 的數據，保證 $ 1 \leq n \leq 10, 1 \leq a_i, b_i \leq 1000 $。
• 對于 50% 的數據，保證 $ 1 \leq n \leq 1000, 1 \leq a_i, b_i \leq 1000 $。
• 對于 80% 的數據，保證 $ 1 \leq n \leq 5000 $。
• 對于 100% 的數據，保證 $ 1 \leq n \leq 10^6, 1 \leq a_i, b_i \leq 10^9 $。

T2 樹上標記（mark）

題目描述

有一棵 $ n $ 個點的樹，藤茵茵和藤坦坦現在要在這棵樹上進行如下操作：

1. 藤茵茵選擇兩個點 $ A $ 和 $ B $，滿足 $ A $ 和 $ B $ 在樹上都只有一個鄰居，然后從 $ A $ 沿最短路徑走到 $ B $，并把沿途經過的點打上標記
2. 藤坦坦選擇一個點 $ S $，然后沿最短路徑走到距離 $ S $ 最近的已經被打上標記的點
3. 現在，兄妹倆希望他們倆走的步數的乘積最大。你來幫助兄妹倆算一算，這個最大值是多少呢？
4. 同時，兄妹倆還有一個疑問，藤茵茵有多少種選擇 $ A, B $ 的方法，使得藤坦坦能選出一個 $ S $ 來達到最大乘積呢？

注意：這里的 $ (A, B) $ 是無序的二元組，所以 $ A, B $ 和 $ B, A $ 視為藤茵茵的同一種選法

輸入格式

從文件 mark.in 中讀取數據
第一行一個正整數 $ n $ 表示樹上點數
接下來 $ n - 1 $ 行，每行兩個正整數 $ u, v $ 表示一條樹邊 $ (u, v) $

輸出格式

輸出到文件 mark.out 中
輸出一行兩個整數，分別表示兩個人步數乘積的最大值和藤茵茵的選擇方案數

輸入樣例 1

6
1 2
1 3
2 4
2 5
2 6

輸出樣例 1

4 3

樣例 1 解釋

• 藤茵茵取 $ (A, B) = (4, 5) $，走的步數為 2，藤坦坦取 $ S = 3 , S $ 最近的標記點是 2，步數是 2，因此乘積為 $ 2 \times 2 = 4 $
• 除此之外，藤茵茵也可以取 $ (A, B) = (4, 6) $ 或 $ (A, B) = (5, 6) $，都存在 $ S $ 能使乘積達到最大

輸入樣例 2~4

見下發文件 sample_mark2~4.in

輸出樣例 2~4

見下發文件 sample_mark2~4.out

數據范圍與約定

測試點編號	$ n \leq $	特殊性質
1~2	20	無
3~5	200	無
6~7	3000	A
8~10	3000	無
11~13	$ 3 \times 10^5 $	A
14~17	$ 3 \times 10^5 $	無
18~20	$ 10^6 $	無

特殊性質 A：數據保證對每個 $ i = 1, 2, \dots, n - 1 , u_i $ 在 $ [1, i] $ 中均勻隨機選取，$ v_i = i + 1 $。

T3 發送消息（message）

題目描述

藤茵茵今天拿到了一個數字串 $ S $，它決定把這個數字串傳遞給藤坦坦。

因為數字串很長，所以藤茵茵想了一種簡單的表示方式：把數字串分解為若干級長的由相同數字組成的連續段，假設每一段有 $ k $ 個數字 $ x $，則傳遞時用 $ \overline{kx} $ 表示。

比如，如果 $ S = 112223 $，則 $ S $ 分為三個級長的相同數字連續段：11, 222, 3，然后分別表示為 21, 32, 13，所以最后她傳遞給藤坦坦的串就為 213213。再比如 $ S = 11111111111122 $，則傳遞給藤坦坦的串為 12122。

藤坦坦在收到藤茵茵發送的串 $ T $ 以后，又用同樣的方式進行表示，變成字符串 $ Q $ 傳遞給藤一零。

當藤一零收到 $ Q $ 之后，它有了一個疑問，藤茵茵拿到的 $ S $ 可能有幾種情況呢？

輸入格式

從文件 message.in 中讀取數據
一個由 $ 0 \sim 9 $ 組成的數字串 $ Q $

輸出格式

輸出到文件 message.out 中
輸出 $ S $ 的方案數，答案對 $ 10^9 + 7 $ 取模

輸入樣例 1

2122

輸出樣例 1

3

樣例 1 解釋

可能的 $ S $ 有以下三種情況：

• $ S = 122 $，發送給藤坦坦后 $ T = 1122 $，然后發給藤一零變成 $ Q = 2122 $ .

• $ S = \underbrace{222 \dots 2}_{112 \text{ 個}2} $，發送給藤坦坦后 $ T = 1122 $，然后發給藤一零變成 $ Q = 2122 $ .

• $ S = \underbrace{2222222 \dots 222}_{211 \text{ 個}2} $ ，(博客園的latex好像有點問題我不換行他后面這公式出不來)

發送給藤坦坦后 $ T = \underbrace{222 \dots 2}_{212 \text{ 個}2} $，然后發給藤一零變成 $ Q = 2122 $

輸入樣例 2

1022112

輸出樣例 2

1032

輸入樣例 3

122112122112

輸出樣例 3

128451905

數據范圍與約定

令 $ n = |Q| $

• 測試點 1：$ n \leq 2 $
• 測試點 2,3：$ n \leq 7 $
• 測試點 4,5：$ n \leq 50 $
• 測試點 6,7,8：$ n \leq 1000 $，并且 $ Q $ 中沒有數字 0
• 測試點 9,10：$ n \leq 1000 $

T4 猜數（guess）

題目描述

有 $ n $ 個小球，每個小球有一個重量 $ w $，任意兩個小球的重量不相同?，F在藤坦坦想知道這 $ n $ 個小球中第二重的球是哪一個。

但是，藤坦坦并不知道每個小球的重量，實驗室只有一個天平，每次可以比較兩個小球的重量。

在藤坦坦到來之前，已經有其它同學進行了 $ m $ 次比較，并記錄在了實驗報告上，第 $ i $ 次比較得到的結果為 $ x_i $ 比 $ y_i $ 重。

現在，藤坦坦想通過盡可能少的次數，來確定哪個小球是第二重的。

你需要幫藤坦坦找到最小的操作次數 $ K $，使得無論任何情況，都一定能在 $ K $ 次內確定第二重的小球。

輸入格式

從文件 guess.in 中讀取數據
第一行兩個非負整數 $ n, m $ 表示小球的數量和已經比較的次數
接下來 $ m $ 行，每行兩個正整數 $ x, y $ 表示已經確定 $ x $ 比 $ y $ 重

輸出格式

輸出到文件 guess.out 中
輸出最小值 $ K $ 使得存在一種策略，能保證 $ K $ 次內一定確定第二重的小球。

輸入樣例 1

4 2
1 2
4 3

輸出樣例 1

2

樣例解釋 1

已經確定的關系為 $ w_1 > w_2 ， w_4 > w_3 $，最優策略如下：

• 先詢問 $ w_1 $ 和 $ w_4 $ 的關系
  • 如果 $ w_1 > w_4 $，我們可以確定的是 $ w_1 $ 為最大值，$ w_3 $ 不可能為次大值，因此再詢問一次$ w_2 $ 和 $ w_4 $ 即可確定第二大
  • 如果 $ w_1 < w_4 $，我們可以確定的是 $ w_4 $ 為最大值，$ w_2 $ 不可能為次大值，因此再詢問一次 $ w_1 $ 和 $ w_3 $ 即可確定第二大

無論哪種情況都可以在兩次確定次大值，同時如果只詢問一次不可能保證能找到次大值，因此答案為 2

數據范圍與約定

• 對于 10% 的數據，$ n \leq 5 $。
• 對于 30% 的數據，$ n, m \leq 300 $。
• 對于另外 10% 的數據，保證事先測試的 $ x $ 都不同。
• 對于另外 10% 的數據，保證事先測試的 $ y $ 都不同。
• 對于另外 10% 的數據，保證每個球都至少被事先比較過一次。
• 對于 100% 的數據，$ 1 \leq n, m \leq 5 \times 10^5 ， x \neq y $，保證給定的 $ m $ 條結果不會矛盾，保證相同的比較不會出現兩次。

簡潔的結尾