NOIP2018Day1！！！題目出爐！！！

今天是NOIP2018 Day1的日子，小編作為學生黨，也參加了NOIP。

自測100，太爛了QAQ

希望明天發揮正常。

下面來給題目和我的思路。

T1

鋪設道路

題目描述

春春是一名道路工程師，負責鋪設一條長度為 n的道路。

鋪設道路的主要工作是填平下陷的地表。整段道路可以看作是 n 塊首尾相連的區 域，一開始，第 i 塊區域下陷的深度為 di 。 春春每天可以選擇一段連續區間[L,R]  ，填充這段區間中的每塊區域，讓其下陷深 度減少 1。在選擇區間時，需要保證，區間内的每塊區域在填充前下陷深度均不為 0 。 春春希望你能幫他設計一種方案，可以在最短的時間内将整段道路的下陷深度都變 為 0 。

輸入輸出格式

輸入格式：

輸入檔案包含兩行，第一行包含一個整數 n，表示道路的長度。 第二行包含 n 個整數，相鄰兩數間用一個空格隔開，第i  個整數為 di。

輸出格式：

輸出檔案僅包含一個整數，即最少需要多少天才能完成任務。

輸入輸出樣例

輸入樣例#1：

6   
4 3 2 5 3 5 
      

輸出樣例#1：

9      

說明

一種可行的最佳方案是，依次選擇： [1,6]、[1,6]、[1,2]、[1,1、[4,6]、[4,4]、[4,4]、[6,6]、[6,6。

對于 30%30\%30% 的資料，1≤n≤10 ；

對于 70%70\%70% 的資料，1≤n≤1000；

對于 100%100\%100% 的資料，1≤n≤100000,0≤di≤10000 。

QAQ，其實還蠻簡單的。

我是這樣想的：

首先，樣例解釋告訴我們：盡量一次填坑選最大的區間。讓我們來模拟一下：

我們每次記錄一下最小值，Ans就累加min，在把所有區間的數減min，再以min的編号為中間點，向兩邊遞歸，是一個很類似二分的算法。

下面我們來付上代碼：

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,a[100010];
 4 int ans=0;
 5 int Read()
 6 {
 7     char a=getchar();
 8     int f=1,r=0;
 9     while(a<'0'||a>'9')
10     {
11         if(a=='-')
12             f=-1;
13         a=getchar();
14     }
15     while(a<='9'&&a>='0')
16     {
17         r=r*10+a-'0';
18         a=getchar();
19     }
20     return r*f;
21 }//讀入優化，可删去
22 void search(int left,int right)
23 {
24     if(right<left)
25         return;
26     int minn=0x3f3f3f3f,mid;
27     for(int i=left;i<=right;i++)
28     {
29         if(minn>a[i])
30         {
31             minn=a[i];
32             mid=i;
33         }
34     }
35     ans+=minn;
36     for(int i=left;i<=right;i++)
37         a[i]-=minn;
38     search(left,mid-1);
39     search(mid+1,right);
40 }//二分搜尋
41 int main()
42 {
43     n=Read();
44     for(int i=1;i<=n;i++)
45         a[i]=Read();
46     search(1,n);
47     cout<<ans<<endl;
48     return 0;
49 }      

這其實就完了，大家可以在

NOIP2018提高自測

測評自己的代碼。

但是，考試結束後，我意識到了一點，點開下面的連結，仔細對比，你也懂。

QAQ

不懂得私信。

T2

貨币系統

在網友的國度中共有 n種不同面額的貨币，第 i 種貨币的面額為 a[i]，你可以 假設每一種貨币都有無窮多張。為了友善，我們把貨币種數為 n、面額數組為 a[1..n] 的貨币系統記作 (n,a)。

在一個完善的貨币系統中，每一個非負整數的金額 x都應該可以被表示出，即對 每一個非負整數 x，都存在 n個非負整數 t[i]滿足 a[i]×t[i]的和為 x。然而， 在網友的國度中，貨币系統可能是不完善的，即可能存在金額 x 不能被該貨币系統表示出。例如在貨币系統 n=3, a=[2,5,9] 中，金額 1,3 就無法被表示出來。

兩個貨币系統 (n,a)和 (m,b) 是等價的，當且僅當對于任意非負整數 x，它要 麼均可以被兩個貨币系統表出，要麼不能被其中任何一個表出。

現在網友們打算簡化一下貨币系統。他們希望找到一個貨币系統 (m,b)，滿足 (m,b) 與原來的貨币系統 (n,a) 等價，且 m盡可能的小。他們希望你來協助完成這個艱巨的任務：找到最小的 m。

輸入檔案的第一行包含一個整數 T，表示資料的組數。

接下來按照如下格式分别給 出 T 組資料。 每組資料的第一行包含一個正整數 n。接下來一行包含 n 個由空格隔開的正整數 a[i]。

輸出檔案共有 T行，對于每組資料，輸出一行一個正整數，表示所有與 (n,a) 等價的貨币系統 (m,b)中，最小的 m。

複制

2 
4 
3 19 10 6 
5 
11 29 13 19 17       

2   
5  

      

其實，這道題也不難，思路我在賽後才想出來，于是也沒寫代碼。

這就是一個完全背包問題！！！

一個數可以選多次，要滿足和為一個數！

當時我在考場上怎麼沒想到啊QAQ

我實在是沒辦法。隻能在心裡無助的呼喊。

最後一題

不會QAQ

我太弱了，畢竟還有很大的學習空間，這一題我是一點思路都沒有，如果我沒有脈動——仙人掌口味，就撐不到現在了QAQ

上題目吧。

這裡我真的無話可說，希望大佬幫幫蒟蒻，提供一個解答，不勝感激。

T3

賽道修建

C 城将要舉辦一系列的賽車比賽。在比賽前，需要在城内修建 m 條賽道。 

C 城一共有 n 個路口，這些路口編号為 1,2,…,n，有 n−1條适合于修建賽道的雙向通行的道路，每條道路連接配接着兩個路口。其中，第 iii 條道路連接配接的兩個路口編号為 ai​ 和 bi​，該道路的長度為 li​。借助這 n−1 條道路，從任何一個路口出發都能到達其他所有的路口。

一條賽道是一組互不相同的道路 e1,e2,…,ek，滿足可以從某個路口出發，依次經過 道路 e1,e2,…,ek（每條道路經過一次，不允許調頭）到達另一個路口。一條賽道的長度等于經過的各道路的長度之和。為保證安全，要求每條道路至多被一條賽道經過。 

目前賽道修建的方案尚未确定。你的任務是設計一種賽道修建的方案，使得修建的 m 條賽道中長度最小的賽道長度最大（即 m條賽道中最短賽道的長度盡可能大）

輸入檔案第一行包含兩個由空格分隔的正整數 n,m，分别表示路口數及需要修建的 賽道數。

接下來 n−1行，第 iii 行包含三個正整數 ai,bi,li，表示第 i條适合于修建賽道的道 路連接配接的兩個路口編号及道路長度。保證任意兩個路口均可通過這 n−1條道路互相到達。每行中相鄰兩數之間均由一個空格分隔。

輸出共一行，包含一個整數，表示長度最小的賽道長度的最大值。

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

31      

輸入樣例#2：

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

輸出樣例#2：

15      

對于今天的題目，我也不能多說什麼，祝願大家的mark++,rank--;

大家可以去洛谷（上面的連結）自測一下分數，好讓自己心裡踏實一點。

題目檔案下載下傳

明天又是苦戰的一天，我們明天繼續！