蓝桥杯知识点最终版

1.1.蔡基姆拉尔森计算公式

又称蔡氏公式，计算星期几的方法

蔡基姆拉尔森计算公式（Zeller's congruence），又称蔡氏公式，是一种计算星期几的方法，公式如下：

蔡基姆拉尔森计算公式（Zeller's congruence），又称蔡氏公式，是一种计算星期几的方法，公式如下：

[w = (d + 2m + 3(m + 1) \ 5 + y + y \4 - y \100 + y \400) \bmod 7]

其中：

  • (w)表示星期几（(0)代表星期日，(1)代表星期一，以此类推）；
  • (d)表示日期；
  • (m)表示月份（(3)代表三月，(4)代表四月，以此类推，把一月和二月看成上一年的(13)月和(14)月）；
  • (y)表示年份（如果是一月或二月，则是上一年的年份）。

2.DFS深度优先运算

#include <bits/stdc++.h>
using namespace std;

int n;
void dfs(int a[], int x, bool b[]) {
    if (x > n) {
        for (int i = 1; i <= n; i++) {
            cout.width(5); // 设置输出宽度为 5
            cout << a[i];
        }
        cout << endl;
    }
    for (int i = 1; i <= n; i++) {
        if (!b[i]) {
            b[i] = true;
            a[x] = i;
            dfs(a, x + 1, b);
            b[i] = false;
        }
    }
}

int main() {
    cin >> n;
    int a[10] = {0};
    bool b[10] = {false}; // 初始化布尔数组为 false
    dfs(a, 1, b);
    return 0;
}

3.空间复杂度

dfs：深度优先搜索

相当于o(n),每次都是单线先搜索，如果有n个，则复杂度为o（n）

bfs：广度优先搜索

相当于o（二的h次方），每次是一层一层搜索，第一层有1个，第二层有2个，第三层有4个

4.queue的用法

需要#include <queue>数据库提前声明，queue相当于一种特殊的数组，先进的数字排序越靠前，以下是几种用法

如：

#include <queue>
using namespace std;
int main(){
	queue<int> arr;//声明int类型的arr容器；
    int a,b,c;
  	cin>>a>>b>>c;
	arr.push(a);//输入
  	arr.push(b);
  	arr.push(c);
   	cout<<arr.front()<<endl;//输出第一个数
  	arr.pop();//去掉队列第一个，把后面的往前移一位，如输入了1，2，3，去掉队首之后，得到2，3，这个时候2为第一个
    if(arr.empty()){//如果arr里面没有东西，则为true，反之则为false；
		cout<<"空"；
	}
  	return 0;
}

5.数据库#include <utility>的用法

#include <utility>
#include <iostream>
using namespace std;
int main(){
	pair<int,int> p1;//p1可以存入两个数字，可以用作一个二维坐标，如果不说，默认为（0，0）
  	pair<int,int> p2(1,2);//p2的初始值为（1，2）
    p2.first//为x，即为1
	 p2.second//为有，即为2
  	return 0;
}

6.贪心算法：有关最优的都是它

7.只要提取出诸如（a1+a2+a3...）时候，用前缀和

8.标准库

用万能头文件#include <bits/stdc++.h>

vector<int> nums = {1, 2, 3, 4, 5};
vector<int>::iterator it;
for(it = nums.begin(); it != nums.end(); it++) {
    cout << *it << " ";  // 输出: 1 2 3 4 5
}


vector<int> v(5,2);//长度为五，所有元素都为2
v.push_back(x);//在末尾添加元素x
v.pop_back();//删除队尾元素
v.size();//返回元素个数



set<int> s;
s.insert(x);//插入元素x（插入的元素不能重复，重复了只会保留一个）
s.erase(x);//删除元素
s.count(x);//统计元素x的个数
s.size();                // 返回元素个数
s.empty();               // 判断集合是否为空，返回真则为空



map<string, int> m;        // 创建空map（前一个代表key,后一个代表value，一个map对应唯一一个value）
m[key] = value;           // 插入或修改键值对
m.erase(key);             // 删除键值对
m.count(key);             // 统计键的个数(0或1)
m.size();                 // 返回键值对个数
m.empty();               // 判断map是否为空，返回真则为空


queue<int> q;             // 创建空队列
q.push(x);               // 将x加入队尾
q.pop();                 // 删除队首元素
q.front();               // 获取队首元素
q.back();                // 获取队尾元素
q.size();                // 返回元素个数
q.empty();               // 判断队列是否为空，返回真则为空



