• 蓝桥杯c++
2021-12-25 20:53:49
• 卡片

3181

vector的初始化方式（）与{}的区别

#include<iostream>
#include<vector>

using namespace std;
int main()
{
vector<int> cards(10,2021);
int i;
for(i=1;i<999999;i++)
{
//cout<<i<<endl;
int num=i;
while(num)
{
int n=num%10;
num/=10;
if(cards[n]==0)
{
return i-1;
}
cards[n]--;
}
}
return -1;
}
• 直线

40257

哈希函数如何定义，为什么斜率*9000

#include<iostream>
#include<vector>
#include<unordered_set>
#include<cmath>

using namespace std;

struct Line
{
Line(double xie_,double jie_)
:xie(xie_),
jie(jie_)
{

}
double xie;
double jie;
};

struct LineHash
{
hash<double> hash_double;
size_t operator()(const Line line) const
{
return hash_double((line.xie*9000+line.jie));
}
};

struct LineEqual
{
bool operator()(const Line line1,const Line line2)const
{
return fabs(line1.jie-line2.jie)<0.00001f&&fabs(line1.xie-line2.xie)<0.00001f;
}
};

int main()
{
unordered_set<Line,LineHash,LineEqual> xies;
for(int i=0;i<20;i++)
{
for(int j=0;j<21;j++)
{
for(int i1=0;i1<20;i1++)
{
for(int j1=0;j1<21;j1++)
{

if(j-j1==0)
{
continue;
}
double xie=(double)(i-i1)/(double)(j-j1);
double jie= i1-(j1)*xie;
auto ret=xies.insert(Line(xie,jie));
if(!ret.second)
{

}
}
}

}
}
cout<<xies.size()+21<<endl;
return xies.size();
}
• 货物摆放

243

#include<iostream>
#include<vector>

using namespace std;

int main()
{
long long ret=0;
int n=2021041820210418;
vector<long long> yins;
for(long long  i=1;i*i<=n;i++)
{
if(n%i==0)
{
yins.push_back(i);
yins.push_back(n/i);
}
}
for(auto i:yins)
{
for(auto j: yins)
{
for(auto k:yins)
{
if(i*j*k==n)
{
ret++;
}
}
}
}
char str[50];
time_t now = time(NULL);
strftime(str, 50, "%x %X", localtime(&now));
cout << str << endl;
cout<<ret<<endl;
return ret;
}
• 最短路径

暴力

递归 堆栈溢出

#include<iostream>
#include<vector>

using namespace std;
//最大公约数
int GCD(int a, int b)
{
if (a < b)
{
int temp = a;
a = b;
b = temp;
}
if (b == 0)
{
return a;
}
return GCD(b, a % b);
}

int LCM(int a, int b)
{
return a * b / GCD(a, b);
}

int MinDist(vector<vector<int>>& graph, int i)
{

if (graph[i][1])
{
//cout << graph[i][1] << endl;
return graph[i][1];
}
int min_dist = 99999999;
for (int j = 1; j < 2022; j++)
{
if (graph[i][j] == 0)
{
continue;
}
//cout<<i<<" "<<j<<" "<<graph[i][j]<<endl;
int temp = MinDist(graph, j) + graph[i][j];
if (temp < min_dist)
{
min_dist = temp;
}
}
//cout << min_dist << endl;
return min_dist;
}

int main()
{
cout << LCM(15, 55) << endl;
vector<vector<int>> graph(2022, vector<int>(2022, 0));
for (int i = 1; i < 2022; i++)
{
for (int j = i - 1; j >= i - 21 && j > 0; j--)
{
graph[i][j] = LCM(i, j);
}
for (int j = i + 1; j <= i + 21 && j < 2022; j++)
{
graph[i][j] = LCM(i, j);
}
}
int ret = MinDist(graph, 2021);
cout << ret << endl;
return ret;
}

dj算法

10266837

注意最短路径和最小生成树的区别click

#include<iostream>
#include<vector>
#include<set>

using namespace std;
//最大公约数
int GCD(int a, int b)
{
if(a<b)
{
int temp=a;
a=b;
b=temp;
}
if(b==0)
{
return a;
}
return GCD(b,a%b);
}

