蓝桥杯2017省赛习题补题总结

2021-03-08 约 2949 字预计阅读 6 分钟

C/C++语言B组

Problem-A 购物单

思路

按题意模拟即可。
注意到蓝桥杯从这一届开始支持使用codeblocks，那么我们可以先把购物单复制到codeblocks中，然后按下Ctrl+R使用多重替换功能，把价格前面的一串*和空格，以及折扣中的汉字替换掉，再在只有一位数字的地方补上0，就可以直接复制输入这一串价格，使用下面的代码得出应取的现金，向上取整到百位即可。

参考代码

#include <iostream>
using namespace std;

int main(void)
{
    double price, discount;
    double sum = 0;
    while(cin >> price >> discount)
    {
        sum += price*discount*0.01;
    }
    cout << sum << endl;
    return 0;
}

Problem-B 等差素数列

原题链接

思路

得到素数表之后，枚举公差构造等差数列即可，由于是从小达到枚举的公差，一旦构造出了长度为10的等差素数列，此时的公差就是最小的。
这道题是填空题，埃氏筛法和欧拉筛法都可以。

参考代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1000010;
int primes[maxn];
bool st[maxn];
int cnt;

void get_prime(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main(void)
{
    get_prime(10000);   //若10000不够，可以继续扩大素数表范围
    for(int delta = 1; delta * 10 <= 10000; delta++)  //从小到大枚举公差，注意控制数列中的数在素数表范围内
    {
        for(int i = 0; i < cnt; i++)    //遍历素数表
        {
            int flag = 1;
            int t = primes[i];
            for(int k = 1; k <= 9; k++)  //构造等差数列，若能够构造出长度为10的，则输出此时公差
            {
                if(t + delta > 10000 || st[t + delta])    //若构造的数列中出现合数，则构造失败，注意最后用来构造的素数不能在素数表范围以外
                {
                    flag = 0;
                    break;
                }
                else
                    t += delta;
            }
            if(flag)
            {
                printf("%d\n", delta);
                break;
            }
        }
    }

    return 0;
}

Problem-C 承压计算

原题链接

思路

首先由题意得到位于第i层第j个方块承重的递推式：
a[i][j] = a[i-1][j]/2 + a[i-1][j-1]/2
又由于最下层的精度极高，而且为整数，所以可以理解为最下层显示的读数是扩大了n倍的结果，使得最上层不断除以2分到下面，最下层显示的读数中也不会出现小数。
一共有30层，最上层的分量到最下层总共缩小了$2^29$倍，那么把每个方块都扩大$2^29$倍即可，这样就使得所有方块的重量和最下层的扩大倍数相匹配。

参考代码

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;
const int inf = 1e17;
const int maxn = 50;
LL a[50][50];

int main(void)
{
    for(int i = 1; i <= 29; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            LL t;
            scanf("%lld", &t);
            a[i][j] = t*(1<<29) + a[i-1][j-1]/2 + a[i-1][j]/2;
        }
    }

    LL maxWeight = -inf;
    for(int i = 1; i <= 30; i++)
    {
        a[30][i] = a[29][i]/2 + a[29][i-1]/2;
        if(maxWeight < a[30][i]) maxWeight = a[30][i];
    }
    printf("%lld", maxWeight);

    return 0;
}

Problem-D 方块分割

原题链接

思路

想对称分割这个正方形的格点图，直接从整张图的中心对称点(3,3)开始，想象拿一把剪刀把这张图剪开即可，由于是从中心对称点开始剪，先dfs遍历一半分割线，只要再关于这个中心对称点再对称一次，得到的这条完整的分割线就一定平分这张图。
那么dfs遍历时，从(3,3)开始遍历所有剪法，并且每次只需要要遍历到分割线的一半，另一半在遍历的同时，标记对称点就可以了。
假设有两点(x1,y1)和(x2,y2)关于(3,3)点对称，那么可以推出，这两点的坐标关系为：
(x1+x2)/2=3且(y1+y2)2=3，即x1 = 6-x2且y1 = 6 -y2。

参考代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 50;
bool st[maxn][maxn];
int a[maxn][maxn];
int res = 0;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

void dfs(int x, int y)
{
    if(x == 0 || x == 6 || y == 0 || y == 6)
    {
        //边长为六的正方形点阵，每一条边有7个点，所以边界点为0和6（点的下标从0开始）
        res++;
        return ;
    }
    st[x][y] = true;    //分割线经过了这个点
    st[6-x][6-y] = true;    //同时分割线对称的另一半经过了该点关于(3,3)的对称点


    for(int i = 0; i < 4; i++)
    {
        int tx = x + dx[i], ty = y + dy[i];
        if(!st[tx][ty])
        {
            dfs(tx, ty);
            st[tx][ty] = false; //回溯
            st[6-tx][6-ty] = false;
        }
    }
}

int main(void)
{
    dfs(3, 3);
    printf("%d\n", res / 4);    //去重，旋转对称的4种只算一种分割法

    return 0;
}

Problem-E 日期问题

原题链接

思路

这道题可以用模拟日期写，但是直接从小到大来枚举日期，判断与输入是否匹配可以简化代码。

参考代码

#include <cstdio>

int a, b, c;

bool isLeap(int n)
{
    if(n%400 == 0 || (n%4 == 0 && n%100 != 0)) return true;

    return false;
}

bool isSame(int y, int m, int d)
{
    if(y == a && m == b && d == c) return true; //采用年月日的
    else if(m == a && d == b && y == c) return true;    //采用月日年的    
    else if(d == a && m == b && y == c) return true;    //采用日月年的

    return false;
}

