第十届蓝桥杯题解 注释:这段时间正好在写蓝桥杯的题,将部分的题目的解法和大家分享,代码中的网址是该代码蒟蒻当时参考其他大佬的题解文章所在的网址,鸣谢大佬,如有错误,欢迎各位大佬指正 有部分网址是提交答案的oj传送门
平方和 直接暴力穷举,无需赘述
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include <bits/stdc++.h> using namespace std;long long ans1 = 0 ;long long ans2 = 0 ;bool judge (int n) { while (n) { int remp = n % 10 ; if (remp == 1 || remp == 2 || remp == 0 || remp == 9 ) return true ; n /= 10 ; } return false ; } int main () { for (int i = 1 ; i <= 2019 ; i++) { if (judge (i)) { ans1+=i; ans2+=i*i; } } cout<<ans2; return 0 ; }
数列求和 枚举过程中注意%1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include <bits/stdc++.h> using namespace std;int a[20190328 ];int main () { a[1 ] = 1 ; a[2 ] = 1 ; a[3 ] = 1 ; for (int i = 4 ; i <= 20190324 ; i++) { a[i] = (a[i - 1 ] + a[i - 2 ] + a[i - 3 ])%10000 ; } cout<<a[20190324 ]; return 0 ; }
最大降雨量 一道脑筋急转弯题。我们可以这样去考虑,49天一共可以分为7组,这7组的中位数再取其中位数,可以画一个邻接矩阵,可以发现绝对比答案大的数字只有15个,那么答案是49-15
1 2 3 4 5 6 7 8 9 #include <bits/stdc++.h> using namespace std;int main () { cout<<34 ; return 0 ; }
迷宫 一道bfs模板题。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 #include <bits/stdc++.h> using namespace std;int m, n; struct node { int x; int y; string path; }; char maze[100 ][100 ];bool visit[100 ][100 ];int dirx[4 ] = {1 , 0 , 0 , -1 }; int diry[4 ] = {0 , -1 , 1 , 0 };char dir[4 ] = {'D' , 'L' , 'R' , 'U' };bool judge (int x, int y, int startx, int starty) { if (x == n && y == m) return true ; else return false ; } void bfs (int startx, int starty) { queue<node> q; visit[startx][starty] = 1 ; node p; p.x = startx, p.y = starty; q.push (p); while (!q.empty ()) { int x = q.front ().x; int y = q.front ().y; string way = q.front ().path; q.pop (); if (judge (x, y, startx, starty)) { cout << way; return ; } for (int i = 0 ; i < 4 ; i++) { int rempx = x + dirx[i]; int rempy = y + diry[i]; string rempway = way + dir[i]; if (maze[rempx][rempy] == '0' && visit[rempx][rempy] == 0 && rempx <= n && rempx > 0 && rempy <= m && rempy > 0 ) { visit[rempx][rempy] = 1 ; node remp; remp.x = rempx, remp.y = rempy, remp.path = rempway; q.push (remp); } } } } int main () { ios::sync_with_stdio (false ); cin >> m >> n; for (int i = 1 ; i <= n; i++) { string remp; cin >> remp; for (int j = 1 ; j <= m; j++) { maze[i][j] = remp[j - 1 ]; } } bfs (1 , 1 ); return 0 ; }
RSA解密 额,这个题我的代码只能参考!~ 答案是跑不出来的 ~只能讲一下我的代码的大(cuo)概(wu)思路,首先求出p,q,求出p,q后转化为求逆元问题,再转化为求 C^d%e的问题。从网上查了很长时间也没搞懂怎么优化。直接摆烂了、、、、、 (数论不会我是菜鸡)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 #include <bits/stdc++.h> using namespace std;int num = 0 ;long long e;long long d = 212353 ;long long n = 1001733993063167141 ;long long C = 20190324 ;long long p, q;long long remp;long long fast_power (long long a, long long b, long long c) { a = a % c; long long ans = 1 ; while (b) { a = a % c; if (b % 2 == 1 ) ans = (ans * a) % c; b = b / 2 ; a = (a * a) % c; } return ans; } long long ex_gcd (long long a, long long b, long long &x, long long &y) { if (b == 0 ) { x = 1 ; y = 0 ; return a; } long long d = ex_gcd (b, a % b, x, y); long long tmp = x; x = y; y = tmp - a / b * y; return d; } int main () { for (int i = 2 ; i < n; i++) { if (n % i == 0 ) p = i, q = n % i; } long long sum = (p - 1 ) * (q - 1 ); long long x, y; e = ex_gcd (d, sum, x, y); e = (e % sum + sum) % sum; cout << fast_power (C, e, d); return 0 ; }
完全二叉树权值 一道数据结构概念题,只要知道完全二叉树的基本概念就迎刃而解了,0-2^1-1是第一层,2^1~2^2-1是第二层,2^2->2^2-1是第三层….以此类推
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <bits/stdc++.h> using namespace std;#define INF 0x7fffffff long long root[100000 ];long long a[100000 ];int n;int limit = 0 ;int num = 0 ;int main () { ios::sync_with_stdio (false ); cin >> n; cin >> a[1 ]; root[1 ] = a[1 ]; num = 2 ; limit = 4 ; for (int i = 2 ; i <= n; i++) { cin >> a[i]; root[num] += a[i]; if (i + 1 == limit) { limit = limit * 2 ; num++; } } long long ans = 0 ; long long max1 = -INF; for (int i = 1 ; i <= num; i++) { if (max1 <= root[i]) { max1 = root[i]; ans = i; } } cout << ans; return 0 ; }
外卖店队列 一道模拟题,如果直接以时间单位为循环入手直接TLE(别问我怎么知道的T—T),可以考虑枚举每一订单,当商店接到订单之后才去处理它,可以大大减少时间
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include <bits/stdc++.h> using namespace std;#define maxn 1000000 pair<int , int > order[maxn]; long long n, m, t;int ans[maxn]; long long last[maxn]; bool first[maxn]; int main () { ios::sync_with_stdio (false ); cin >> n >> m >> t; for (int i = 1 ; i <= m; i++) { cin >> order[i].first >> order[i].second; } sort (order + 1 , order + 1 + m); for (int i = 1 ; i <= m; i++) { int ts = order[i].first, id = order[i].second; if (ts != last[id]) { ans[id] = ans[id] - (ts - last[id] - 1 ); } ans[id] = max (ans[id], 0 ); if (ans[id] <= 3 ) { first[id] = false ; } ans[id] += 2 ; if (ans[id] > 5 ) first[id] = true ; last[id] = ts; } for (int i = 1 ; i <= n; i++) { if (last[i] != t) ans[i] = ans[i] - (t - last[i]); if (ans[i] <= 3 ) first[i] = false ; } long long res = 0 ; for (int i = 1 ; i <= n; i++) { if (first[i]) res++; } cout << res; return 0 ; }
二刷的时候用了结构体存数据,思路更清晰了一些
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 #include <bits/stdc++.h> using namespace std;struct node1 { int lastcall; int ans; bool flag; }shop[100010 ]; struct node2 { int time; int id; }ding[100010 ]; bool cmp1 (node2 a,node2 b) { if (a.time!=b.time) return a.time<b.time; else return a.id<b.id; } int main () { int n,m,t; scanf ("%d %d %d" ,&n,&m,&t); for (int i=1 ;i<=m;i++) { int time,id; scanf ("%d %d" ,&time,&id); ding[i].time=time; ding[i].id=id; } sort (ding+1 ,ding+1 +m,cmp1); for (int i=1 ;i<=m;i++) { int id=ding[i].id; int time=ding[i].time; if (shop[id].lastcall!=time) { shop[id].ans-=(time-1 -shop[id].lastcall); } shop[id].ans=max (shop[id].ans,0 ); if (shop[id].flag&&shop[id].ans<=3 ) shop[id].flag=false ; shop[id].ans+=2 ; shop[id].lastcall=time; if (shop[id].ans>5 ) shop[id].flag=true ; } for (int i=1 ;i<=n;i++) { if (shop[i].lastcall!=t) { shop[i].ans-=(t-shop[i].lastcall); } if (shop[i].flag&&shop[i].ans<=3 ) shop[i].flag=false ; } long long res=0 ; for (int i=1 ;i<=n;i++) { if (shop[i].flag) res++; } cout<<res; return 0 ; }