priority_queue<int> pq;    // 创建空优先队列
pq.push(x);               // 插入元素x
pq.pop();                 // 删除最大元素
pq.top();                 // 获取最大元素
pq.size();                // 返回元素个数
pq.empty();               // 判断队列是否为空，返回真则为空


// set的二分查找
set<int> s;
s.lower_bound(x);  // 返回大于等于x的第一个元素的迭代器，如果不存在，则返回 s.end()
s.upper_bound(x);  // 返回大于x的第一个元素的迭代器，如果不存在，则返回 s.end()

// map的二分查找
map<int, string> m;
m.lower_bound(x);  // 返回key大于等于x的第一个元素的迭代器,如果不存在，则返回 m.end()
m.upper_bound(x);  // 返回key大于x的第一个元素的迭代器,如果不存在，则返回 m.end()


//例子
set<int> s = {1, 3, 5, 7, 9};
auto it = s.lower_bound(4);  // it指向5
cout << *it << endl;  // 输出: 5

map<int, string> m;
m[1] = "one";
m[3] = "three";
m[5] = "five";
auto it2 = m.lower_bound(2);  // it2指向key为3的元素
cout << it2->first << " " << it2->second << endl;  // 输出: 3 three

9.高精度

实在不行直接用long long，能拿多少分算多少分

有时间就背背语法

10.链表

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <iostream>
using namespace std;
struct student{
	int id;
	char name[101];
	int result;
	struct student *next;//结构体指针，用于指向下一个结构体
}; 
typedef struct student stu;
int main(){
	stu *head,*tail,*p;
	p=(stu*)malloc(sizeof(stu));//分配一个地址
	head=p;
	tail=p;
	head->next=NULL;//为了让最后一个指针的next可以正确指引退出，要使之为负
	cin>>p->id;
	while(p->id!=0){
		cin>>p->name;
		cin>>p->result;
		p=(stu*)malloc(sizeof(stu));//分派新的空间
		tail->next=p;//让上一个结构体可以正确指向下一个
		tail=p;//更新地址
		tail->next=NULL;//使之可以正确退出
		cin>>p->id;
	}
	p=head;
	while(p!=NULL){
		if(p->id!=0)cout<<p->id<<" "<<p->name<<" "<<p->result<<endl;
		p=p->next;
	}
	return 0;
}

11.哈希表

map哈希表默认按照升序来排序key，就是map<string,int>中string那一部分，系统排顺序就是依照他的升序

但是基于map实现的unorderede_map就是无序的

12.前缀和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
ll n, a[maxn], b[maxn];
int main()
{
    cin >> n;
    //预处理b数组
    for(int i = 1; i <= n; i++)
        cin >> a[i], b[i] = b[i - 1] + a[i];
    ll S = 0;
    //O(n)求解S
    for(int i = 1; i <= n; i++)
        S += a[i] * (b[n] - b[i]);
    cout<<S<<endl;
    return 0;
}

13.二分

满足某个条件使得一边均满足，另一边均不满足的，就是二分

14.整数与整除

符号^代表的是同时成立的意思

15.组合数公式

#include<bits/stdc++.h>
using namespace std;

int C(int n, int m)
{
    if (m == 0) return 1;//此时组合数为0
    if (m == 1) return n;//此时组合数为n
    if (n == m) return 1;//此时组合数为1
    else return C(n - 1, m - 1) + C(n - 1, m);
}
int main()
{
    int t, n, m;
    cin >> t;
    while (t--)
    {
        int ans;
        cin >> n >> m;
        ans = C(n, m);
        cout << ans << endl;
    }
    return 0;
}

优先级

前缀和 差分

排序 贪心

标准库

填空

递归

dfs bfs

16.按位与（&）

这个地方比较的是两个数字的二进制，比如a&b（a为5，b为10时，a的二进制表示为0101，b的二进制表示为1010），他们对应的位置如果都为1时，则新的位置为1，其余都为0，故a&b=0000；

17.按位或（OR）

按位或运算符（|）将两个数的二进制位逐位对齐，只要其中一个位为1，结果位就为1；如果两个位都为0，结果位才为0。

18.按位异或（XOR）

按位异或运算符（^）将两个数的二进制位逐位对齐，当两个位不同（一个为0，一个为1）时，结果位为1；否则为0。

19.按位取反/取非（NOT）

按位非运算符（~）将一个数的每个位反转：0变为1，1变为0。

20.>>和<<

>>n位，就相当于除以2的n次方。

<<n位，就相当于乘以2的n次方。

21.汉诺塔问题

