2024常州day4(8.15)(补

1.这是一篇在8.16号写的blog
Because昨天没有晚自习！！

步入正题

1.队列

• STL队列操作
  定义队列：queue q;
  队头：q.front()
  队尾：q.back()
  弹出（出队）：q.pop()
  入队： q.push(x)
  判断队列是否为空：q.empty()
  例题：新约瑟夫问题（围圈报数）

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
queue<int> q;
int main()
{
    int v=1;
    cin>>n>>m;
    for(int i=1;i<=n;i++) q.push(i);
    while(!q.empty())
    {
        if(v==m)
        {
            cout<<q.front()<<" ";
            q.pop();
            v=1;
        }
        else
        {
            v++;
            q.push(q.front());
            q.pop();
        }
    }

    return 0;
}

• 单调队列
  这个东西在聚龙学过
  单调队列是一种存储数据的队列，其中元素的顺序是单调递增或单调递减的。一般使用两个单调队列，分别维护单调递增和递减序列。
  注意：单调队列是一个双端队列（两边均可以进队出队）。
  最典型的题目是滑动窗口
  没时间了，代码就不打了

2.BFS 宽搜

很早就学过了
但是我还是更喜欢DFS

例题：猴群（有多少细胞）

#include<bits/stdc++.h>
using namespace std;
int n,m,sum,a[110][110];
char c;
int xi[5]={0,1,-1,0,0};
int yi[5]={0,0,0,1,-1};
void bfs(int x,int y)
{
    int new_x,new_y,tail,front;
    int q[1000][3];
    sum++;a[x][y]=&#039;0&#039;;front=1;tail=1;
    q[1][1]=x;q[1][2]=y;
    do
    {   
        for(int i=1;i<=4;i++)
        {
            new_x=q[front][1]+xi[i];
            new_y=q[front][2]+yi[i];
            if(new_x>=1 && new_x<=n && new_y>=1 && new_y<=m && a[new_x][new_y]==1)
            {
                tail++;
                q[tail][1]=new_x;
                q[tail][2]=new_y;
                a[new_x][new_y]=&#039;0&#039;;
            }
        }
        front++;
    }while(front<=tail);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>c;
            if(c>=&#039;1&#039; && c<=&#039;9&#039;) a[i][j]=1;
        }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==1) bfs(i,j);
        }
    }   
    cout<<sum;
    return 0;
}

啥也不是的东西

昨天（8.15）号去了青果巷，真的是中看不中用
拍照特好看，但是啥都没有
（不明白为什么傍晚那么多人）