蓝桥杯题目类型,蓝桥杯大赛题目

==蓝桥杯b组(java或c )==不说填空题的前两个填空题

这个问题大多数人都认为精度问题double的比较大小应该小于一定的精度，我们已经相等了，所以直接上传代码

# include iostream # include cstring # include algorithm # include ' cmath ' usingnamespacestd； 类型支付双精度，双精度pii； PII l[200000] int main () intn=0； for(intx1=0； x1 20； x1 ) for(inty1=0； y1 21； y1 ) for(intx2=0； 220； x2 ) for(inty2=0； y2 21； y2 ) if ) x1！=x2 )//不存在斜率的情况除外(双精度=(双精度) ) y2 - y1 )x2-x1 )； 双精度b=y1-k * x1； l[n ]={k，b}； }sort(L，l n )； int res=1； for(intI=1； i n； I ) if ) Fabs(L(I ).first-L ) I-1 ).first ) 1e-8||Fabs ) l ).second-L(I-1 ).second ) 1e-8 ) 答案： 40257}

这个问题考察了大多数公约数

# include iostream # include cstring # include algorithm # includevectorusingnamespacestd； 泰普德夫龙龙LL； int main () lln； cin n； vectorLL d； for(LLI=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(autoa:d ) for(autoa:d ) for(autoa:d ) if ) a*b*c==n ) res； cout res endl； 返回0； (答案) 2430

我们考察了这个问题是最短路的问题，这个问题只要是填补问题就不管，选择它写了dijskra (普通)堆优化也可以)算法spfa

也有flyod，只是跑的时间慢

在这里写spfa吧

# include iostream # include cstring # includealgorithmusingnamespacestd； 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]； intgcd(inta，int b ) /积极的导师算法({返回b？ GCD(b，a % b ) : a； }添加}voidadd(inta、int b、int c ) /边a-b，边权为c邻表(e[idx]=b，w[idx]=c，ne[idx]=h[a]，h[a]=idx 短信(dist，0x3f，sizeof dist )； dist[1]=0； q[tt ]=1； //手写队列st[1]=true； wile(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("%dn", dist[n]); return 0;}答案：10266837 编程题 F：就不说了

砝码称重：考察有选择的背包问题
dp的状态转移有三种情况
1、不选择当前数字
2、选择当前数字放到左边相当于减去当前背包重量
3、选择当前数字放到右边相当于加上当前背包重量
只要这三种情况有一种方案能表示当前数字这个数字就能表示出来

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 110, M = 200010, B = M / 2; //B为偏移量因为下表不能为负的int n, m;int w[N];bool f[N][M]; //如果为true说明当前j这个数字能够表示出来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("%dn", res); return 0;}

这个解法不太正宗但是组合数到 32取16好像就超1e9了所以跑到这么大的数
就如果还表示不出来说明这个数只能 是当前这个数取1等于他本身（数据全过）

#include "iostream"using namespace std;int a[1000010][40];void init(int n){ a[1][0] = 1; a[1][1] = 1; for(int i = 2; i < 1000010; i ++){ a[i][0] = 1; for(int j = 1; j <= i; j ++){ a[i][j] = a[i - 1][j - 1] + a[i - 1][j]; if(a[i][j] == n){ cout << (long long)i * (i + 1) / 2 + 1 + j<< endl; return ; } if(a[i][j] < 0) break; } } cout << (long long)n * (n + 1) /2 + 2 << endl;}int main(){ int n; cin >>n; if(n == 1) { cout << 1 << endl; return 0; } init(n); }

正宗正解 ：利用组合数

#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){ LL l = k * 2, r = max((LL)n, l); 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;}

后面的题实在是有点难可以骗骗分就走吧