#include <bits/stdc++.h>
using namespace std;  
vector<string> arr;//设置一个arr容器储存每一步
void hnt(string from,string assist,string to,int n){
  if(n==1){//如果只有一个需要移动，他可以直接从起点到终点，所以直接存入即可
    string s="#"+to_string(n)+": "+from+"->"+to;
    arr.push_back(s);
    return ;
  }
  hnt(from,to,assist,n-1);//先把最大的上面的全都放到辅助位置
  string s="#"+to_string(n)+": "+from+"->"+to;//现在可以把最大的放到终点
  arr.push_back(s);
  hnt(assist,from,to,n-1);//把辅助位置放到终点
}
int main(){

  int n,m;
  cin>>n>>m;
  hnt("A","B","C",n);
  cout<<arr[m-1]<<endl;
  cout<<arr.size();
  return 0;
}

22.全排列的价值（？）

特别注意，对于取模运算来说，加法和乘法的运算不受影响，只有除法不能分步取模

#include <iostream>
using namespace std;
typedef long long ll;
int main(){
  ll n;
  cin>>n;
  ll x=998244353;
  ll jie=1;
  ll now=0;
  for(ll i=1;i<=n;i++){
    jie*=i;
    jie%=x;
    now=(now*i%x+ i*(i-1)/2*jie%x)%x;//公式推到的来源是规律，每次插入一个新的数字n，有n个位置去插入上一个数组，上一个数组的组合有n-1的阶乘那么多，然后加上上一个数组的价值*n，因为多插入了一个数字，现在一共有n个数字，所以乘上n
	}
  cout<<now;
}

23.排序模板

这一套算法的基础来源于规律，比如一组数（1 3 4 2 5），从第四个数2开始，我们的算法发现了他的前一个数字比他本身要大，和我们升序的要求不符合，所以我们从第三个开始往回走，他只要满足下表不小于零且比第四个数2要大就往前走，由于每交换一次，下表都会减一，减一之后到了下一次循环就会发现不符合要求，所以最后安排哨兵（第四个数2）的位置的时候就要给下标+1；

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<int> arr;
	for(int i=0;i<n;i++)cin>>arr[i];
	for(int i=0;i<n;i++){
		int now=arr[i];
		int j=i-1;
		while(j>=0&&a[j]>now){
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=key;//相当于最后如果说上面的那个while循环的退出是因为j==-1,那么这个时候j++是为了让空出来的0位置补上去，相当于从始至终只有一个元素被覆盖，但是一开始已经保存好了这个元素，所以不用担心 
	}
	
	return 0;
}

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

24.错误票据

#include <bits/stdc++.h>
using namespace std;
const int N=1e5;
int shu[N]={0};
int main(){
	int a;
	int m1=-1;
	int m2=1000000;
	int ci;
	cin>>ci;
	while(ci--){//一共要输入的行数
	while(cin>>a){//读取每一行要输入的每个元素，遇到了换行符就会退出
		m1=max(m1,a);
		m2=min(m2,a);//直接得到最大和最小的数字，这样子代表了这一个数组的范围
		shu[a]++;
	}
	}
	int c,q;
	for(int i=m2;i<=m1;i++){
		if(shu[i]==0){
			q=i;
		}
		if(shu[i]==2){
			c=i;
		}
	}
	cout<<q<<" "<<c<<endl;
  //cout<<m2<<" "<<m1;
	return 0;
}

25.二分例题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
bool check(ll x,ll a[],ll b[]){
  ll v=m;
  for(ll i=0;i<n;i++){
    if(a[i]>=x)continue;
    else if(a[i]+b[i]<x)return false;
    else if(a[i]+b[i]>=x&&v-(x-a[i])>=0){
      v-=(x-a[i]);
    }
  }
  return true;
}
int main(){
  cin>>n>>m;
  ll a[n];
  ll b[n];
  for(ll i=0;i<n;i++){
    cin>>a[i];
  }

  for(ll g=0;g<n;g++){
    cin>>b[g];
  }
  ll l=0,r=100;
  while(l<r){//只要l超过了r，那么此时我们的逼近就起到了作用。
    ll x=(l+r)>>1;
    if(check(x,a,b))l=x+1;
    else r=x-1;
  }
  cout<<l;
  return 0;
}

26.动态规划基础题

#include <bits/stdc++.h>
using namespace std;
const int N=20;
int mem[N];

int dfs(int x){
    if(mem[x])return mem[x];
    int sum=0;
    if(x==1)sum=1;
    else if(x==2)sum=2;
    else sum=dfs(x-1)+dfs(x-2);
    mem[x]=sum;
    return sum;
}
int main(){
    int x;
    cin>>x;
    cout<<dfs(x);
    return 0;
}