int LCM(int a, int b)
{
return a*b/GCD(a,b);
}

int MinDist(vector<vector<int>>& graph)
{
vector<int>dist(2022,99999999);
set<int> touched;
dist[1]=0;
while(1)
{
int min_j;
int min_dist=99999999;

for(int j=1;j<2022;j++)
{
if(touched.find(j)!=touched.end())
{
continue;
}
if(dist[j]<min_dist)
{
min_dist=dist[j];
min_j=j;
}
}

if(min_dist==99999999)
{
break;
}

touched.insert(min_j);

for(int k=1;k<2022;k++)
{
if(graph[k][min_j]==0)
{
continue;
}
dist[k]=min(dist[k],dist[min_j]+graph[min_j][k]);
//cout<<k<<""<<dist[k]<<endl;
}

}
return dist[2021];
}

int main()
{
cout<<LCM(15,55)<<endl;
vector<vector<int>> graph(2022,vector<int>(2022,0));
for(int i=1;i<2022;i++)
{
// for(int j=i-1;j>=i-21&&j>0;j--)
// {
//     graph[i][j]=LCM(i,j);
// }
for(int j=i+1;j<=i+21&&j<2022;j++)
{
graph[i][j]=LCM(i,j);
graph[j][i]=graph[i][j];
}
}
int ret=MinDist(graph);
cout<<ret<<endl;
return ret;
}
更多相关内容
• 2018第九届蓝桥杯C++B组真题。2018第九届蓝桥杯C++B组真题。
• ## 时间显示 蓝桥杯c++

千次阅读 2022-01-27 15:59:22
#include<bits/stdc++.h> using namespace std; int main(){ long long num,mm,ss,hh; cin>>num; hh=num/3600000; hh=hh%24; mm=num/60000; mm=mm%60; ss=num/1000; ss=ss%60;...h...

#include<bits/stdc++.h>
using namespace std;
int main(){
long long num,mm,ss,hh;
cin>>num;
hh=num/3600000;
hh=hh%24;
mm=num/60000;
mm=mm%60;
ss=num/1000;
ss=ss%60;
if(hh<10){
cout<<'0'<<hh;
}else{
cout<<hh;
}
if(mm<10){
cout<<':'<<'0'<<mm;
}else{
cout<<':'<<mm;
}
if(ss<10){
cout<<':'<<'0'<<ss;
}else{
cout<<':'<<ss;
}
} 

展开全文
• ## 第十二届蓝桥杯C++赛后感

万次阅读 多人点赞 2021-04-29 20:15:22
文章目录 A 空间 卡片 直线 货物摆放 路径 时间显示 G砝码称重 H杨辉三角形 双向排列 J括号序列 注：有些代码忘了考试时怎么写的了，（我也懒得重新写），所以很多题的代码是acwing蓝桥杯讲解里的，我对其进行注释和...

### 文章目录

注：有些代码忘了考试时怎么写的了，（我也懒得重新写），所以很多题的代码是acwing蓝桥杯讲解里的，我对其进行注释和修改

# A 空间

32位程序中，INT变量占用4个字节
1mb=1024kb
1kb=1024B
1B=8b
B:byte
b:bit
32位二进制数是四个字节
实际上就是求256MB有多少个32 bit

答案：256*1024*1024/4
= 67108864


# 卡片

直接模拟即可

#include<bits/stdc++.h>
#define debug(a,b) printf("%s = %d\n",a,b)
typedef long long ll;
using namespace std;

int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
return s*w;
}
int a[10];

bool iff(int x)
{
while (x)
{
int y = x % 10;
if (a[y])
a[y]--;
else
return 0;

x /= 10;
}
return 1;
}

int main() {
for (int i = 0; i <= 9; i++) a[i] = 2021;
for (int i = 1;; i++)
{
if (!iff(i))
{
cout << i - 1 << endl;
break;
}
}
return 0;
}


答案：3181


# 直线

比赛时用set实现的，忘了自己做的对不对。。
我当时做的方法是因为两点确定一线，所以枚举两个点，然后用set记录斜率和截距（y=k*x+b）,但是k有可能不存在，所以最后的答案还要额外加上20
当时代码懒得写了，按照其他博主的写法重新写的，只不过用的不是set，存下所有k和b后，排序，将重复的k和b删掉

