蓝桥杯知识点最终版
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;
}
SHEIN希音公司福利 261人发布