每次只有推到到了最后一行的时候才得到了所有可能的结果，这个时候开始往前推算自己的答案来获得自己的正确答案。

“递”往下的过程是类似于树的分支，每一个分支都是一种可能，也就是分解成子问题来分类讨论。

大学 C 组

1.枚举[1-3]

#include <iostream>
#include <vector>
using namespace std;
int sum=0;
void dfs(int x,int n1,int n2){
  if(x>=7){
    if(!n1&&!n2)sum++;
    return ;
  }
  if(x==7||n1<0||n2<0)return ;
  for(int i=0;i<=n1;i++){
    for(int g=0;g<=n2;g++){
      if(i+g<=5&&i+g>=2){
        dfs(x+1,n1-i,n2-g);
      }
    }
  }
  }
  
int main()
{
  int n1,n2;
  n1=9;
  n2=16;
  dfs(0,9,16);
  cout<<sum;
  return 0;
}

27.贪心[1-5]

28.模拟[1-3] 

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int main()
{
  int sum1=0;
  int n,m;
  cin>>n>>m;
  vector<string> arr(n);
  int b=1;
  for(int i=0;i<n;i++)cin>>arr[i];
  for(int i=0;i<n;i++){
    for(int g=0;g<m;g++){
      bool is=true;
      b=1;
      while(is){
        if(i+b>=n||i-b<0||g+b>=m||g-b<0)break;
        if(arr[i+b][g+b]==arr[i][g]&&arr[i+b][g-b]==arr[i][g]&&arr[i-b][g+b]==arr[i][g]&&arr[i-b][g-b]==arr[i][g])sum1++;
        else break;
        b++;
      }
    }
    b=1;
  }
  cout<<sum1;
  return 0;
}

29.1.区间最大最小值：

调用c+自带的算法max_element来解决：

#include <iostream>
#include <algorithm>
using namespace std;
int n,q;
int a[500005]={0};
int a1[500005][2]={0};
int main()
{
  cin>>n>>q;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  for(int i=0;i<q;i++)
  {
    cin>>a1[i][0]>>a1[i][1];
  }
  for(int i=0;i<q;i++)//max_element的范围是包含起点不包含终点！
  {
    cout<<*max_element(a+(a1[i][0]-1),a+(a1[i][1]) )<<endl;
  }
  return 0;
}

30.区间最大最小值：

调用c+自带的算法max_element来解决：

#include <iostream>
#include <algorithm>
using namespace std;
int n,q;
int a[500005]={0};
int a1[500005][2]={0};
int main()
{
  cin>>n>>q;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  for(int i=0;i<q;i++)
  {
    cin>>a1[i][0]>>a1[i][1];
  }
  for(int i=0;i<q;i++)//max_element的范围是包含起点不包含终点！
  {
    cout<<*max_element(a+(a1[i][0]-1),a+(a1[i][1]) )<<endl;
  }
  return 0;
}

31：st表

gcd 最大公因数，每一个gcd组里面加上一个数，只会变小或者不变

调用c+自带的算法max_element来解决：

#include <iostream>
#include <algorithm>
using namespace std;
int n,q;
int a[500005]={0};
int a1[500005][2]={0};
int main()
{
  cin>>n>>q;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  for(int i=0;i<q;i++)
  {
    cin>>a1[i][0]>>a1[i][1];
  }
  for(int i=0;i<q;i++)//max_element的范围是包含起点不包含终点！
  {
    cout<<*max_element(a+(a1[i][0]-1),a+(a1[i][1]) )<<endl;
  }
  return 0;
}

32. 二维费用的背包问题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1001;
ll f[110][110];
ll n,V,M;
ll v[N],m[N],w[N];
int main(){
	cin>>n>>V>>M;
	for(int i=1;i<=n;i++){
		cin>>v[i]>>m[i]>>w[i];
	}
	for(int i=1;i<=n;i++){
		for(int vs=V;vs>=v[i];vs--){
			for(int ws=M;ws>=m[i];ws--){
				
					f[vs][ws]=max(f[vs][ws],f[vs-v[i]][ws-m[i]]+w[i]);
				
			}
		}
	}
	cout<<f[V][M];
	return 0;
}

33.完全背包问题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1010;
ll v[N],w[N];
ll n,V;
ll f[N];
int main(){
	cin>>n>>V;
	for(int i=1;i<=n;i++){
		cin>>v[i]>>w[i];
	}
	
	for(int i=1;i<=n;i++){
		for(int vs=v[i];vs<=V;vs++){
			f[vs]=max(f[vs],f[vs-v[i]]+w[i]);
		} 
	}
	cout<<f[V];
	return 0;
}