#include<bits/stdc++.h>
#define debug(a,b) printf("%s = %d\n",a,b)
typedef long long ll;
using namespace std;

int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
return s*w;
}
const int maxn = 200000;
double eps=1e-8;
int n;
struct Line
{
double k, b;
bool operator< (const Line& t) const
{
if (k != t.k) return k < t.k;
return b < t.b;
}
}L[maxn];

int main()
{
for (int x1 = 0; x1 < 20; x1 ++ )
for (int y1 = 0; y1 < 21; y1 ++ )
for (int x2 = 0; x2 < 20; x2 ++ )
for (int y2 = 0; y2 < 21; y2 ++ )
if (x1 != x2)
{
double k = (double)(y2 - y1) / (x2 - x1);
double b = y1 - k * x1;
L[n ++ ] = {k, b};//存两点所形成的直线
}

sort(L, L +maxn);
int res = 1;
for (int i = 1; i < n; i ++ )
if (fabs(L[i].k - L[i - 1].k) > eps || fabs(L[i].b - L[i - 1].b) > eps)//说明不是一条直线
res ++ ;
cout << res + 20 << endl;//加20是因为k不存在的直线也要考虑

return 0;
}



我当时的做法是对的，但是最后的答案忘了是不是这个

答案：40257


# 货物摆放

LWH都是n的约数，问有多少种方案，其实就是求n的约数，用这些约数进行组合。因为约数不是很多，所以三重循环枚举约数，看是否等于n
对n求约束，直接开方求就行（因为如果x是约数，那么n/x也是，所以只需要将范围缩小到根号n）
（比赛时我是这么做的，确信）

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

int main()
{
LL n;
cin >> n;
vector<LL> d;
for (LL i = 1; i * i <= n; i ++ )
if (n % i == 0)
{
d.push_back(i);
if (n / i != i) d.push_back(n / i);
}

int res = 0;
for (auto a: d)
for (auto b: d)
for (auto c: d)
if (a * b * c == n)
res ++ ;
cout << res << endl;

return 0;
}

答案：2430


# 路径

就是一个建边跑最短路。。比赛时忘了gcd咋写emm
好像有的用dp来做？

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2200, M = N * 50;

int n;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N];
bool st[N];

int gcd(int a, int b)  // 欧几里得算法
{
return b ? gcd(b, a % b) : a;
}

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa()  // 求1号点到n号点的最短路距离
{
int hh = 0, tt = 0;
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
q[tt ++ ] = 1;
st[1] = true;

while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;

for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}

int main()
{
n = 2021;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
for (int j = max(1, i - 21); j <= min(n, i + 21); j ++ )
{
int d = gcd(i, j);
add(i, j, i * j / d);
}

spfa();
printf("%d\n", dist[n]);
return 0;
}

答案：10266837


# 时间显示

比赛时忘了1s等于多少ms，还好电脑自带计算器里有时间的进制关系（狗头🐕）

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int main()
{
LL n;
cin >> n;
n /= 1000;
n %= 86400;
int h = n / 3600;
n %= 3600;
int m = n / 60;
int s = n % 60;
printf("%02d:%02d:%02d\n", h, m, s);
return 0;
}


# G砝码称重

背包问题
自己对dp真的不熟。。五一要好好练练dp

对于每个砝码他有三个选择，称的左侧，右侧和不放，
我们设dp[i][j]表示前i个物品中，总质量为j的情况是否存在，dp为bool型
对于第j个物品，我们说了有三种选择，所以我们可以得到转移方程：

分别对应不选，放左侧，放右侧
dp[i][j]|=dp[i-1][j]
dp[i][j]|=dp[i-1][j-w[i]]
dp[i][j]|=dp[i-1][j+w[i]]


按照题目要求j-w[i]最小为-m，数组不能用负下标，所以我们加一个偏移量B，保证数组下标都为非负

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 200010, B = M / 2;

int n, m;
int w[N];
bool f[N][M];

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]), m += w[i];

