锐客网

  1. 首页 > it技术 > >

蓝桥杯|蓝桥冲刺31天打卡—Day11

算法蓝桥杯

1、天干地支 题目链接
蓝桥杯|蓝桥冲刺31天打卡—Day11
文章图片

蓝桥杯|蓝桥冲刺31天打卡—Day11
文章图片

输入样例

2020

输出样例
gengzi

思路
暴力模拟
题目中告诉我们2020年是庚子年，而庚是天干中的第七个（天干数组下标从0开始），所以要要对输入数加6后再模10，地枝则是直接模12
AC代码
#include #include #include #include using namespace std; string t[10]={"jia","yi","bing","ding","wu","ji","geng","xin","ren","gui"}; string d[12]={"zi","chou","yin","mao","chen","si","wu","wei","shen","you","xu","hai"}; int y; //年份 int main(){ cin>>y; string s1=t[(y+6)%10]; string s2=d[(y)%12]; cout<

2、包子凑数 题目链接
蓝桥杯|蓝桥冲刺31天打卡—Day11
文章图片

输入样例1：
2 4 5

输出样例1：
6

输入样例2：
2 4 6

输出样例2：
INF

思路
完全背包+数论
没做出来（DP问题大部分都不会）题解好像看懂了点
AC代码
#include #include #include #include using namespace std; const int N = 10010; int a[110]; bool dp[110][N]; //只取前i种笼子的包子，总和为是否能凑出int gcd(int a, int b)//最大公约数 { return b ? gcd(b, a % b) : a; } //两个数最大凑不出来的数为(a-1)(b-1)-1 int main() { int n; cin>>n; int d = 0; //储存所有数的最大公约数，如果不为1则凑不出来 for (int i = 1; i <= n; i ++ ) { cin>>a[i]; d = gcd(d, a[i]); } if (d != 1) cout<<"INF"; else { dp[0][0] = true; for (int i = 1; i <= n; i ++ ) for (int j = 0; j < N; j ++ ) { dp[i][j] = dp[i - 1][j]; if (j >= a[i]) dp[i][j] |= dp[i][j - a[i]]; }int res = 0; //统计个数 for (int i = 0; i < N; i ++ ) if (!dp[n][i])//凑不到i res ++ ; cout<


3、求值 题目链接
蓝桥杯|蓝桥冲刺31天打卡—Day11
文章图片

思路
直接暴力枚举
AC代码
#include #include #include #include using namespace std; int i; //约数 int n; int ans; int main() { for ( n = 1; ; n++) { //遍历n ans = 0; //每轮都清零 for (i = n; i >= 1; i--) { //从n开始往前遍历所有可能的约数 if (n % i == 0) { ans++; } if (ans == 100) { cout << n; return 0; } } } return 0; }


4、青蛙跳杯子 题目链接
蓝桥杯|蓝桥冲刺31天打卡—Day11
文章图片

蓝桥杯|蓝桥冲刺31天打卡—Day11
文章图片

思路
bfs，遍历6种走法，走到的地方与青蛙换位，直到当前串和目标串相同后输出步数
AC代码
#include #include #include #include #include using namespace std; string start, End; map dist; //map中string映射到int，标记且存储步数 queueq; int d[6] = {1, -1, 2, -2, 3, -3}; int bfs() { q.push(start); //起始串入队 dist[start] = 0; //步数置0 while ( q.size() ) { string t = q.front(); q.pop(); int distance = dist[t]; if ( t == End ) return distance; //当目标串和当前串相同输出步数 int a = t.find('*'); //找到空杯坐标位置 for ( int i = 0; i < 6; i ++ ) { //遍历6种走法 int b = a + d[i]; if ( b < 0 || b >= start.size() ) continue; //越界 swap(t[b], t[a]); //交换位置 if ( dist.count(t) == 0 ) { dist[t] = distance + 1; //步数+1 q.push(t); } swap(t[b], t[a]); } } }int main() { cin >> start >> End; cout << bfs() << endl; return 0; }


【蓝桥杯|蓝桥冲刺31天打卡—Day11】

    推荐阅读


    上一篇：#|蓝桥杯31天冲刺打卡题解（Day4）

    下一篇：#|蓝桥杯31天冲刺打卡题解（Day10）