33回文字符串

#include <bits/stdc++.h>
using namespace std;
bool isstring(string a){
  vector<char> x;
  for(int i=0;i<a.length();i++){
    if(a[i]!='l'&&a[i]!='q'&&a[i]!='b'){
      x.push_back(a[i]);
    }
  }


  for(int i=0;i<x.size();i++){
    if(x[i]!=x[x.size()-i-1])return false;
  }
  return true;
}
int main(){
  int n;
  cin>>n;
  string a;
  for(int i=1;i<=n;i++){
    cin>>a;
    if(isstring(a))cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
  return 0;
}

34.班级活动：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5;
ll st[N];
int main()
{
  ll n;
  cin>>n;
  ll m1=-1;
  ll a[n+1];
  for(ll i=1;i<=n;i++){
    cin>>a[i];
    st[a[i]]++;
    m1=max(m1,a[i]);
  }
  ll sum=0;
  ll s1=0;
  for(ll i=1;i<=m1;i++){
    if(st[i]>2){
      sum+=(st[i]-2);
    }
    else if(st[i]==1){
      s1++;
    }
  }
  if(s1>sum){
    sum=sum+(s1-sum)/2;
  }
  cout<<sum;
  return 0;
}

35握手问题

#include <bits/stdc++.h>
using namespace std;
int main(){
  int sum=0;
  for(int i=1;i<=50;i++){
    for(int g=i+1;g<=50;g++){
      if(i<=7&&g<=7)continue;
      sum++;
    }
  }
  cout<<sum;
  return 0;
}

36:数字接龙

#include <bits/stdc++.h>
using namespace std;

const int N = 11; // 定义棋盘的最大大小为11×11
int n, k; // n为棋盘大小，k为数字循环的范围
int g[N][N]; // 存储棋盘上的数字
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; // 定义8个方向的x坐标偏移
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}; // 定义8个方向的y坐标偏移
string path; // 存储路径的方向编号
bool st[N][N]; // 标记棋盘上的格子是否被访问过
bool edge[N][N][N][N]; // 检查路径是否交叉

// 深度优先搜索函数，用于寻找路径
bool dfs(int a, int b) {
    // 如果到达右下角格子，检查路径长度是否为n*n-1（因为起点不计入路径）
    if (a == n - 1 && b == n - 1)
        return path.size() == n * n - 1;

    st[a][b] = true; // 标记当前格子已访问
    for (int i = 0; i < 8; i++) { // 遍历8个方向
        int x = a + dx[i], y = b + dy[i]; // 计算目标格子的坐标
        // 检查目标格子是否越界、是否访问过、数字是否满足循环序列要求
        if (x < 0 || x >= n || y < 0 || y >= n) continue;
        if (st[x][y]) continue;
        if (g[x][y] != (g[a][b] + 1) % k) continue;
        // 检查路径是否交叉（对于斜向移动，检查是否有反向的路径）
        if (i % 2 && (edge[a][y][x][b] || edge[x][b][a][y])) continue;

        edge[a][b][x][y] = true; // 标记路径
        path += i + '0'; // 将方向编号加入路径
        if (dfs(x, y)) return true; // 递归搜索下一个格子
        path.pop_back(); // 回溯，移除路径中的最后一个方向
        edge[a][b][x][y] = false; // 回溯，取消路径标记
    }
    st[a][b] = false; // 回溯，取消当前格子的访问标记
    return false; // 如果所有方向都无法到达终点，返回false
}

int main() {
    cin >> n >> k; // 输入棋盘大小和数字循环范围
    for (int i = 0; i < n; i++) // 读取棋盘上的数字
        for (int j = 0; j < n; j++)
            cin >> g[i][j];

    // 从起点(0,0)开始搜索路径
    if (!dfs(0, 0))
        cout << -1 << endl; // 如果没有找到路径，输出-1
    else
        cout << path << endl; // 输出路径的方向编号序列

    return 0;
}

37.回文数组

