2018年第九届蓝桥杯B组C/C++决赛题解

1.换零钞 ok

枚举

设x表示1元钱的个数,y表示2元钱的个数,z表示5元钱的个数
x+210y+5y == 200,求x+y+z的最小值

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

2.激光样式 ok

dfs搜索
每个位置两种情况:开激光(在前一个激光没打开的情况下)、不开激光

3.格雷码 ok

二进制问题,lowbit函数 x & -x 找到末尾为1的位置

4.调手表 ok

bfs搜索
任意数调到任意数,就等于从0开始调到n-1的过程中的最大值
bfs搜索:每个状态两种情况 +1秒 +k秒,第一次到达的状态就是最优解;vis数组作标记,以确保后面不能再更新这个状态

5. 搭积木 0%

dp
不会

6.矩阵求和 40%

暴力还是能过40%的数据点

拿满分涉及数论的知识点
欧拉函数:(求[1,p)内与p互质数的个数的函数)
欧拉线性筛,求欧拉函数
我们需要求n以内一共有几个k*k(1<=k<=n),比如样例中有几个1 几个4 几个9;也就是说gcd(i,j)=k的(i,j)共有多少对,可以转化为n/k以内有几对i和j的gcd(i,j)=1,这样就可以用欧拉筛法求一下欧拉函数(n/k内有多少个数与i互质),然后前缀和就是满足条件的对数,然后求总和
参考:https://cloud.tencent.com/developer/article/1200020
参考:http://www.cnblogs.com/8023spz/p/10761240.html

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