f[0][B] = true;
for (int i = 1; i <= n; i ++ )
for (int j = -m; j <= m; j ++ )
{
f[i][j + B] = f[i - 1][j + B];
if (j - w[i] >= -m) f[i][j + B] |= f[i - 1][j - w[i] + B];
if (j + w[i] <= m) f[i][j + B] |= f[i - 1][j + w[i] + B];
}

int res = 0;
for (int j = 1; j <= m; j ++ )
if (f[n][j + B])
res ++ ;
printf("%d\n", res);
return 0;
}


# H杨辉三角形

因为杨辉三角形左右对称，所以我们只考虑左半部分
我们进行枚举可以看出，斜列的数量不会超过20个，所以枚举每一个斜列，每个斜列的第一个元素也是递增排列且有关系（第一个斜列的首元素为C(1,0),第二个为C(1,2),第三个为C(2,4),…C(x,2x)）,斜列内的元素是递增排列的，且大小都有公式关系（比如第3个斜列，第一个元素是C(2,4),第二个元素是C(2,5),然后是C(2,6)…），然后二分找具体位置
如果第C(r,k)是我们要找的元素，他的位置就是r * (r + 1) / 2 + k + 1
思维题
妙啊，当时写了一个半暴力，真想不到

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int n;

LL C(int a, int b)
{
LL res = 1;
for (int i = a, j = 1; j <= b; i --, j ++ )
{
res = res * i / j;
if (res > n) return res;
}
return res;
}

bool check(int k)
{
//C(a,b)
//a>=2b,二分a
LL l = k * 2, r = n;
while (l < r)
{
LL mid = l + r >> 1;
if (C(mid, k) >= n) r = mid;
else l = mid + 1;
}
if (C(r, k) != n) return false;

cout << r * (r + 1) / 2 + k + 1 << endl;

return true;
}

int main()
{
cin >> n;
for (int k = 16; ; k -- )
if (check(k))
break;
return 0;
}


讲解链接

# J括号序列

肯定是dp，但是我不会。。。等会了再更新

展开全文
• #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 2200, M = N * 50; int n; int h[N],e[M],w[M],ne[M]...void add(int a , int b , int c)/...

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2200, M = N * 50;

int n;
int h[N],e[M],w[M],ne[M],idx;//带权单链表

int q[M] , d[M];//队列,d[]存储距离
bool st[M];

void add(int a , int b , int c)//边权是c
{
e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx++;
}

//绝对值
int fabs(int x)
{
if(x < 0) return -x;
else return x;
}

//最小公约数
int ges(int a , int b)
{
while(a!=b)
{
if(a>b) a = a - b;
else b = b - a;
}
return a;
}