#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
long long a[N], b[N], sum = 0;
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    // 构建差值数组
    for (int i = 1; i <= n / 2; ++i) {
        b[i] = a[n - i + 1] - a[i];
    }
    // 贪心算法处理差值数组
    for (int i = 1; i <= n / 2; ++i) {
        if (b[i] > 0 && b[i + 1] > 0) { // 相邻同正
            if (b[i + 1] > b[i]) {
                sum += min(b[i], b[i + 1]);
                b[i + 1] -= b[i];
            } else {
                sum += max(b[i], b[i + 1]);
                i++; // 跳过下一个元素
            }
        } else if (b[i] < 0 && b[i + 1] < 0) { // 相邻同负
            if (b[i + 1] < b[i]) {
                sum += abs(max(b[i], b[i + 1]));
                b[i + 1] -= b[i];
            } else {
                sum += abs(min(b[i], b[i + 1]));
                i++; // 跳过下一个元素
            }
        } else {
            sum += abs(b[i]); // 相邻异号
        }
    }
    cout << sum << endl;
    return 0;
}

38.二分

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
bool check(ll x,ll a[],ll b[]){
  ll v=m;
  for(ll i=0;i<n;i++){
    if(a[i]>=x)continue;
    else if(a[i]+b[i]<x)return false;
    else if(a[i]+b[i]>=x&&v-(x-a[i])>=0){
      v-=(x-a[i]);
    }
  }
  return true;
}
int main(){
  cin>>n>>m;
  ll a[n];
  ll b[n];
  for(ll i=0;i<n;i++){
    cin>>a[i];
  }

  for(ll g=0;g<n;g++){
    cin>>b[g];
  }
  ll l=0,r=100;
  while(l<r){
    ll x=(l+r)>>1;
    if(check(x,a,b))l=x+1;
    else r=x-1;
  }
  cout<<l;
  return 0;
}

39.逃离中山路

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll N=1010;
ll way[N][N];
ll n,x1,y3,x2,y2;
ll dx[]={1,0,-1,0};
ll dy[]={0,1,0,-1};
ll st[N][N];
ll bfs(ll x1,ll y3,ll x2,ll y2){
    queue<pii> arr;
    arr.push({x1,y3});
    st[x1][y3]=0;
    while(!arr.empty()) {
        ll x=arr.front().first;
        ll y=arr.front().second;
        arr.pop();
        for(ll i=0;i<4;i++){
            ll a=x+dx[i];
            ll b=y+dy[i];
            if(a<1||b<1||a>n||b>n)continue;
            if(st[a][b])continue;
            if(way[a][b]==1)continue;
            st[a][b]=st[x][y]+1;
            if(a==x2&&b==y2)return st[a][b];
            arr.push({a,b});
        }
    }
}
int main(){
    cin>>n;
    string a[n+1];
    for(ll i=1;i<=n;i++)cin>>a[i]; 
    for(ll i=1;i<=n;i++){
        for(ll g=1;g<=n;g++)way[i][g]=a[i][g-1]-'0';
    }
    cin>>x1>>y3>>x2>>y2;
    cout<<bfs(x1,y3,x2,y2);
    return 0;
}

40

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
const ll N=200;
char way[N][N];
bool is[N][N];
ll dx[]={0,0,1,1,-1,-1,1,-1};
ll dy[]={1,-1,1,-1,1,-1,0,0};
void dfs(ll x,ll y){
	for(int i=0;i<8;i++){
		ll x1=x+dx[i];
		ll y1=y+dy[i];
		if(is[x1][y1])continue;
		if(x1<1||y1<1||x1>n||y1>m)continue;
		if(way[x1][y1]=='.')continue;
		is[x1][y1]=true;
		dfs(x1,y1); 
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int g=1;g<=m;g++)cin>>way[i][g];
	}
	ll sum=0;
	for(int i=1;i<=n;i++){
		for(int g=1;g<=m;g++){
			if(way[i][g]=='W'&&!is[i][g]){
				dfs(i,g);
				sum++;
			}
		}
	}
	cout<<sum;
	return 0;
}

41

.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct ele{
    int floor;
    int s;
};
ll n,a,b;
const ll N=300;
ll updown[N];
bool step[N];
int dfs(){
    queue<ele> q;
    q.push({a,0});
    step[a]=true;
    while(!q.empty()){
        ele cur=q.front();
        q.pop();
        if(cur.floor==b){
            return cur.s;
        }
        int up=cur.floor+updown[cur.floor];
        int down=cur.floor-updown[cur.floor];
        if(up<=n&&up>=1&&!step[up]){
            q.push({up,cur.s+1});
            step[up]=true;
        }
        if(down>=1&&down<=n&&!step[down]){
            q.push({down,cur.s+1});
            step[down]=true;
        }
    }
    return -1;
}
int main(){
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)cin>>updown[i];
    cout<<dfs();
    return 0;
    }

42.最大和

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=10100;
const ll MIN=-1e5;