int main(void)
{

    scanf("%d/%d/%d", &a, &b, &c);

    for(int i = 19600101; i <= 20591231; i++)
    {
        int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        int y = i/10000, m = i%10000/100, d = i%100;
        if(isLeap(y)) month[2]++;   //判断枚举年是否是闰年
        if(m <= 12 && m >= 1 && d >= 1 && d <= month[m])    //验证枚举日期是否合法
            if(isSame(y%100, m, d))
                printf("%d-%02d-%02d\n", y, m, d);
    }

    return 0;
}

Problem-F 包子凑数

原题链接

思路

这道题主要是对裴蜀定理的应用。
裴蜀定理：
对任意整数a,b且gcd(a, b)=d，那么对于任意不全为0的整数x,y，都有a*x + b*y = m*d (m为不为0的整数)。
有了以上定理，我们就可以得到，若两个整数a,b的最小公约数为1，即这两个数互质，那么一定存在整数x,y使得a*x + b*y能够得到它们最小公约数d的整数倍。这个定理也可以扩展到对于n个整数的情况中。
应用到这道题目中，也就是说，除了小于这n个蒸笼中最少的包子数ai的包子凑不出来以外，若这n个蒸笼中的包子数互质，那么可以得到，它们一定凑出它们的最小公约数1的m倍，即它们的最大公约数为1的情况下，它们凑不出的数目显然是有限的，即凑数的过程中，出现“空隙”的数量是有限的。反之，则凑不出的数目是无限的。

参考代码

#include <cstdio>

const int maxn = 10010;
int a[maxn];
int f[maxn];

int gcd(int a, int b)
{
    return (b == 0) ? a : gcd(b, a%b);
}

int main(void)
{
    int n;
    scanf("%d", &n);
    int d;  //存储n个数的最大公约数，后面用来判断这n个数是否互质
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if(i == 1) d = a[i];
        else d = gcd(d, a[i]);
    }

    if(d != 1)
        printf("INF\n");
    else    //只考虑物品价值的完全背包问题
    {
        f[0] = 1;   //初始化边界方便计算，可以理解为0个数目的包子可以凑出来
        //枚举所有凑法，在能凑出来的数字基础上再凑，剩下的就是凑不出来的
        for(int i = 1; i <= n; i++)
            for(int j = 0; j+a[i] <= 10000; j++)
                if(f[j]) f[j+a[i]] = 1;

        int res = 0;
        for(int i = 1; i <= 10000; i++)
            if(!f[i]) res++;

        printf("%d\n", res);
    }

    return 0;
}

Problem-G 分巧克力

原题链接

思路

二分。这道题是二分判断可行解的应用。题目本是求一个最优解的问题，但是可以用二分来枚举巧克力的边长值，判断这个边长值能够分出多少块巧克力，根据分出的巧克力数量是大于还是小于小朋友的数量来进行二分，从而不断向最优解靠拢，最终查找到最优解。

参考代码

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;
const int inf = 0x3f3f3f3f;
vector<PLL> v;
int n, k;

bool check(int mid)
{
    LL sum = 0;
    for(auto it : v)
        sum += (it.first/mid)*(it.second/mid);
    return sum >= k;
}

int main(void)
{
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> k;
    for(int i = 0; i < n; i++)
    {
        LL a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }

    int l = 0, r = inf;
    while(l < r)
    {
        int mid = (l+r+1)/2;
        if(check(mid)) l = mid;
        else r = mid-1;
    }
    cout << l << endl;

    return 0;
}

Problem-H k倍区间

原题链接

思路

前缀和。前缀和是处理连续区间问题的利器。
此题先用前缀和预处理后，把前n个数的前缀和s[n]对k取模，并用一个cnt数组统计前缀和中对k取模后的结果相同的个数。
首先，对于区间[l, r]，若(s[r]-s[l-1])%k = 0（区间和为k的倍数即区间和对k取模为0），则说明区间[l,r]是一个满足条件的区间，而上述等式又可以转化为s[r]%k = s[l-1]%k，也就是找%k后结果相同的区间个数，利用组合数公式计算能够组成多少个区间即可。
比如样例中：
前1个数的和取模得1，则记录下取模得1的区间数变为1。
前2个数的和取模得1，则取模得1区间数变为2。
前3个数的和取模得0，则取模得0区间数变为1。
以此类推，得到取模结果依次为1 1 0 0 1。
可以用组合数公式计算出符合题目结果的区间数量为4，计算方式见代码注释。对于cnt数组也有一个注意点，详见注释。

参考代码

#include <cstdio>

const int maxn = 100010;
typedef long long LL;
LL cnt[maxn], sum[maxn];
LL res;
int n, k;

int main(void)
{
    scanf("%d %d", &n, &k);
    
    //这样的统计方式会漏掉[1,i]这个区间本身，cnt[0]先初始化为1，后面每次在遇到这种情况时就不会漏掉了
    cnt[0]++;   
    for(int i = 1; i <= n; i++)
    {
        LL t;
        scanf("%lld", &t);
        sum[i] = sum[i-1] + t;
        res += cnt[sum[i]%k];   //新的取模结果相同的区间能与之前取模结果相同的每个区间构成一个新的符合条件的区间
        cnt[sum[i]%k]++;
    }

    printf("%lld\n", res);

    return 0;
}

参考资料

承压计算
 方块分割
 等差素数列
 包子凑数
 日期问题

目录

蓝桥杯2017省赛习题补题总结

C/C++语言B组

Problem-A 购物单

Problem-B 等差素数列

Problem-C 承压计算

Problem-D 方块分割

Problem-E 日期问题

Problem-F 包子凑数

Problem-G 分巧克力

Problem-H k倍区间

参考资料