文章目录
- 十三届蓝桥杯国赛原题
- 1.2022
- 2.钟表
- 3卡牌
- 4最大数字
- 4.5 Dijkstra算法
- 5出差
十三届蓝桥杯国赛原题
1.2022
#include<iostream>
using namespace std;
long long int f[2023][11][2023]; //表示前2022个物品选择10个物品，体积总和为2022的方案个数 ,,数组下标为1开始，所以使2023，11，2023
int i, j, k;
int main()
{
for (i = 0; i <= 2022; i++) //因为体积为0，物品为0的所有情况都只有一种选择，即什么都不选
f[i][0][0] = 1;
for (i= 1; i <= 2022; i++) //枚举所有物品
{
for (j = 1; j <= 10; j++) //选了几个物品
{
for (k = 1; k <= 2022; k++) //枚举体积
{
f[i][j][k] = f[i-1][j][k]; //不选第i个物品
if (k >= i) //选第i个物品
f[i][j][k] += f[i-1][j - 1][k - i];
}
}
}
cout << f[2022][10][2022];
return 0;
}
2.钟表
试题 B: 钟表
【问题描述】
在 12 小时制的钟表中，有分针、时针、秒针来表示时间。记分针和时
针之间的夹角度数为 A（0 ≤ A ≤ 180）、分针和秒针之间的夹角度数为 B（0 ≤ B ≤ 180）。而恰好在 s 时 f 分 m 秒时，满足条件 A = 2B 且 0 ≤ s ≤ 6； 0 ≤ f < 60；0 ≤ m < 60，请问 s, f, m 分别是多少。
注意时针、分针、秒针都围绕中心匀速转动。
提交格式为三个由一个空格隔开的整数，分别表示 s, f, m。如 3 11 58表示
3 点 11 分 58 秒
问题解析
本人答案是：4 48 0.
我是这么想的，常见的那种时钟，分针和秒针走了，时针也是会跟着走的，比如有的人可能想着是6 0 15这样，但是秒针走了时针和分针其实也在走，严格来说此时分针和秒针并不是90度，分针和时针也不是180度，所以我认为是不行的。
我们知道秒针走一圈（360度）是60秒，即秒针一秒钟可以走6度；分针60分钟走一圈，即10秒钟走1度；时针12小时走一圈，即120秒走一度。根据范围我们知道我们可以枚举的最大时间是6小时59分59秒，即25199秒，我们只要从0枚举到25199，通过秒数算出分针、时针和秒针走过的角度，相减后得到角A和角B，再判断是否满足A=2*B即可。算出来后发现有两个结果：0 0 0和4 48 0，0 0 0被官方发公告ban了，所以我写的是4 48 0.
————————————————
版权声明：本文为CSDN博主「你好_Ä」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/fnmdpnmsl/article/details/125347764
#include<bits/stdc++.h>
using namespace std;
int main()
{
for(int i = 0; i < 25960 ; i++)
{
double m = (double) 1/10.0 * i ;
double h = (double) 36 / 4320 * i ;
double s = (double) 6 / 1.0 * i ;
while(m > 360) m -= 360 ;
while(s > 360) s -= 360 ;
double a , b ;
a = abs(m - h);
b = abs(m - s);
if(a == 2 * b) cout << i / 3600 << " " << i / 60 % 60 << " " << i % 60 << endl;
}
return 0;
}
3卡牌
2.解题思路
从题意出发，发现想直接求出答案，并没有一个很高效的办法，但如果给定我们一个 x ，让我们去判断能否凑出 x套牌，这个操作对我们来说并不难。所以我们可以考虑二分答案的做法，既然要二分那肯定得具有两段性，不难理解，如果我们可以凑出x xx套牌，那么[1,x−1]套牌也都是一定可以凑出来的,而并不一定可以凑出大于x xx的套牌数。
那么二分的check判断函数我们该如何书写呢？显然要凑够x套牌，我们需要使得每种类似的牌都有x xx张，如果已经当前判断牌的类型的数量已经大于等于x ，则不需要使用空白牌补充。如果使用当前类型的牌数加上它最多可加上的空白牌数仍然小于x ,那么此时可以直接返回false了。如果当前牌类型允许补充空白牌的数量足够给我们进行补充到 x，那么我们让空白牌的数减去需要使用的数量，如果不够用了，那么也返回false，如果可以完成所有的牌的填充，则返回true。
另外一个需要注意的点是r 的上限，以及m 的范围。m 的最大范围已经超出int，所以我们要使用long long，另外n 的最大范围是2×10^5
，而m 最大取到n^2
,能凑出的最大套牌数应该是2n,所以r的上限一定不能设小了。
整体做法的时间复杂为:O(nlogn)
————————————————
版权声明：本文为CSDN博主「执 梗」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_57487901/article/details/127124262
#include <iostream>
using namespace std;
typedef long long ll ;
const int N = 2e5 + 10;
ll n , m ;
int a[N] , b[N];
bool check(int mid , int a[] , int b[])
{
ll ans = m;
for (int i = 0; i < n; i++)
{
if (a[i] < mid)
{
if (mid - a[i] > b[i] || mid - a[i] > ans)return false;
else ans -= mid - a[i];
}
}
return ans >= 0;
//bool flag = true ;
//for(int i = 0 ; i < n ; i++)
//{
// if(a[i] + b[i] < m) flag = false;
// }
//return flag;
}
int main()
{
cin >> n >> m ;
for(int i = 0 ; i < n ; i++) cin >> a[i];
for(int i = 0 ; i < n ; i++) cin >> b[i];
int l = 0 , r = 2*N ;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid , a , b)) l = mid ;
else r = mid - 1 ;
}
cout << l ;
// 请在此输入您的代码
return 0;
}
4最大数字
看上去N的范围貌似很大，达到了1e17的范围，但其实我们最多只需要考虑这最多17位数，所以可以想到爆搜得到答案。
一个数的大小是从左到右依次判断，所以我们从最左边开始枚举，我们无需关注后面的数，要利用自己的1号操作和2号操作保证当前这个数位的数一定要尽可能最大
然后分别考虑两种操作，首先两种操作不可能混用，因为它们是抵消的效果，所以要么对这个数全使用1操作，要么2操作。假设某个数位的值为x,首先考虑1号操作，使用后可以让该数位变大，出于贪心考虑，我们想让它变成9，那么需要进行9-x次1号操作，当然可能此时1号操作并不足以让我们将x变成9，但我们还是使用剩余的全部的次数将其变大，所以每次考虑1号操作应该使用的操作数t应该为t=min(n,9-x),此时x将变为x+t，然后进行下一位的判断。
其次我们考虑2号操作，这个的判断比较简单，它是让某个值减小，唯一能让某个数变大的机会就是将其减到0后再减就会变成9。那么这样操作需要的次数就是x+1，如果操作次数不够，那我们宁愿不使用，因为这只会让这个数位变得更小。
在深搜dfs的过程中，参数记录遍历到第几个数位以及此时累计的和，当搜索完所有数位后，将此时的和与答案进行一个取max，最后的值则为答案。
————————————————
版权声明：本文为CSDN博主「执 梗」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_57487901/article/details/127150940
#include <iostream>
using namespace std;
string s ;
int a,b;
long long ans = 0 ;
void dfs(int i , long long v)
{
int m = s[i] - '0' ;
if(s[i])
{
int t = min(a,9-m);
a -= t;
dfs(i+1, v*10 + m + t);
a += t ;
if(b > m)
{
b -= m +1 ;
dfs(i + 1 , v * 10 + 9) ;
b += m + 1 ;
}
}
else
{
ans = max(ans , v);
}
}
int main()
{
cin >> s >> a >> b ;
dfs(0,0);
cout << ans ;
return 0;
}
4.5 Dijkstra算法
acwing例题：Dijkstra求最短路I
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510 ;
int g[N][N];
int n , m ;
bool st[N];
int d[N];
int dijkstra()
{
memset(d,0x3f,sizeof d);
d[1] = 0;
for(int i = 1 ; i <= n ; i++)
{
int t = -1 ;
for(int j = 1 ; j <= n ; j++)
{
if(!st[j] && (t == -1 || d[t] > d[j]))
{
t = j ;
}
}
st[t] = true;
for(int j = 1 ; j <= n ; j++)
{
d[j] = min(d[j] , d[t] + g[t][j]) ;
}
}
if(d[n] == 0x3f3f3f3f) return -1;
return d[n];
}
int main()
{
cin >> n >> m ;
memset(g, 0x3f, sizeof g);
while(m--)
{
int a , b, c ;
cin >> a >> b >>c ;
g[a][b] = min(g[a][b] , c);
}
int t = dijkstra();
cout << t;
return 0;
}
5出差
题意很明显考察的是一个最短路径问题，虽然题目说了给定的是双向边，但是假设g[i]的含义是到达i城市需要隔离的时间。假设有城市A和城市B,且两城市存在一条权值为w的双向边，当我们从A去到B所需要花费的时间应该是w+g[B],当我们从B去到A所花的时间应该是w+g[A]。所以虽然题意是双向边，但是方向不同的情况下，权值并不一定相同，所以我们应该看成两条边。
也就是说,存在邻接矩阵gra[][]，gra[i][j]表示从i到j的所需要的时间，g[i][j]和g[j][i]并不一定是相等的。所以我们在建图时应该分清楚，需要注意的是终点n的隔离时间我们是不考虑的，所以我们要把它置为0。然后建图完毕后直接跑一遍最短路算法即可，由于n nn的最大只有1000,所以使用朴素dijkstra算法也是能过的。
————————————————
版权声明：本文为CSDN博主「执 梗」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_57487901/article/details/127132577
#include<bits/stdc++.h>
using namespace std;
const int N = 1010 ;
int w[N];
int g[N][N] ;
int n , m ;
bool st[N];
int d[N];
int dijkstra()
{
memset(d , 0x3f , sizeof d);
d[1] = 0 ;
for(int i = 1; i <= n ; i++)
{
int t = -1 ;
for(int j = 1 ; j <= n ; j++)
{
if(!st[j] && (t == -1 || d[t] > d[j]))
t= j ;
}
for(int j = 1 ; j <= n ; j++)
d[j] = min(d[j] , d[t] + g[t][j]);
st[t] = true ;
}
return d[n];
}
int main()
{
cin >> n >> m;
for(int i = 1 ; i <= n ; i++) cin >> w[i];
w[n] = 0;
memset(g , 0x3f , sizeof g);
while(m--)
{
int a,b,c;
cin >> a >> b >> c;
g[a][b] = w[b] + c;
g[b][a] = w[a] + c;
}
cout << dijkstra() ;
return 0;
}
