題目結構

填空題

第一題 空間

• 問題描述

  小藍準備用 256 M B 256MB 256MB 的記憶體空間開一個陣列，陣列的每個元素都是 32 32 32 位二進制整數，如果不考慮程式占用的空間和維護記憶體需要的輔助空間，請問 256 M B 256MB 256MB 的空間可以存盤多少個 32 32 32 位二進制整數？

• 解題思路

  ? 1 M B = 2 10 K B = 2 20 B = 2 20 × 8 b i t 1MB=2^{10}KB=2^{20}B=2^{20}\times 8 bit 1MB=210KB=220B=220×8bit，換算輸出即可，

• 答案

  67108864 67108864 67108864

第二題 卡片

• 問題描述

  小藍有很多數字卡片，每張卡片上都是數字 0 0 0 到 9 9 9，小藍準備用這些卡片來拼一些數，他想從 1 開始拼出正整數，每拼一個，就保存起來，卡片就不能用來拼其它數了，小藍想知道自己能從 1 拼到多少，例如，當小藍有 30 30 30 張卡片，其中 0 0 0 到 9 9 9 各 3 3 3 張，則小藍可以拼出 1 到 10，但是拼 11 時卡片 1 已經只有一張了，不夠拼出 11，現在小藍手里有 0 到 9 的卡片各 2021 2021 2021 張，共 20210 20210 20210 張，請問小藍可以從 1 1 1拼到多少？提示：建議使用計算機編程解決問題，

• 解題思路

  直接模擬到用完為止，注意細節，最后退出的數需要減 1 1 1，因為我們拼不成，

• 代碼