int spfa()  // 求1号点到n号点的最短路距离
{
int hh = 0, tt = 0;
memset(d, 0x3f, sizeof d);
d[1] = 0;
q[tt ++ ] = 1;
st[1] = true;

while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;

for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (d[j] > d[t] + w[i])
{
d[j] = d[t] + w[i];
if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
return d[n];
}

int main()
{
n = 2021;
memset(h , -1 , sizeof h);
for(int i = 1 ; i <= n ; i++)
for(int j = 1; j <= n ; j++)
{
if(fabs(i-j) <= 21)
{
int p = ges(i ,j);//最小公约数
add(i , j , i * j / p);
}
}

//求1号点到n号点的最短路距离
cout << spfa();
}

现在，她一个人漫游在夜晚的黄原街头，细细思索着孙少平这个人和他的道路。她从他的谈吐中，知道这已经是一个对生活有了独特理解的人。

——《平凡的世界》第二十三章

常常将自己化身为少平，却唯独少了那份坚定

展开全文
• 借鉴java版，案例修改为c++，供c++蓝桥杯参赛选手参考
• 题目链接：砝码称重 题解： f[i][j]表示选择前i个砝码总重量为j是否可以得到 我们设定砝码放在左边为正，放在右边为负 对于枚举到当前这个砝码，我们有三种选择方案： ...则当前状态与上一个状态方案相同，即f[i]...
• 2022 蓝桥杯C++ B组题解
• 后缀表达式 #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 200010; typedef long long LL; int n, m; int a[N];... for (int
• 这届蓝桥杯已经快开始了，为自己这一个月来关于C++的学习做点总结。 STL标准库数据结构 <vector> 这个函数主要是用于申请一个动态数组的。 先介绍基本操作： vector<int> a 用于申请一维 int 型...
• 蓝桥杯C++练习题 试题 基础练习 数列排序 资源限制 时间限制：1.0s 内存限制：512.0MB 问题描述 　给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200 输入格式 　第一行为一个整数n。 　第二...
• 第十三届蓝桥杯 C++ B组题解： A：进位制 （2022）9= 2 * 9^3 + 2 * 9+ 2=1478 B:顺子日期：（0，1，2算顺子，逆序不算） 枚举，14个 #include <iostream> #include <cstring> #include <algorithm&...
• #include<iostream> #include<cstdio> #include<algorithm> using namespace std; int a[15]; int main(void){ for(int i = 1;i<=10;i++){ a[i] = 2021; } int j;... }
• 第十二届蓝桥杯C++B 组真题 试题A. 空间 小蓝准备用256MB的内存空间开一个数组，数组的每个元素都是32 位二进制整数。 如果不考虑程序占用的空间和维护内存需要的辅助空间，请问256MB 的空间可以存储多少个32 位二...
• 可以直接遍历： 开个数组存下0-9卡牌的数量， 然后从1开始往后遍历 每次都分解当前遍历的数 如果出现卡牌数量为零 说明当前数无法拼出 直接输出上一个数 #include<bits/stdc++.h>...#define ll long long ...
• 题目 题目链接 题解 DFS + 并查集。 哇，不得不说两年前的我确实比现在强，这题是我当年比赛的时候遇到的，当时居然想出来了，现在根本不会，JR老矣，尚能AC否。 用 1 ~ 7 来代表 a ~ g；...若某两个二极管相邻，...
• 题解是注释，直接看
• 两个字概括，寄了！ 目录 A 九进制转十进制 B ... } J 砍竹子 不会写 总结一下，这次蓝桥杯表现极其不好，估了一下分数好像只有30几分，会的没做对，不会的也没骗到分，简直就是从头炸到尾 ，学算法的兴趣都快被打没了
• 2022年十三届蓝桥杯国赛将至，来看看去年蓝桥杯C++b组国赛题目如何
• 第十二届蓝桥杯c++b组（第二场） 试题A 求余 #include<iostream> using namespace std; int main() { cout << 2021 % 20; return 0; } //答案：1 试题B 双阶乘 #include<iostream> using ...
• 标准库类型string 标准库类型string表示可变长的字符序列，使用前先加头文件 #include<string> using std::string 1、定义和初始化string对象 string s1; //默认初始化，s1是一个空字符串 ...
• 2022蓝桥杯
• A空间 答案：67108864 #include<bits/stdc++.h> using namespace std;//结果：67108864 int main(){ cout<<256*1024*1024/4; return 0;...int use[20]={2021,2021,2021,2021,2021,2021,202
• 试题 算法训练 阶乘（蓝桥杯C++） 资源限制 题目 输入 输出格式 如何改变文本的样式 数据规模和约定 解题（使用C++解题） 资源限制 时间限制：1.0s 内存限制：256.0MB 题目 n ! 表示为n的阶乘，其中阶乘的定义是这样...
• 目录问题描述题目解析C++代码正确答案 问题描述 1/1 + 1/2 + 1/4 + 1/8 + 1/16 + … 每项是前一项的一半，如果一共有20项，求这个和是多少，结果用分数表示出来。 类似：3/2 当然，这只是加了前2项而已。分子分母...
• 写的时候太匆忙，平时习惯不好，忘记写return 0了，后来下午才发现
• 今天参加了蓝桥杯的比赛，感觉除了最后一道题写完后，差一点点没有运行成功，别的也没什么遗憾了，在算法刷题方面自己起步较晚，刷题较少，但是今天依旧做出了两道填空题（今年采取线上，一共只有两道填空题目），和...
• 蓝桥杯c++,青少组
• 蓝桥杯C++省赛真题题解.pdf
• 搭积木 矩阵求和

...

c++ 订阅