ll t[N];
ll n;
ll f[N];
bool iszhi(ll n){
  if(n==1)return false;
  if(n==2)return true;
  if(n%2==0)return false;
  for(ll i=3;i<=sqrt(n);i++){
    if(n%i==0)return false;
  }
  return true;
}
ll minzhi(ll n){
  if(n==1)return 1;
  if(n==2)return 2;
  for(ll i=2;i<=sqrt(n);i++){
    if(n%i==0&&iszhi(i))return i;
  }
  return n;
}
int main(){
  cin>>n;
  for(ll i=1;i<=n;i++){
    f[i]=MIN;
  }
  for(ll i=1;i<=n;i++){
    cin>>t[i];
  }
  f[1]=t[1];
  for(ll i=1;i<=n;i++){
    
    ll s=i+1,f1=i+minzhi(n-i);
    for(ll g=s;g<=f1;g++){
      f[g]=max(f[g],f[i]+t[g]);
    }
  }
  cout<<f[n];
  return 0;
}

43.又到了喜闻乐见的dfs和记忆化搜索

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;
int dp[101][101][101];
int dfs(int jiu,int sn,int sm){
  if(sn<0||sm<0||jiu<0)return 0;
  if(jiu>sm)return 0;
  if(sn==0&&sm==1&&jiu==1)return 1;
  if(dp[jiu][sn][sm]!=-1)return dp[jiu][sn][sm];
  return dp[jiu][sn][sm]=(dfs(jiu*2,sn-1,sm)%MOD+dfs(jiu-1,sn,sm-1)%MOD)%MOD;
}
int main(){
  int n,m;
  cin>>n>>m;
  memset(dp,-1,sizeof dp);
  cout<<dfs(2,n,m);
  return 0;
}

44.缩位求和

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  int sum=10;
  string a;
  cin>>a;
  int s=0;
  while(sum>=10){
    for(int i=0;i<a.size();i++){
      s+=a[i]-'0';//从字符串转化4成整数不能用（int）强制转换，因为这样子得到的实际上是他的ASCLL码值
    }
    if(s<10){
      cout<<s;
      return 0;
    }
    else {
      string k;
      while(s){
        k+=s%10+'0';
        s/=10;
      }
      a=k;
    }
  }
  return 0;
}

45.阶乘求和

#include <iostream>
using namespace std;
int main()
{
  // 请在此输入您的代码
  long long int sum=0;
  long long int jiech=1;
  for(long long int i=1;i<=100;++i){
    if(jiech%1000000000==0){//后九位都为0则跳出循环不需要再取余相加
      break;//因为根据规律，随着阶乘数字越来越大，后面会出现越来越多的数字0，当他出现了9个零的时候就可以停止运算了，因为题目只要求了最后的九个数字
    }
    jiech %= 1000000000;
    jiech = jiech*i;
    
    sum+=jiech;
  }
  
  cout<<sum%1000000000<<endl;
  
  return 0;
}

46.空间

#include <iostream>
using namespace std;
int main()
{
  
  cout<<(long long )256*1024*1024*8/32;//1mb=1024kb;1kb=1024byte 1byte=8bits
  return 0;
}

47.ACL(其实就是ASCLL码）

#include <iostream>
using namespace std;
int main()
{
  char a='L';
  cout<<(int)(a);
  return 0;
}

48.进制转换

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
  cout<<2+2*9+2*9*9*9;
  return 0;
}

49.握手问题

#include <bits/stdc++.h>
using namespace std;
int main(){
  int sum=0;
  for(int i=1;i<=50;i++){
    for(int g=i+1;g<=50;g++){
      if(i<=7&&g<=7)continue;
      sum++;
    }
  }
  cout<<sum;
  return 0;
}

50.排列字母

#include <bits/stdc++.h>
using namespace std;
int main()
{
  string a;
  a="WHERETHEREISAWILLTHEREISAWAY";
  for(int i=0;i<a.size();i++){
  	for(int g=i+1;g<a.size();g++){
  		if((int)a[i]>(int)a[g]){
  			char z=a[i];
  			a[i]=a[g];
  			a[g]=z;
		  }
	  }
  }
  cout<<a;
  return 0;
}

全部评论

相关推荐

