蓝桥杯2023什么时候开始发通知了吗？
每年大概什么时候开始？
bfs做法
#include<bits/stdc++.h>
using namespace std;
struct manCow
{
int x;//坐标
int deep;//时间
};
queue<manCow> q;
bool flags[100010];//标记该点是否走过，否则会MLE
void bfs(int x, int y)
{
manCow f;
f.x = x;
f.deep = 0;
flags[f.x] = 1;
q.push(f);//入队
while(!q.empty())
{
f = q.front();
q.pop();
if(f.x == y)//退出条件
{
cout << f.deep << endl;
return;
}
manCow fn;
fn.deep = f.deep + 1;//更新时间
if(f.x > y)
{
fn.x = f.x - 1;
if(fn.x >= 0 && fn.x <= 100000)//一定要有， 否则RE
{
if(flags[fn.x] != 1)
{
flags[fn.x] = 1;
q.push(fn);
}
}
}
else
{
for(int i = 0;i < 3;i++)
{
if(i == 0)
fn.x = f.x + 1;
if(i == 1)
fn.x = f.x - 1;
if(i == 2)
fn.x = 2 * f.x;//新的坐标
if(fn.x >= 0 && fn.x <= 100000)
{
if(flags[fn.x] != 1)
{
flags[fn.x] = 1;
q.push(fn);
}
}
}
}
}
}
int main()
{
int fx, cx;
cin >> fx >> cx;
bfs(fx, cx);
return 0;
}
问题
蒟蒻求助
Acwing.1100抓住那头牛
用bfs如何做？
下附MLE代码
#include<bits/stdc++.h>
using namespace std;
struct manCow
{
int x;
int deep;
};
queue<manCow> q;
void bfs(int x, int y)
{
manCow f;
f.x = x;
f.deep = 0;
q.push(f);
while(!q.empty())
{
f = q.front();
if(f.x == y)
{
cout << f.deep << endl;
return;
}
manCow fn;
fn.deep = f.deep + 1;
if(f.x > y)
{
fn.x = f.x - 1;
q.push(fn);
}
else
{
for(int i = 0;i < 3;i++)
{
if(i == 0)
fn.x = f.x + 1;
if(i == 1)
fn.x = f.x - 1;
if(i == 2)
fn.x = 2 * f.x;
q.push(fn);
}
}
q.pop();
}
}
int main()
{
int fx, cx;
cin >> fx >> cx;
bfs(fx, cx);
return 0;
}
bfs 做法
#include<bits/stdc++.h>
using namespace std;
int n, m;
char field[101][101];
int ans = 0;
struct point
{
int x;
int y;
};
queue<point> q;
void bfs(int x, int y)
{
point p1;
p1.x = x;
p1.y = y;
q.push(p1);
while(!q.empty())
{
for(int i = -1;i <= 1;i++)
{
for(int j = -1;j <= 1;j++)
{
int ny = q.front().y + j;
int nx = q.front().x + i;
if(nx >= 0 && nx < n
&& ny >= 0 && ny < m
&& field[nx][ny] == 'W')
{
field[nx][ny] = '.';
point p2;
p2.x = nx;
p2.y = ny;
q.push(p2);
}
}
}
q.pop();
}
}
int main()
{
cin >> n >> m;
for(int i = 0;i < n;i++)
{
for(int j = 0;j < m;j++)
{
cin >> field[i][j];
}
}
for(int i = 0;i < n;i++)
{
for(int j = 0;j < m;j++)
{
if(field[i][j] == 'W')
{
bfs(i, j);
ans++;
}
}
}
cout << ans << endl;
return 0;
}
dfs做法
#include<bits/stdc++.h>
using namespace std;
int n, m;
char field[101][101];
int ans = 0;
void dfs(int x, int y)
{
for(int i = -1;i <= 1;i++)
{
for(int j = -1;j <= 1;j++)
{
int ny = y + j;
int nx = x + i;
if(nx >= 0 && nx < n
&& ny >= 0 && ny < m
&& field[nx][ny] == 'W')
{
field[nx][ny] = '.';
dfs(nx, ny);
}
}
}
return;
}
int main()
{
cin >> n >> m;
for(int i = 0;i < n;i++)
{
for(int j = 0;j < m;j++)
{
cin >> field[i][j];
}
}
for(int i = 0;i < n;i++)
{
for(int j = 0;j < m;j++)
{
if(field[i][j] == 'W')
{
dfs(i, j);
ans++;
}
}
}
cout << ans << endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 20123;
struct hulk
{
int j;
int x;
};
int num[10001] = {0};
hulk o[10001][101];//存储n,m,个人比较喜用结构体
int main()
{
int n, m, st;
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
for(int j = 0;j < m;j++)
{
cin >> o[i][j].j >> o[i][j].x;
if(o[i][j].j == 1)
num[i]++;//统计每层梯子数量
}
}
cin >> st;
int ans = 0;
for(int i = 1;i <= n;i++)
{
ans += o[i][st].x;//密钥
int tmp = o[i][st].x % num[i];//利用周期性，x取模每层的梯子数，不然5个T
if(!tmp)
{
tmp = num[i];//余数为0特殊处理
}
for(int j = st;;j++)//循环找即可
{
if(o[i][j].j == 1)
tmp--;
if(!tmp)
{
st = j;//更新st
break;
}
if(j == m - 1)
j = -1;
}
}
cout << ans % N<< endl;//取模不要忘， wo因为这个调了半小时
return 0;
}
活动打卡代码
AcWing 4455. 出行计划
1、首先说前面相乘是什么情况–GGGHGGGG，比如这样的情况的牛，左边取1头G右边取1头加上中间H，就组成了GHG，这就是一个孤独的牛，需要删掉，然后右边取到GGGG都是一样，可以组成孤独的牛，然后在左边取两头，右边全部取，这样就是两个数的乘积的结果，
2、然后加上左边 - 1的长度，需要满足长度是3，所以左边是GGGH，左边不同的牛长度是3，你不能直接就取3，要留出一个组成跟中间点组成GH来达到长度是3，所以就是左边剩下两头G，取一头跟两头可以组成两种情况 ，就有G+GH ， GG + GH，这样两种情况就是左边长度 - 1；
3、右边同理
import java.util.*;
import java.io.*;
public class Main{
static int N = 500010;
static char[] g = new char[N];//存储所有牛
public static void main(String[] args)throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
Scanner scan = new Scanner(System.in);
int n = Integer.parseInt(bf.readLine());//输入n
g = bf.readLine().toCharArray();//输入所有牛
long res = 0;
for (int i = 0 ; i < n ; i ++){ //枚举所有牛
int lhs = 0; //当前这头牛的左边不同的连续的牛
//i > 0保证了左边这头牛，如果是=0，那么左边没有牛
//并且左边跟他不相等的数的长度
if (i > 0 && g[i] != g[i - 1]){
lhs ++;
//然后看左边最长不超过边界的最长的不同的牛
for (int j = i - 2;j >= 0 && g[j] != g[i]; j -- ) lhs ++;
}
int rhs = 0;//当前这头牛的右边不同的连续的牛
//i + 1 < n 保证了右边这头牛，如果是>n，那么右边超过边界没有牛
//并且右边跟他不相等的数的长度
if (i + 1 < n && g[i + 1] != g[i]){
rhs ++;
//然后看右边最长不超过边界的最长的不同的牛
for (int j = i + 2 ; j < n && g[j] != g[i]; j ++) rhs ++;
}
//每次累加所有的牛的应该扔掉的孤独照片
//左边跟右边的所有点都可以跟中间当前点组成
//（左边长度*右边长度 + 左边的长度 - 1 + 右边的长度 - 1）
///为什么左边减1呢，因为长度最低是3，所以要留出 一个当前点跟左边一个点，
//然后跟左边其他点组成3以上的长度，右边同理
res += (long)lhs * rhs + (long)Math.max(0,lhs - 1) + (long)Math.max(0,rhs - 1);
}
System.out.println(res);
wt.flush();
}
}
活动打卡代码
AcWing 4510. 寻宝！大冒险！
1、首先说前面相乘是什么情况–GGGHGGGG，比如这样的情况的牛，左边取1头G右边取1头加上中间H，就组成了GHG，这就是一个孤独的牛，需要删掉，然后右边取到GGGG都是一样，可以组成孤独的牛，然后在左边取两头，右边全部取，这样就是两个数的乘积的结果，
2、然后加上左边 - 1的长度，需要满足长度是3，所以左边是GGGH，左边不同的牛长度是3，你不能直接就取3，要留出一个组成跟中间点组成GH来达到长度是3，所以就是左边剩下两头G，取一头跟两头可以组成两种情况 ，就有G+GH ， GG + GH，这样两种情况就是左边长度 - 1；
3、右边同理
import java.util.*;
import java.io.*;
public class Main{
static int N = 500010;
static char[] g = new char[N];//存储所有牛
public static void main(String[] args)throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
Scanner scan = new Scanner(System.in);
int n = Integer.parseInt(bf.readLine());//输入n
g = bf.readLine().toCharArray();//输入所有牛
long res = 0;
for (int i = 0 ; i < n ; i ++){ //枚举所有牛
int lhs = 0; //当前这头牛的左边不同的连续的牛
//i > 0保证了左边这头牛，如果是=0，那么左边没有牛
//并且左边跟他不相等的数的长度
if (i > 0 && g[i] != g[i - 1]){
lhs ++;
//然后看左边最长不超过边界的最长的不同的牛
for (int j = i - 2;j >= 0 && g[j] != g[i]; j -- ) lhs ++;
}
int rhs = 0;//当前这头牛的右边不同的连续的牛
//i + 1 < n 保证了右边这头牛，如果是>n，那么右边超过边界没有牛
//并且右边跟他不相等的数的长度
if (i + 1 < n && g[i + 1] != g[i]){
rhs ++;
//然后看右边最长不超过边界的最长的不同的牛
for (int j = i + 2 ; j < n && g[j] != g[i]; j ++) rhs ++;
}
//每次累加所有的牛的应该扔掉的孤独照片
//左边跟右边的所有点都可以跟中间当前点组成
//（左边长度*右边长度 + 左边的长度 - 1 + 右边的长度 - 1）
///为什么左边减1呢，因为长度最低是3，所以要留出 一个当前点跟左边一个点，
//然后跟左边其他点组成3以上的长度，右边同理
res += (long)lhs * rhs + (long)Math.max(0,lhs - 1) + (long)Math.max(0,rhs - 1);
}
System.out.println(res);
wt.flush();
}
}
活动打卡代码
AcWing 3422. 左孩子右兄弟
1、首先说前面相乘是什么情况–GGGHGGGG，比如这样的情况的牛，左边取1头G右边取1头加上中间H，就组成了GHG，这就是一个孤独的牛，需要删掉，然后右边取到GGGG都是一样，可以组成孤独的牛，然后在左边取两头，右边全部取，这样就是两个数的乘积的结果，
2、然后加上左边 - 1的长度，需要满足长度是3，所以左边是GGGH，左边不同的牛长度是3，你不能直接就取3，要留出一个组成跟中间点组成GH来达到长度是3，所以就是左边剩下两头G，取一头跟两头可以组成两种情况 ，就有G+GH ， GG + GH，这样两种情况就是左边长度 - 1；
3、右边同理
import java.util.*;
import java.io.*;
public class Main{
static int N = 500010;
static char[] g = new char[N];//存储所有牛
public static void main(String[] args)throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
Scanner scan = new Scanner(System.in);
int n = Integer.parseInt(bf.readLine());//输入n
g = bf.readLine().toCharArray();//输入所有牛
long res = 0;
for (int i = 0 ; i < n ; i ++){ //枚举所有牛
int lhs = 0; //当前这头牛的左边不同的连续的牛
//i > 0保证了左边这头牛，如果是=0，那么左边没有牛
//并且左边跟他不相等的数的长度
if (i > 0 && g[i] != g[i - 1]){
lhs ++;
//然后看左边最长不超过边界的最长的不同的牛
for (int j = i - 2;j >= 0 && g[j] != g[i]; j -- ) lhs ++;
}
int rhs = 0;//当前这头牛的右边不同的连续的牛
//i + 1 < n 保证了右边这头牛，如果是>n，那么右边超过边界没有牛
//并且右边跟他不相等的数的长度
if (i + 1 < n && g[i + 1] != g[i]){
rhs ++;
//然后看右边最长不超过边界的最长的不同的牛
for (int j = i + 2 ; j < n && g[j] != g[i]; j ++) rhs ++;
}
//每次累加所有的牛的应该扔掉的孤独照片
//左边跟右边的所有点都可以跟中间当前点组成
//（左边长度*右边长度 + 左边的长度 - 1 + 右边的长度 - 1）
///为什么左边减1呢，因为长度最低是3，所以要留出 一个当前点跟左边一个点，
//然后跟左边其他点组成3以上的长度，右边同理
res += (long)lhs * rhs + (long)Math.max(0,lhs - 1) + (long)Math.max(0,rhs - 1);
}
System.out.println(res);
wt.flush();
}
}
活动打卡代码
AcWing 4728. 乘方
1、首先说前面相乘是什么情况–GGGHGGGG，比如这样的情况的牛，左边取1头G右边取1头加上中间H，就组成了GHG，这就是一个孤独的牛，需要删掉，然后右边取到GGGG都是一样，可以组成孤独的牛，然后在左边取两头，右边全部取，这样就是两个数的乘积的结果，
2、然后加上左边 - 1的长度，需要满足长度是3，所以左边是GGGH，左边不同的牛长度是3，你不能直接就取3，要留出一个组成跟中间点组成GH来达到长度是3，所以就是左边剩下两头G，取一头跟两头可以组成两种情况 ，就有G+GH ， GG + GH，这样两种情况就是左边长度 - 1；
3、右边同理
import java.util.*;
import java.io.*;
public class Main{
static int N = 500010;
static char[] g = new char[N];//存储所有牛
public static void main(String[] args)throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
PrintWriter wt = new PrintWriter(new OutputStreamWriter(System.out));
Scanner scan = new Scanner(System.in);
int n = Integer.parseInt(bf.readLine());//输入n
g = bf.readLine().toCharArray();//输入所有牛
long res = 0;
for (int i = 0 ; i < n ; i ++){ //枚举所有牛
int lhs = 0; //当前这头牛的左边不同的连续的牛
//i > 0保证了左边这头牛，如果是=0，那么左边没有牛
//并且左边跟他不相等的数的长度
if (i > 0 && g[i] != g[i - 1]){
lhs ++;
//然后看左边最长不超过边界的最长的不同的牛
for (int j = i - 2;j >= 0 && g[j] != g[i]; j -- ) lhs ++;
}
int rhs = 0;//当前这头牛的右边不同的连续的牛
//i + 1 < n 保证了右边这头牛，如果是>n，那么右边超过边界没有牛
//并且右边跟他不相等的数的长度
if (i + 1 < n && g[i + 1] != g[i]){
rhs ++;
//然后看右边最长不超过边界的最长的不同的牛
for (int j = i + 2 ; j < n && g[j] != g[i]; j ++) rhs ++;
}
//每次累加所有的牛的应该扔掉的孤独照片
//左边跟右边的所有点都可以跟中间当前点组成
//（左边长度*右边长度 + 左边的长度 - 1 + 右边的长度 - 1）
///为什么左边减1呢，因为长度最低是3，所以要留出 一个当前点跟左边一个点，
//然后跟左边其他点组成3以上的长度，右边同理
res += (long)lhs * rhs + (long)Math.max(0,lhs - 1) + (long)Math.max(0,rhs - 1);
}
System.out.println(res);
wt.flush();
}
}
