1點(diǎn)下訓(xùn)總結(jié)一下前兩天學(xué)的部分。

?？蚒CF Local Programming Contest Round 1A?C題

題目：

代碼：C（web1)

#include<bits/stdc++.h>

using namespace std;

long long n, t, a, lt, rt, ans;

map<long long, int>pos, cnt;

int main()

{

cin >> n;

for(rt; rt < n; rt++)

{

cin >> a;

if(cnt[a]++)

lt=max(lt, pos[a]+1LL);

pos[a]=rt;ans+=rt-lt+1;

}

cout << ans;

}

這題大概思路就是從最后開始向前數(shù)，碰到第一個(gè)重復(fù)及停止，轉(zhuǎn)換為程序大概的意思是，如果n個(gè)元素沒有重復(fù)則為n+(n-1)+(n-2)........+1,那么現(xiàn)在有重復(fù)了如何？那么就以在此點(diǎn)的n0減去重復(fù)前的個(gè)數(shù)及代碼中的rt-lt因?yàn)槭菑牧汩_始，所以+1及：rt-lt+1。其中rt是元素原本位置lt是碰到第一個(gè)重復(fù)的數(shù)。

那么 如何標(biāo)出第一個(gè)重復(fù)的數(shù)呢？map——pos, cnt;當(dāng)輸入的a時(shí)cnt【a】++這個(gè)的意思表示a出現(xiàn)的次數(shù)，如何已經(jīng)出現(xiàn)了那么就讓lt于pos【a】+1比較選大，該怎么解釋呢。。。pos【a】是儲存最后一次出現(xiàn)的相同元素的位置的map。

比如1 2?2?4?3 5

1（0）第一次出現(xiàn) pos1= 0

2（1）第一次出現(xiàn) pos2= 1

2?（2）第二次出現(xiàn) pos2（1+1）與lt（0）比較 lt=1+1?，pos2=2，所以之后每一個(gè)元素到2位置結(jié)束前面兩個(gè)元素不用管當(dāng)2-1此位置那么之后比有2的重復(fù)。

而max的比較意義是找出最近那個(gè)相同 比如 1 ?2?1 0 2 1

之后求和輸出（比賽時(shí)只做出了兩題最簡單的那種但是還是得了個(gè)三等獎(jiǎng)）

知識：1 #include<bits/stdc++.h>包括了很多就不用打一大串include了

????????? ?2?map<long long, int>pos, cnt; map表示一個(gè)字典 前一個(gè)是key 后一個(gè)參數(shù)是value，類型可自己定義，無需聲明大小，key是唯一的，后面兩給 pos cnt 是變量?？梢陨赡０宥啻问褂茫椒ǖ綍r(shí)百度。

2 牛客50題中第一題

代碼：

#include<bits/stdc++.h>//0->A 1->B

using namespace std;

const int dx[]={1,0,-1,0,1,1,-1,-1};

const int dy[]={0,1,0,-1,1,-1,1,-1};

int n,m;

char a[1005][1005];

bool vis[2][1005][1005];

struct node{

? ? int x,y;

};

queue<node> q[2];

//

bool check_bfs(int w){

? ? int Size=q[w].size();

? ? while(Size--){

? ? ? ? int x=q[w].front().x;

? ? ? ? int y=q[w].front().y;

? ? ? ? q[w].pop();

? ? ? ? for(int k=0;k<(w?4:8);k++){

? ? ? ? ? ? int tx=x+dx[k];

? ? ? ? ? ? int ty=y+dy[k];

? ? ? ? ? ? if(tx<1 || tx>n || ty<1 || ty>m || a[tx][ty]=='#' || vis[w][tx][ty]) continue;

? ? ? ? ? ? if(vis[!w][tx][ty]) return true;

? ? ? ? ? ? q[w].push((node){tx,ty});

? ? ? ? ? ? vis[w][tx][ty]=1;

? ? ? ? }

? ? }

? ? return false;

}

int main(){

? ? cin>>n>>m;

? ? for(int i=1;i<=n;i++){

? ? ? ? for(int j=1;j<=m;j++){

? ? ? ? ? ? cin>>a[i][j];

? ? ? ? ? ? if(a[i][j]=='C'){

? ? ? ? ? ? ? ? q[0].push((node){i,j});

? ? ? ? ? ? ? ? vis[0][i][j]=1;

? ? ? ? ? ? }

? ? ? ? ? ? if(a[i][j]=='D'){

? ? ? ? ? ? ? ? q[1].push((node){i,j});

? ? ? ? ? ? ? ? vis[1][i][j]=1;

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? int tim=0;

? ? bool flag=false;

? ? while(q[0].size() || q[1].size()){

? ? ? ? flag=false;

? ? ? ? tim++;

? ? ? ? if(q[0].size() && check_bfs(0)){

? ? ? ? ? ? flag=true;

? ? ? ? ? ? break;

? ? ? ? }

? ? ? ? if(q[1].size() && check_bfs(1)){

? ? ? ? ? ? flag=true;

? ? ? ? ? ? break;

? ? ? ? }

? ? ? ? if(q[1].size() && check_bfs(1)){

? ? ? ? ? ? flag=true;

? ? ? ? ? ? break;

? ? ? ? }

? ? }

? ? if(flag){

? ? ? ? puts("YES");

? ? ? ? cout<<tim<<'\n';

? ? }

? ? else{

? ? ? ? puts("NO");

? ? }

? ? return 0;

}

因?yàn)槭乔蟛綌?shù)，所以用的是BFS，BFS是廣度優(yōu)先遍歷把第一給放進(jìn)隊(duì)列彈出來，然后壓入第一個(gè)彈出來的周圍的鏈接的路。每次循環(huán)tim+1；然后代碼寫得很漂亮，? vis[1][i][j]=1;0，1分別表示兩個(gè)點(diǎn)是否走過，如果碰到走過路徑立即結(jié)束，遍歷完都沒有碰到就no，下訓(xùn)了，干飯了。

知識點(diǎn)：

queue<node> q[2];

push(x) 將x壓入隊(duì)列的末端

pop() 彈出隊(duì)列的第一個(gè)元素(隊(duì)頂元素)，注意此函數(shù)并不返回任何值

front() 返回第一個(gè)元素(隊(duì)頂元素)

back() 返回最后被壓入的元素(隊(duì)尾元素)

empty() 當(dāng)隊(duì)列為空時(shí)，返回true

size() 返回隊(duì)列的長度

代碼例子：

1.#include <iostream>

2.#include <queue>

3.using namespace std;

4.int main()

5.{

6. int n,k;

7. cin>>n>>k;

8. int num=1;

9. queue<int> list;

10. for(int i=1;i<=n;i++)

11. list.push(i);

12. while(list.size()>1)

13. {

14. int a=list.front();

15. list.pop();

16. if(num%k!=0&&num%10!=k)

17. {

18. list.push(a);

19. }

20. num++;

21. }

22. cout<<list.front()<<endl;

23. return 0;

24.}