/**
  *@filename:B
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-18 14:37
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

int n;
int a[10];
bool work(int x){
    while(x){
        int temp=x%10;
        x/=10;
        if(a[temp]>0){
            a[temp]--;
        }
        else{
            return false;
        }
    }
    return true;
}
int main(){
    while(cin>>n){
        for(int i=0;i<=9;i++)a[i]=n;
        int cnt=1;
        while(true){
            if(work(cnt)){
                cnt++;
            }
            else{
                break;
            }
        }
        cout<<cnt-1<<endl;//注意減1.
        //3181
    }
    return 0;
}

• 答案

  3181 3181 3181

第三題 直線

• 問題描述

  在平面直角坐標系中，兩點可以確定一條直線，如果有多點在一條直線上，那么這些點中任意兩點確定的直線是同一條，給定平面上 2 × 3 2 × 3 2×3個整點 ( x , y ) ∣ 0 ≤ x < 2 , 0 ≤ y < 3 , x ∈ Z , y ∈ Z {(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x∈ Z, y ∈ Z} (x,y)∣0≤x<2,0≤y<3,x∈Z,y∈Z，即橫坐標是 0 到 1 (包含 0 和 1) 之間的整數、縱坐標是 0 0 0 到 2 2 2 (包含 0 0 0 和 2 2 2) 之間的整數的點，這些點一共確定了 11 條不同的直線，給定平面上 20 × 21 個整點 ( x , y ) ∣ 0 ≤ x < 20 , 0 ≤ y < 21 , x ∈ Z , y ∈ Z {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z} (x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z，即橫坐標是 0 0 0 到 19 19 19 (包含 0 0 0 和 19 19 19) 之間的整數、縱坐標是 0 到 20 (包含 0 0 0 和 20 20 20) 之間的整數的點，請問這些點一共確定了多少條不同的直線，

• 解題思路

  寫錯了，以為是找規律，比賽的時候推的公式為 n + m + ( n ? 1 ) ? n / 2 ? ( m ? 1 ) ? m / 2 ? 2 n+m+(n-1)*n/2*(m-1)*m/2*2 n+m+(n?1)?n/2?(m?1)?m/2?2，正確解法利用直線判重解決這道題，表示直線的方式有很多種，這里采用斜截式來表示，通set容器來判重，需要注意的一個細節就是需要避免 k = 0 k=0 k=0和 k = i n f k=inf k=inf的情況， 具體看代碼，

• 代碼

/**
  *@filename:C
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-18 14:40
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

int n,m;
struct Point{
    int x,y;
    Point(){}
    Point(int x,int y){
        this->x=x,this->y=y;
    }
};
struct Line{
    //我們通過點斜式來確定一條直線，即y=kx+b;那么判重的方法就是判斷k和b是不是相等的，
    double k,b;
    Line(){}
    Line(double k,double b){
        this->k=k,this->b=b;
    }
    //由于我們要利用set判重，故我們需要對<運算子多載，
    bool operator<(const Line &A)const {
        if(k==A.k)return b<A.b;
        return k<A.k;
    }
};
set<Line> t;
Point points[maxn];
int cnt=0;//點的個數，
void addLine(Point a1,Point a2){
    if(a1.x==a2.x||a1.y==a2.y)return;//對于k=0，或者k=無窮的情況我們不考慮，避免精度損失等問題，最后我們累加上這些即可，n+m，
    double temp=(a2.x-a1.x)*1.0;
    double k=(a2.y-a1.y)*1.0/temp;
    double b=(a1.y*a2.x-a1.x*a2.y)*1.0/temp;
    t.insert(Line(k,b));
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            points[cnt++]=Point(i,j);
        }
    }
    //接下來確定直線加入set中，
    for(int i=0;i<cnt;i++){
        for(int j=0;j<cnt;j++){
            addLine(points[i],points[j]);
        }
    }
    cout<<t.size()+n+m<<endl;
    return 0;
}

• 答案

  40257 40257 40257

第四題 貨物擺放

• 問題描述

  小藍有一個超大的倉庫，可以擺放很多貨物，現在，小藍有 n 箱貨物要擺放在倉庫，每箱貨物都是規則的正方體，小藍規定了長、寬、高三個互相垂直的方向，每箱貨物的邊都必須嚴格平行于長、寬、高，小藍希望所有的貨物最終擺成一個大的立方體，即在長、寬、高的方向上分別堆 L 、 W 、 H L、W、H L、W、H 的貨物，滿足 n = L × W × H n = L × W × H n=L×W×H，給定 n，請問有多少種堆放貨物的方案滿足要求，例如，當 n = 4 n = 4 n=4 時，有以下 6 種方案： 1 × 1 × 4 、 1 × 2 × 2 、 1 × 4 × 1 、 2 × 1 × 2 、 2 × 2 × 1 、 4 × 1 × 1 1×1×4、1×2×2、1×4×1、2×1×2、 2 × 2 × 1、4 × 1 × 1 1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1，請問，當 n = 2021041820210418 n = 2021041820210418 n=2021041820210418（注意有 16 16 16 位數字）時，總共有多少種方案？提示：建議使用計算機編程解決問題，

• 解題思路

  列舉因子，由于不同順序是不同的方案，所以我們先要假定 i ≤ j ≤ k i\leq j \leq k i≤j≤k，然后最后我們就可以對 i , j , k i,j,k i,j,k排列了，這樣所有的情況都會被考慮，而因為都不相同的時候是 6 6 6種排列，有且只有兩個相同的時候是 3 3 3種排列，都相同的時候是一種排列，所以我們需要統計滿足條件的數目 c n t 0 cnt0 cnt0、滿足條件的數目且其中有且僅有兩個相同的數目 c n t 1 cnt1 cnt1、滿足條件的數目有且僅有三個相同的數目 c n t 2 cnt2 cnt2，最后答案即是 c n t 0 × 6 ? c n t 1 × 3 ? c n t 2 × 5 cnt0\times 6-cnt1\times 3 - cnt2\times 5 cnt0×6?cnt1×3?cnt2×5，

• 代碼

/**
  *@filename:B
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-18 14:28
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

ll n;
void solve(){
}
int main(){
    while(cin>>n){
        int cnt0=0,cnt1=0,cnt2=0;//cnt0統計所有情況，cnt1統計兩個數相等的情況，cnt2統計三個數相等的情況
        for(ll i=1;i*i*i<=n;i++){
            if(n%i)continue;
            for(ll j=i;i*j*j<=n;j++){
                if(n%j)continue;
                ll k=n/(i*j);
                if(i*j*k==n){
                    cnt0++;
                    if(i==j&&j==k){
                        cnt2++;
                    }
                    else if(i==j||j==k||i==k){
                        cnt1++;
                    }
                }
            }
        }
        cout<<cnt0<<" "<<cnt1<<" "<<cnt2<<endl;//406 2 0
        //不相等6種排列，只有兩個相等三種排列，三個相等一種排列，
        cout<<cnt0*6-cnt1*3-cnt2*5<<endl;//2430
    }
    solve();
    return 0;
}

• 答案

  2430 2430 2430

第五題 路徑

• 問題描述

  小藍學習了最短路徑之后特別高興，他定義了一個特別的圖，希望找到圖中的最短路徑，小藍的圖由 2021 2021 2021 個結點組成，依次編號 1 1 1 至 2021 2021 2021，對于兩個不同的結點 a , b a, b a,b，如果 a a a 和 b b b 的差的絕對值大于 21 21 21，則兩個結點之間沒有邊相連；如果 a a a 和 b b b 的差的絕對值小于等于 21 21 21，則兩個點之間有一條長度為 a a a 和 b b b 的最小公倍數的無向邊相連，例如：結點 1 1 1 和結點 23 23 23 之間沒有邊相連；結點 3 3 3 和結點 24 24 24 之間有一條無向邊，長度為 24 24 24；結點 15 15 15 和結點 25 25 25 之間有一條無向邊，長度為 75 75 75，請計算，結點 1 1 1 和結點 2021 2021 2021 之間的最短路徑長度是多少，提示：建議使用計算機編程解決問題，

• 解題思路

  最短路模板題，本題我采用 d i j k s t r a dijkstra dijkstra演算法實作的，

• 代碼

/**
  *@filename:E
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-18 14:50
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 10000 + 5;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;

//最短路板子題，
int n;
int g[maxn][maxn];
int dist[maxn];
bool vis[maxn];
int gcd(int n,int m){
    return n%m?gcd(m,n%m):m;
}
void init(){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(abs(i-j)<=21){
                g[i][j]=g[j][i]=i*j/gcd(i,j);
            }
            else{
                g[i][j]=g[j][i]=inf;
            }
        }
    }
}
void dijkstra(int st){
    for(int i=1;i<=n;i++){
        dist[i]=g[st][i];
    }
    vis[st]=true;
    for(int i=1;i<=n;i++){
        int minn=inf,index;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&dist[j]<minn){
                minn=dist[j];
                index=j;
            }
        }
        if(minn==inf)break;
        vis[index]=true;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&dist[j]>dist[index]+g[index][j]){
                dist[j]=dist[index]+g[index][j];
            }
        }
    }
    cout<<dist[n]<<endl;//n=2021 print:10266837
}
void solve(){
    init();
    dijkstra(1);
}
int main(){
    while(cin>>n){
        solve();
    }
    return 0;
}

• 答案

  10266837 10266837 10266837

程式題

第六題 時間顯示

• 問題描述

  小藍要和朋友合作開發一個時間顯示的網站，在服務器上，朋友已經獲取了當前的時間，用一個整數表示，值為從 1970 1970 1970 年 1 1 1 月 1 1 1 日 00 : 00 : 00 00:00:00 00:00:00到當前時刻經過的毫秒數，現在，小藍要在客戶端顯示出這個時間，小藍不用顯示出年月日，只需要顯示出時分秒即可，毫秒也不用顯示，直接舍去即可，給定一個用整數表示的時間，請將這個時間對應的時分秒輸出，

  【輸入格式】

  輸入一行包含一個整數，表示時間，

  【輸出格式】

  輸出時分秒表示的當前時間，格式形如 H H : M M : S S HH:MM:SS HH:MM:SS，其中 H H HH HH 表示時，值為 0 0 0 到 23 23 23， M M MM MM 表示分，值為 0 0 0 到 59 59 59， S S SS SS 表示秒，值為 0 0 0 到 59 59 59，時、分、秒

  不足兩位時補前導 0 0 0，

  【樣例輸入 1】

  46800999 46800999 46800999

  【樣例輸出 1】

  13 : 00 : 00 13:00:00 13:00:00

  【樣例輸入 2】

  1618708103123 1618708103123 1618708103123

  【樣例輸出 2】

  01 : 08 : 23 01:08:23 01:08:23

  【評測用例規模與約定】

  對于所有評測用例，給定的時間為不超過 1018 的正整數，

• 解題思路

  水題，轉換時間，注意： 1 s = 1000 m s 1s=1000ms 1s=1000ms，

• AC代碼

/**
  *@filename:F
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-18 14:57
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

ll n;
void solve(){
    n/=1000;
    printf("%02d:%02d:%02d\n",(n%(24*3600))/3600,n%3600/60,n%60);
}
int main(){
    while(cin>>n){
        solve();
    }
    return 0;
}

第七題 砝碼稱重

• 問題描述

  你有一架天平和 N N N 個砝碼，這 N N N個砝碼重量依次是 W 1 , W 2 , ? ? ? , W N W_1, W_2, · · · , W_N W1?,W2?,???,WN?，請你計算一共可以稱出多少種不同的重量？注意砝碼可以放在天平兩邊，

  【輸入格式】

  輸入的第一行包含一個整數 N N N，

  第二行包含 N N N 個整數： W 1 , W 2 , W 3 , ? ? ? , W N W_1, W_2, W_3, · · · , W_N W1?,W2?,W3?,???,WN?，

  【輸出格式】

  輸出一個整數代表答案，

  【樣例輸入】

  3

  1 4 6

  【樣例輸出】

  10

  【樣例說明】

  能稱出的 10 種重量是：1、2、3、4、5、6、7、9、10、11，

  1 = 1；

  2 = 6 ? 4 (天平一邊放 6，另一邊放 4)；

  3 = 4 ? 1；

  4 = 4；

  5 = 6 ? 1；

  6 = 6；

  7 = 1 + 6；

  9 = 4 + 6 ? 1；

  10 = 4 + 6；

  11 = 1 + 4 + 6，

  【評測用例規模與約定】

  對于 50% 的評測用例， 1 ≤ N ≤ 15 1 ≤ N≤ 15 1≤N≤15，

  對于所有評測用例， 1 ≤ N ≤ 100 1 ≤ N ≤ 100 1≤N≤100， N N N 個砝碼總重不超過 100000 100000 100000，

• 解題思路

  我們可以先來定義一下，我們總認為稱出的重量為左邊減右邊，也就是說如果要增加就放左邊，如果要減少就放右邊，否則不放，

  這種決策問題一看就是 d p dp dp了，然而比賽的時候也還是不知道該怎么處理，于是用dfs列舉，能過一半的樣例，
  補題：看了大佬的寫法，確實是背包問題的變種，三種決策，不過這個題我們不是用 m a x max max來判斷，因為我們只關心能否湊成，所以只需要累加之前的狀態即可，
  還有一種解法是利用 s e t set set來寫的，暫時不能理解，不過也貼出來供大家參考，

• d f s dfs dfs撿分代碼

/**
  *@filename:G
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-18 15:15
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

//
int n;
int w[maxn];
int cnt[maxn];
int sum;
void dfs(int step,int ans){
    //step表示當前正在選擇的砝碼，ans為左邊減右邊的重量，
    if(step==n+1){
        //說明前n個已經選完了，
        if(ans<=0)return;
        cnt[ans]++;
        return;
    }
    dfs(step+1,ans+w[step]);//放左邊，
    dfs(step+1,ans);//不放，
    dfs(step+1,ans-w[step]);//放右邊，
}
void solve(){
    dfs(1,0);
    int ans=0;
    for(int i=1;i<=sum;i++){
        if(cnt[i]>0)ans++;
    }
    cout<<ans<<endl;
}
int main(){
    cin>>n;
    sum=0;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        sum+=w[i];
    }
    solve();
    return 0;
}

• 動態規劃解題代碼

/**
  *@filename:G砝碼稱重背包問題變種
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-19 18:55
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

//背包dp，累加三種方案數即可，
int n;
int w[105];
int dp[105][maxn<<2];//dp[i][j]表示的即是前i個砝碼中能湊成重量j的方案數，
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>w[i];
	//由于我們在進行決策的時候會出現負數，所以我們需要將陣列進行偏移一個maxn確保列舉的時候不會出現錯誤，
	dp[0][maxn]=1;//注意設立起始值作為更新點，
	for(int i=1;i<=n;i++){
		for(int j=-maxn+w[i];j<=maxn;j++){
			//從小到大開始列舉，
			//不選，加上，減去三種決策，
			dp[i][j+maxn]=dp[i-1][j+maxn]+dp[i-1][j+maxn+w[i]]+dp[i-1][j+maxn-w[i]];
		}
	}
	int ans=0;//累加所有出現的狀態，
	for(int j=maxn+1;j<=maxn*2;j++){
		if(dp[n][j])ans++;
	}
	cout<<ans<<endl;
	return 0;
}

• s e t set set容器判重處理代碼

/**
  *@filename:G砝碼稱重利用set巧解
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-19 21:13
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

int n,w[105];
set<int> t1,t2;
int sum;
bool vis[maxn];//判斷是否出現，
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    t1.insert(0),t2.insert(0);//以它們作為更新點，
    for(int i=1;i<=n;i++){
        //每次加入一個元素進去，
        for(auto &x:t1){
            t2.insert(x+w[i]);
            t2.insert(x-w[i]);
        }
        t1=t2;
    }
    for(auto &x:t1){
        vis[abs(x)]=true;
    }
    int ans=0;
    for(int i=1;i<=maxn;i++){
        if(vis[i])ans++;
    }
    cout<<ans<<endl;
    return 0;
}

第八題 楊輝三角形

• 問題描述

  下面的圖形是著名的楊輝三角形：

  

  如果我們按從上到下、從左到右的順序把所有數排成一列，可以得到如下數列：

  1 , 1 , 1 , 1 , 2 , 1 , 1 , 3 , 3 , 1 , 1 , 4 , 6 , 4 , 1 , . . . 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ... 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,...

  給定一個正整數 N N N，請你輸出數列中第一次出現 N N N 是在第幾個數？

  【輸入格式】

  輸入一個整數 N ， N， N，

  【輸出格式】

  輸出一個整數代表答案，

  【樣例輸入】

  6

  【樣例輸出】

  13

  【評測用例規模與約定】

  對于 20% 的評測用例， 1 ≤ N ≤ 10 1 ≤ N≤ 10 1≤N≤10；

  對于所有評測用例， 1 ≤ N ≤ 1000000000 1 ≤N ≤ 1000000000 1≤N≤1000000000，

• 解題思路

  楊輝三角第 i i i行第 j j j列的數為 C i ? 1 j ? 1 C_{i-1}^{j-1} Ci?1j?1?，那么我們直接列舉 i , j i,j i,j即可，不過有一個坑點，比賽的時候沒想到，就是 C n 1 C_{n}^1 Cn1?的時候，需要列舉 O ( n 2 ) O(n^2) O(n2)，沒有想到，哎，只能過的 20 % 20\% 20%的分，

• 代碼

/**
  *@filename:H
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-18 15:00
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

ll C(ll n,ll m){
    ll ans=1;
    for(ll i=n,j=1;i>=(n-m+1);i--,j++){
        ans=ans*i/j;
    }
    return ans;
}
ll n;
void solve(){
    if(n==1){
        cout<<1<<endl;
        return;
    }
    bool flag=false;
    for(ll i=3;;i++){
        for(ll j=1;j<i;j++){
            if(C(i-1,j)==n){
                flag=true;
                cout<<(i-1)*i/2+j+1<<endl;//不過好像沒考慮n特別大的時候，，，即跑1e9*1e9跑不出，
                break;
            }
        }
        if(flag)break;
    }
}
int main(){
    while(cin>>n){
        solve();
    }
    return 0;
}

第九題 雙向排序

• 問題描述

  給定序列 ( a 1 , a 2 , ? ? ? , a n ) = ( 1 , 2 , ? ? ? , n ) a_1, a_2, · · · , a_n) = (1, 2, · · · , n) a1?,a2?,???,an?)=(1,2,???,n)，即 a i = i a_i = i ai?=i，小藍將對這個序列進行 m m m 次操作，每次可能是將 a 1 , a 2 , ? ? ? , a q i a_1, a_2, · · · , a_{q_i} a1?,a2?,???,aqi?? 降序排列，或者將 a q i , a q i + 1 , ? ? ? , a n a_{q_i},a_{q_{i+1}}, ···,a_n aqi??,aqi+1??,???,an? 升序排列，請求出操作完成后的序列，

  【輸入格式】

  輸入的第一行包含兩個整數 n , m n, m n,m，分別表示序列的長度和操作次數，

  接下來 m m m 行描述對序列的操作，其中第 i i i 行包含兩個整數 p i , q i p_i, q_{i} pi?,qi? 表示操作型別和引數，當 p i p_i pi? = 0 時，表示將 a 1 , a 2 , ? ? ? , a q i a_1, a_2, · · · , a_{q_i} a1?,a2?,???,aqi?? 降序排列；當 p i = 1 p_i = 1 pi?=1 時，表示將 a q i , a q i + 1 , ? ? ? , a n a_{q_i} , a_{q_{i+1}}, · · · , a_n aqi??,aqi+1??,???,an? 升序排列，

  【輸出格式】
  輸出一行，包含 n n n 個整數，相鄰的整數之間使用一個空格分隔，表示操作完成后的序列，

  【樣例輸入】

  3 3

  0 3

  1 2

  0 2

  【樣例輸出】

  3 1 2

  【樣例說明】

  原數列為 (1, 2, 3)，

  第 1 步后為 (3, 2, 1)，

  第 2 步后為 (3, 1, 2)，

  第 3 步后為 (3, 1, 2)，與第 2 步操作后相同，因為前兩個數已經是降序了，

  【評測用例規模與約定】

  對于 30% 的評測用例， n , m ≤ 1000 n, m ≤ 1000 n,m≤1000；

  對于 60% 的評測用例， n , m ≤ 5000 n, m ≤ 5000 n,m≤5000；

  對于所有評測用例， 1 ≤ n , m ≤ 100000 ， 0 ≤ p i ≤ 1 ， 1 ≤ q i ≤ n 1 ≤ n, m ≤ 100000，0 ≤ p_i ≤ 1，1 ≤ q_i ≤ n 1≤n,m≤100000，0≤pi?≤1，1≤qi?≤n，

• 解題思路

  有點線段樹的味道，但不知道怎么處理，所以只能暴力出奇跡了，能過 60 % 60\% 60%的資料，

• 代碼

/**
  *@filename:I
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-18 15:58
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

int n,m;
int main(){
    while(cin>>n>>m){
        vector<int> a(n);
        for(int i=0;i<n;i++)a[i]=i+1;
        int p,q;
        while(m--){
            cin>>p>>q;
            if(p)sort(a.begin()+q-1,a.end());
            else sort(a.begin(),a.begin()+q,greater<int>() );
        }
        for(int i=0;i<n;i++){
            cout<<a[i];
            i==n-1?cout<<endl:cout<<" ";
        }
    }
    return 0;
}

第十題 括號序列

• 問題描述

  給定一個括號序列，要求盡可能少地添加若干括號使得括號序列變得合法，當添加完成后，會產生不同的添加結果，請問有多少種本質不同的添加結果，兩個結果是本質不同的是指存在某個位置一個結果是左括號，而另一個是右括號，例如，對于括號序列 ((()，只需要添加兩個括號就能讓其合法，有以下幾種不同的添加結果：()()()、()(())、(())()、(()()) 和 ((()))，

  【輸入格式】

  輸入一行包含一個字串 s s s，表示給定的括號序列，序列中只有左括號和右括號，

  【輸出格式】

  輸出一個整數表示答案，答案可能很大，請輸出答案除以 1000000007 1000000007 1000000007(即 1 0 9 + 7 10^9 + 7 109+7) 的余數，

  【樣例輸入】

  ((()

  【樣例輸出】

  5

  【評測用例規模與約定】

  對于 40% 的評測用例， ∣ s ∣ ≤ 200 |s| ≤ 200 ∣s∣≤200，

  對于所有評測用例， 1 ≤ ∣ s ∣ ≤ 5000 1 ≤ |s| ≤ 5000 1≤∣s∣≤5000，

• 解題思路

  持續懵逼中，偷分都不知道怎么偷，待補，

• 代碼

總結

難度適中，梯度明顯，整體還算OK，待結果出來還愿，希望能取得一個不錯的結果，