杨辉三角数
输入样例
2
3
6
输出样例
8
13
思路:这题主要考数学思维;首先通过观察,杨辉三角左右对称，题目要求找到数N的最先出现的地方，所以我们只要看左边就可以了.
我们如果单单通过观察行和列这样枚举,上面给的数据是10亿,是个很庞大的数据,我们能不能斜着来分析此问题囊？ 话不多说直接上图
我们会发现第一个斜行是1=C(0,0),第二斜行 2=C(2,1),,,,,;以此得到第i斜行的第一个数是C(2*i,i);
下面我们来确定10亿是在哪行,考试时可以用电脑自带的计算机计算，计算得出只要对其前16行进行枚举就可以。
我们从第16斜行开始枚举，出现等于n的数就返回其位置,这里n的位置我们可以这样确定:r为行，k为斜行,然后通过r*(r+1)/2计算它前面的行的总数再加上它所在行的前面的数k+1.对于查找过程中我们发现斜行是按升序来着,可以通过采用二分的方法进行查找,避免超时。
假如我们推个20;r=6,k=3;n=6*(6+1)/2+3+1=25
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; int n; LL C(int a, int b) //计算C（a，b） { LL res = 1; for(int i = a, j = 1; j <= b; i --, j ++) { res = res * i / j; if(res > n) return res; // 大于n已无意义，且防止爆LL } return res; } bool check(int k) { int l = 2 * k, r = max(n,l); while(l < r) { int mid = l + r >> 1; if(C(mid, k) >= n) r = mid; else l = mid + 1; } if(C(r, k) != n) return false; cout << 1ll*(r + 1) * r / 2 + k + 1 << endl; return true; } int main() { cin >> n; // 从第16斜行枚举 for(int i = 16; ; i--) if(check(i)) break; return 0; }
视频版:
第十二届蓝桥杯C++ B组讲解_哔哩哔哩_bilibili
双向排序
输入样例
3 3
0 3
1 2
0 2
输出样例
3 1 2
思路:感觉最后两道题都挺难的,都是考思维的,对于我这个小白真是太不友好了，只会个sort暴力排序偷几分,这个代码我就不放在这里面了.找了acw的视频看了下,条理清晰了些，视频放在这里:
第十二届蓝桥杯C++ B组讲解_哔哩哔哩_bilibili
下面我附上一位大佬写的博客,跟这个视频是相匹配的大家可以去看看,我就不必要再写了,总结的太详细啦.
蓝桥杯 I.双向排序_Jozky86的博客-CSDN博客_蓝桥杯双向排序
代码:
#include <iostream> #include <cstring> #include <algorithm> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 100010; int n, m; PII stk[N]; int ans[N]; int main() { scanf("%d%d", &n, &m); int top = 0; while (m -- ) { int p, q; scanf("%d%d", &p, &q); if (!p)//操作1 { while (top && stk[top].x == 0) q = max(q, stk[top -- ].y);//出现连续的操作1，我们取最大 while (top >= 2 && stk[top - 1].y <= q) //如果当前的操作1比上一次的操作1范围大，则将上一次操作1和操作2删除 top -= 2; stk[ ++ top] = {0, q};//存本次最佳操作 } else if (top)//操作2 &&且操作1已经进行过（操作二第一个用没效果） { while (top && stk[top].x == 1) q = min(q, stk[top -- ].y); while (top >= 2 && stk[top - 1].y >= q) top -= 2; stk[ ++ top] = {1, q}; } } int k = n, l = 1, r = n; for (int i = 1; i <= top; i ++ ) { if (stk[i].x == 0)//如果是操作1 while (r > stk[i].y && l <= r) ans[r -- ] = k -- ;//移动r值 ，并赋值 else while (l < stk[i].y && l <= r) ans[l ++ ] = k -- ; if (l > r) break; } if (top % 2) while (l <= r) ans[l ++ ] = k -- ; else while (l <= r) ans[r -- ] = k -- ; for (int i = 1; i <= n; i ++ ) printf("%d ", ans[i]); return 0; }
括号序列
老样子这题还是不完全会,又是用暴搜在测试点骗了部分分。
既然咱做不出来就要去学习大佬的做法和思路。
博客:12届蓝桥杯省赛c++b组 J题 括号序列_thejohn2020的博客-CSDN博客_蓝桥杯括号序列
视频:第十二届蓝桥杯C++ B组讲解_哔哩哔哩_bilibili
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; using LL=long long; const int N = 5005; int f[N][N]; int mod=1e9+7; string s; int n; LL get(){ memset(f,0,sizeof f); f[0][0]=1; for(int i=1;i<=n;i++){ if(s[i-1]=='('){ for(int j=1;j<=n;j++) f[i][j]=f[i-1][j-1]; } else{ f[i][0]=(f[i-1][1]+f[i-1][0])%mod; for(int j=1;j<=n;j++) f[i][j]=(f[i-1][j+1]+f[i][j-1])%mod; } } for(int i=0;i<=n;i++) if(f[n][i]) return f[n][i]; return -1; } int main(){ cin>>s; n=s.size(); LL x=get(); reverse(s.begin(),s.end()); for(int i=0;i<n;i++){ if(s[i]==')') s[i]='('; else s[i]=')'; } LL y=get(); cout<<(x*y)%mod; }
