2021_7_23 acm训练部分心得
1点下训总结一下前两天学的部分。
牛客UCF 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;
}
这题大概思路就是从最后开始向前数，碰到第一个重复及停止，转换为程序大概的意思是，如果n个元素没有重复则为n+(n-1)+(n-2)........+1,那么现在有重复了如何？那么就以在此点的n0减去重复前的个数及代码中的rt-lt因为是从零开始，所以+1及：rt-lt+1。其中rt是元素原本位置lt是碰到第一个重复的数。
那么 如何标出第一个重复的数呢？map——pos, cnt;当输入的a时cnt【a】++这个的意思表示a出现的次数，如何已经出现了那么就让lt于pos【a】+1比较选大，该怎么解释呢。。。pos【a】是储存最后一次出现的相同元素的位置的map。
比如1 2 2 4 3 5
1（0）第一次出现 pos1= 0
2（1）第一次出现 pos2= 1
2 （2）第二次出现 pos2（1+1）与lt（0）比较 lt=1+1 ，pos2=2，所以之后每一个元素到2位置结束前面两个元素不用管当2-1此位置那么之后比有2的重复。
而max的比较意义是找出最近那个相同 比如 1 2 1 0 2 1
之后求和输出（比赛时只做出了两题最简单的那种但是还是得了个三等奖）
知识：1 #include<bits/stdc++.h>包括了很多就不用打一大串include了
2 map<long long, int>pos, cnt; map表示一个字典 前一个是key 后一个参数是value，类型可自己定义，无需声明大小，key是唯一的，后面两给 pos cnt 是变量。可以生成模板多次使用，方法到时百度。
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;
}
因为是求步数，所以用的是BFS，BFS是广度优先遍历把第一给放进队列弹出来，然后压入第一个弹出来的周围的链接的路。每次循环tim+1；然后代码写得很漂亮， vis[1][i][j]=1;0，1分别表示两个点是否走过，如果碰到走过路径立即结束，遍历完都没有碰到就no，下训了，干饭了。
知识点：
queue<node> q[2];
push(x) 将x压入队列的末端
pop() 弹出队列的第一个元素(队顶元素)，注意此函数并不返回任何值
front() 返回第一个元素(队顶元素)
back() 返回最后被压入的元素(队尾元素)
empty() 当队列为空时，返回true
size() 返回队列的长度
代码例子：
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.}