04-06 20:09
The University of Queensland Java
观察者模式（Observer Pattern）
观察者模式（Observer&nbsp;Pattern）是一种行为设计模式，它定义了对象之间的一对多依赖关系，当一个对象的状态发生改变时，所有依赖它的对象都会得到通知并自动更新。这种模式也被称作发布&nbsp;-&nbsp;订阅（Publish&nbsp;-&nbsp;Subscribe）模式。下面从多个方面详细介绍观察者模式。&nbsp;模式结构与角色&nbsp;观察者模式主要包含以下几个角色：&nbsp;主题（Subject）：也称为被观察者，它维护一个观察者列表，提供注册、移除观察者的方法，并且在自身状态改变时通知所有注册的观察者。&nbsp;具体主题（Concrete&nbsp;Subject）：实现主题接口，当状态发生变化时，调用通知方法来通知所有观察者。&nbsp;观察者（Observe...
Java设计模式
点赞 评论 收藏
分享
03-24 10:58
华中科技大学 后端
点赞 评论 收藏
分享
04-06 15:26
OPPO_人力资源部_人事专员(准入职员工)
OPPO内推OPPO内推
关于工作环境：base深圳前海&nbsp;内部配置绝了。一整栋50层都是oppo哒，我的工位可以看到欢乐港湾和大海，零食柜自给，很感动的是每层都提供独立的隔音室，3层饭堂里，23楼是最好吃的&nbsp;周边很繁华。楼下三层是大商场，午饭后我一般会和其他实习生姐妹去citywalk，好多奶茶店，茶救，奈雪&nbsp;喜茶，瑞幸，奶白，煲珠公每天换着喝，好幸福&nbsp;关于工作氛围&nbsp;感受到相当年轻，相当扁平的氛围，我们组（销售运营部）有三个哥哥姐姐直接对接我，她们人真的很nice，笨笨的我不会时，问她们都会耐心解答~~&nbsp;关于工作内容&nbsp;感觉出入还是有的，问了哥哥姐姐，他们收到五六十份简历，面了6个，最后选了我，好感动好幸运。偏大客户...
OPPO公司福利 370人发布
点赞 评论 收藏
分享
03-26 15:39
门头沟学院 Java
点赞 评论 收藏
分享
03-18 14:37
运营
面试华为？这三招让你从“菜鸟”变“HR收割机”！——“别再背算法了！华为面试官最怕你问‘这个问题’
先问个扎心问题：为什么你刷了500道LeetCode，还是过不了华为面试？&nbsp;你肯定遇到过这种情况：&nbsp;背了“我的缺点是追求完美”，结果被问“那你怎么解决的？”；&nbsp;准备了“STAR法则案例”，面试官却说“这个项目数据造假的嫌疑太大了”；&nbsp;甚至有人熬了三天模拟面试，结果被群面时的“即兴辩论”吓得语无伦次……&nbsp;我猜你心里肯定在想：“难道华为在故意为难人？”&nbsp;但真相是：华为要的不是“解题机器”，而是“能解决问题的人”。&nbsp;（面试金句：面试不是考试，是“真人秀”——你的每个表情，都在暴露真实的自己。）&nbsp;第一招：破解华为面试的底层逻辑——“他们要的不是你，是‘未来的你’”&nbsp;想象一下华为面试官...
大厂求职破局25职业突围... 大家都开始春招面试了吗 面试时最害怕被问到的问题
点赞 评论 收藏
分享
评论
1
1
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 实习进度记录 #
9372次浏览 59人参与
# 校招求职有谈薪空间吗 #
123550次浏览 1711人参与
# 春招进度记录 #
7053次浏览 13人参与
# 找工作如何保持松弛感？ #
32102次浏览 522人参与
# 初创公司值得加入吗？ #
17003次浏览 147人参与
# 创作灵感 #
95462次浏览 1470人参与
# 工作经验重要还是工资重要？ #
37333次浏览 468人参与
# 新能源会是生化环材的春风吗 #
9627次浏览 78人参与
# 如果没找到工作，考公是你的退路吗 #
21389次浏览 240人参与
# 秋招感动瞬间 #
16645次浏览 133人参与
# 中美关税战对我们有哪些影响 #
17965次浏览 230人参与
# 多益网络求职进展汇总 #
11511次浏览 70人参与
# 新凯来求职进展汇总 #
20955次浏览 72人参与
# 滴滴工作体验 #
19163次浏览 101人参与
# 参加完秋招的机械人，还参加春招吗？ #
35820次浏览 403人参与
# 怎么防止在试用期被辞退 #
112991次浏览 858人参与
# 摸鱼打卡站 #
34782次浏览 658人参与
# 阿里巴巴工作体验 #
14118次浏览 45人参与
# 机械制造公司求职体验 #
82551次浏览 345人参与
# 在国企工作的人，躺平了吗？ #
316857次浏览 3812人参与
牛客网
牛客企业服务