重走長征路---OI每周刷題記錄---11月8日 2014

總目錄詳見https://blog.csdn.net/mrcrack/article/details/84471041

做題原則，找不到測評位址的題不做。2018-11-28

重走長征路---OI每周刷題記錄---11月8日  2014

本周共計38題+題

測評位址：

樹形dp：

1.「NOIP模拟賽」LazyChild黑OJ

歐拉圖：

2.「NOIP模拟賽」世界人民大團結

字元串：

3.「NOIP模拟賽」擒賊先擒王

dp：

4.「NOIP模拟賽」機房人民大團結 

5.「NOIP模拟賽」序列問題

6.「NOIP模拟賽」改造二叉樹 

7.「NOIP模拟賽」籃球比賽1

貪心：

8.「NOIP模拟賽」盤子序列

9.「codechefFATCHEF」Remy paints the fence

10.「NOIP模拟賽」number

heap：

11.「NOIP模拟賽」點名 

12.「codechefPRPOTION」

13.Magical Girl and Colored Liquid Potions

spfa：

14.「NOIP模拟賽」長途旅行

st表+二分：

15.「NOIP模拟賽」數字對

連結清單：

16.「NOIP模拟賽」字元串

并查集：

17.「NOIP模拟賽」感冒病毒

樹狀數組：

18.「NOIP模拟賽」弱點

單調隊列：

19.「NOIP模拟賽」滑動的窗戶   //線上測評位址https://www.luogu.org/problemnew/show/P1886

dfs：

20.「NOIP模拟賽」序列問題（30分）

dfs+bfs：

21.「NOIP模拟賽」密室逃脫

dijkstra：

22.「bzoj2407」探險

dfs+背包dp：

23.「NOIP模拟賽」籃球比賽2（20分）

狀壓dp：

24.「NOIP模拟賽」籃球比賽2

數學：

25.「NOIP模拟賽」刷漆 

26.「NOIP模拟賽」數列

27.「NOIP模拟賽」median 

28.「codechefCHEFSEG」Chef and Segment Game

差分限制：

29.「NOIP模拟賽」排隊

貪心+bfs：

30.NOIP2010引水入城

二分：

31.NOIP2011聰明的質檢員

二分圖染色：

32.NOIP2008雙棧排序

乘法逆元+快速幂：

33.「NOIP模拟賽」calc

treap+hash：

34.「bzoj2761」[JLOI2011]不重複數字

模拟：

35.「codechefCHEFGR」 Chef and Ground

36.「codechefCHEFLR」Chef and Left-Right

37.「codechefPRPALN」 Let us construct palindrome

map：

38.「codechefDISCHAR」Distinct Characters Subsequence

題解：

樹形dp：

1.「NOIP模拟賽」LazyChild黑OJ

歐拉圖：

2.「NOIP模拟賽」世界人民大團結

字元串：

3.「NOIP模拟賽」擒賊先擒王

dp：

4.「NOIP模拟賽」機房人民大團結 

5.「NOIP模拟賽」序列問題

6.「NOIP模拟賽」改造二叉樹 

7.「NOIP模拟賽」籃球比賽1

貪心：

8.「NOIP模拟賽」盤子序列

9.「codechefFATCHEF」Remy paints the fence

10.「NOIP模拟賽」number

heap：

11.「NOIP模拟賽」點名 

12.「codechefPRPOTION」

13.Magical Girl and Colored Liquid Potions

spfa：

14.「NOIP模拟賽」長途旅行

st表+二分：

15.「NOIP模拟賽」數字對

連結清單：

16.「NOIP模拟賽」字元串

并查集：

17.「NOIP模拟賽」感冒病毒

樹狀數組：

18.「NOIP模拟賽」弱點

單調隊列：

19.「NOIP模拟賽」滑動的窗戶

//P1886 滑動視窗

//線上測評位址https://www.luogu.org/problemnew/show/P1886 

//針對 單調隊列 作訓練，拿該題練練手，進行回憶。 

//不斷對些錯誤進行修改，才發現，隊列的最後一個元素是q[t-1]而不是q[t]。 

//花了點時間，最小值列印成功，應該來說，隔了這麼久，能編寫成功，單調隊列掌握得不錯。 

//接下來是 最大值 的列印。 

//樣例通過，送出90分，測試點3WA。2019-4-19

//仔細想了想，忽略了了k=1的情況，馬上修改 

//測試了k=1的情況，送出AC。2019-4-19 

#include <stdio.h>

#define maxn 1000010

int n,k,a[maxn],q[maxn],h,t;//q[h]存儲位置 

int main(){

    int i;

    scanf("%d%d",&n,&k);

    for(i=1;i<=n;i++)scanf("%d",&a[i]);

    h=t=1,q[t]=1,t++;

    for(i=1;i<=n;i++){//此處寫成for(i=2;i<=n;i++)//處理最小值,數組坐标 中對應的元素自 小到大 排列 

        while(h<t&&a[q[t-1]]>=a[i])t--;//此處寫成while(h<t&&a[q[t]]>=a[i])t--;同樣是跟蹤代碼後才發現//此處寫成 while(a[q[t]]>=a[i])t--;

        q[t]=i,t++;//i位置必須加入隊列

        while(h<t&&q[t-1]-q[h]+1>k)h++;//此處寫成while(h<t&&t-h>k)h++;跟蹤了代碼才發現寫得有問題//此處寫成while(t-h>k)h++;  

        if(i>=k)printf("%d ",a[q[h]]);

    }

    printf("\n");

    h=t=1,q[t]=1,t++;

    for(i=1;i<=n;i++){//此處寫成for(i=2;i<=n;i++)//處理最大值，隊列中 數組坐标 對應的元素，自大到小排列

        while(h<t&&a[q[t-1]]<=a[i])t--;//此處寫成 while(h<t&&q[t-1]<=a[i])t--;

        q[t]=i,t++;//此處寫成 q[t]=a[i],t++;

        while(h<t&&q[t-1]-q[h]+1>k)h++;

        if(i>=k)printf("%d ",a[q[h]]); 

    }

    printf("\n");

    return 0;

}

dfs：

20.「NOIP模拟賽」序列問題（30分）

dfs+bfs：

21.「NOIP模拟賽」密室逃脫

dijkstra：

22.「bzoj2407」探險

dfs+背包dp：

23.「NOIP模拟賽」籃球比賽2（20分）

狀壓dp：

24.「NOIP模拟賽」籃球比賽2

數學：

25.「NOIP模拟賽」刷漆 

26.「NOIP模拟賽」數列

27.「NOIP模拟賽」median 

28.「codechefCHEFSEG」Chef and Segment Game

差分限制：

29.「NOIP模拟賽」排隊

貪心+bfs：

30.NOIP2010引水入城

二分：

31.NOIP2011聰明的質檢員

二分圖染色：

32.NOIP2008雙棧排序

乘法逆元+快速幂：

33.「NOIP模拟賽」calc

treap+hash：

34.「bzoj2761」[JLOI2011]不重複數字

模拟：

35.「codechefCHEFGR」 Chef and Ground

36.「codechefCHEFLR」Chef and Left-Right

37.「codechefPRPALN」 Let us construct palindrome

map：

38.「codechefDISCHAR」Distinct Characters Subsequence