锐客网

  1. 首页 > it技术 > >

蓝桥杯|第十届蓝桥杯省赛编程题题解（C++A组）

蓝桥杯算法数据结构c++二叉树经验分享动态规划


目录：

      • 完全二叉树的权值
      • 外卖店优先级
        • 算法步骤：
      • 修改数组
        • 因此我们考虑用另一种方法—并查集
          • 算法步骤：
      • 糖果
          • 状态表示： f [ i ] f[i] f[i]表示状态`i`下的最少方案数
          • 状态转移方程： f [ t ] = m i n ( f [ t ] , f [ j ] + 1 ) f[t]=min(f[t],f[j]+1) f[t]=min(f[t],f[j]+1)
          • 结果表示： f [ ( 1 < < m ) ? 1 ] f[(1<
      • 组合数问题【待补】

完全二叉树的权值
【蓝桥杯|第十届蓝桥杯省赛编程题题解（C++A组）】蓝桥杯|第十届蓝桥杯省赛编程题题解（C++A组）
文章图片

  • 基本思想：完全二叉树的层序遍历
  • 由于是完全二叉树，每层结点都是按顺序的，该层的结点数：
    0 < = x < = 2 n ? 1 , （ n 为 层 数 ） 0<=x<=2^{n-1},（n为层数） 0<=x<=2n?1,（n为层数）
    如果该层结点数x < 2 n ? 1 x<2^{n-1} x<2n?1，则为最后一层
    设每一层有num个结点，k为当前层级
  • 扫描一遍序列即可，由于结点绝对值最大为 1 0 5 10^5 105，最多有 1 0 5 10^5 105个点，最后一层和可能爆int，所以这里用long long.
  • 代码如下
#include using namespace std; const int N=100010; int a[N]; int n; int main() { cin>>n; for(int i=0; ires) res=sum,d=k; }cout<

外卖店优先级
  • 同理，直接暴力会TLE
算法步骤：
  1. 根据订单时间对所有订单排序，为什么要排序呢，因为排序后处理每一个外卖店都是往后的时间，可以轻易得到上一次外卖店的订单时间
  2. 根据上一次的订单时间计算优先级，用数组a表示当前优先级数量，数组b表示上一次的订单时间，st标记该外卖点是否在缓存中
  3. 遍历所有订单，再处理最后一次时间T产生的优先级减少
  • 代码如下
#include #include using namespace std; typedef pairPII; #define t first #define id secondconst int N=100010; int a[N],b[N]; int n,m,T; PII s[N]; bool st[N]; int main() { cin>>n>>m>>T; for(int i=0; i5) st[k]=true; b[k]=s[i].t; }for(int i=1; i<=n; i++) { a[i]-=T-b[i]; if(a[i]<=3) st[i]=false; }int res=0; for(int i=1; i<=n; i++) res+=st[i]; cout<

修改数组
  • 这题容易想到的是直接模拟一遍，用一个st数组标记是否用过该数，依次扫描输入的数往下递推，但是这样是妥妥地TLE.
因此我们考虑用另一种方法—并查集 算法步骤：
  • 基本思路：用p[x]储存这个x的下一个可用的数
  1. 对并查集初始化，p[i]=i;
  2. 对输入的数进行判断，通过find(x)找到该数的下一个可用的数，最后这个数的p[x]=x+1，表示x已经用过了，下一个只能用x+1.
  3. 每轮操作都输出数即可，也可以用离线做法
  • 代码如下：
#include using namespace std; const int N=100010,M=1100010; int n; int p[M]; int find(int x) { if(x==p[x]) return x; return p[x]=find(p[x]); //并查集能行优化得益于这里 }int main() { cin>>n; for(int i=1; i<=M; i++) p[i]=i; //init(); for(int i=0; i

糖果
  • 糖果种数少，每种糖果只有选了和未选两种状态，因此我们可以考虑状压dp，经过验证，可行！
  • 如 1000011 1000011 1000011表示这种状态已经有了第 1 , 2 , 7 1,2,7 1,2,7这三种糖果，用a数组保存
    既然是dp题，我们就直接上处理方法
状态表示： f [ i ] f[i] f[i]表示状态i下的最少方案数 状态转移方程： f [ t ] = m i n ( f [ t ] , f [ j ] + 1 ) f[t]=min(f[t],f[j]+1) f[t]=min(f[t],f[j]+1) 结果表示： f [ ( 1 < < m ) ? 1 ] f[(1<
  • 代码如下：
    • #include #include using namespace std; const int M=1<<20; int a[M],f[M]; int n,m,k; int main() { cin>>n>>m>>k; for(int i=1; i<=n; i++) { for(int j=0; j

    组合数问题【待补】
    未完待续…

      推荐阅读


      上一篇：第十届蓝桥杯省赛C++大学B组

      下一篇：蓝桥杯|2019第十届蓝桥杯B组决赛题解第二题