第五届蓝桥杯C++本科A组

浏览数：21 / 时间：2015年06月08日

今天上午参加了第五届蓝桥杯比赛，还是去年的地方，还是去年的考场，不同的是经过了一年的历练，多了一份坦然与自信。不管最后结果如何，是对自己一年学习的一个小小的交代。ACMER IN HHUC, we never say no.
结果填空
1.
a*a+b*b+c*c=1000;a,b,c均为整数，求一组解中的最小值。暴力的题目，很容易就想到了0，10，30.所以没多想就填上了0，可是考完发现还可以是负数。。。悲了个剧了，三分就这么水没了。。
2.
类似于往年的一道高斯的生日，求距离某一天（yyyy-mm-dd）X天是几月几日。因为数据比较小1000，编程反倒麻烦，所以手算了。答案应该是2017-08-05；
3.
说有一个神奇的数字，他的平方与立方各位数字不同而且能把0～9十个数全部用完。求这个数！每年都有这种考察对数的每一位操作的，关键还是暴力+每一位数字提取判断；但是刚上来应该要想到i*i+i*i*i 能表示十位，i是个两位数，从10到100里面找。答案好象是69；
代码填空
4.
输出一个图形。大致是将一个字符串嵌套到一个框框的正中间。
关键代码是：printf(“%*s%s%*s”); ________________;//输出最中间的一行
关键在于考得知识点很偏,%*s之前没有接触到过，知道表示的是将前面的空格填满，但是不知道该怎么表示。回来查过之后才知道用法类似于空格占位。所以正确代码应该是：

printf("%*s%s%*s",(width-2-strlen(buf))/2," ",buf,width-2-(width-2-strlen(buf))/2," ");

5.
1～9排列组合，一些做分子，一些做分母。求能组成的表示为1/3的组合。题目是用递归来做的，递归求排列枚举得出。
关键代码:

    {t=x[k];x[k]=x[i];x[i]=t};//完成一次交换

结果填空
6.
原题是发扑克，抽象出来就是1～13各最多有四张，任意挑13张，问最多有几种组合。最开始听学长说做蓝桥杯只要会深搜就可以了。果然是这样，以后好几道题思路也是一致的。深搜遍历，找到所有可能的情况，保证不重复只要保证后一个数大于等于前一个数就可以了。答案是：3598180

#include <iostream>
#include <cstdio>

using namespace std;

int sum;
int used[14];
int save[14];
void dfs(int num);
int main()
{
    for( int i = 1; i <= 13; i++ )
    {
        used[i]=4;
        save[i]=0;
    }
    dfs(1);
    printf("%d\n",sum);
    return 0;
}

void dfs(int num)
{
    if( num == 14 )
    {
        sum++;
        return ;
    }
    for( int i = 1; i <= 13; i++ )
    {
        if( used[i] != 0 && i >= save[num-1] )
        {
            used[i]--;
            save[num]=i;
            dfs(num+1);
            save[num]=0;
            used[i]++;
        }
    }
    return ;
}

7.
本质是一个环排列问题。有3颗黄色，4颗绿色，5颗紫色（颜色是我编的，无所谓了）珠子，串成一串手链。求所有不重复的情况数。环排列的公式我当时忘掉了，或者说压根没记住。但是我发现深搜得到的每种情况都会有12种重复，并且很容易想到不会出现逆序的情况。就深搜得到了答案，想一想其实原理也差不多。代码很简单，答案为：2310.

程序设计
8.
换饮料的题目，大概意思就是三个空瓶换一瓶饮料。问最多喝几瓶。之前在蓝桥杯官网上做到过，但是这次不能外借。不太习惯，刚开始还很纳闷，但是其实对于没做过的人来说反倒降低了难度。
关键代码：

    while( N >= 3 ){
        sum+=N-N%3;
        N=N/3+N%3;
    }
    //if( N == 2 )
    //    sum++;
    sum+=N;

9.
摞骰子问题。就是说有n个骰子摞在一起，但是有m组情况会使这摞骰子不稳定，所以要避免。比如1 2，所以1和2不能相邻。输入n,m;接下来m组数据。输出所有的可能数。注意每一个对着你的面不同都代表不同的情况，可以旋转。
一组样例：
输入：
2 1
1 2
输出：
544
分析：544=2×4×5×4+4×4×6×4；
这是一道dp，并且因为数据量太大，所以需要用滚动dp。具体数据量我忘记了，100%好象是10^9.因为结果可能数量太大，所以需要对10^9+7取模。

#include <iostream>
#include <cstring>
#include <cstdio>
#define mod 1000000007

using namespace std;

int N,M;
int a,b;
int dp[2][7];
int m[7][7];
long long sum;

int main()
{
    memset(m,0,sizeof(m));
    cin>>N>>M;
    for( int i = 0; i < M; i++ )
    {
        cin>>a>>b;
        m[a][b]=1;
        m[b][a]=1;
    }
    for( int i = 1; i <= 6; i++ )
        dp[0][i]=4;
    for( int i = 2; i <= N; i++ )
    {
        for( int j = 1; j <= 6; j++ )
        {
            for( int k = 1; k <= 6; k++ )
            {
                if( m[j][k] != 1 )
                {
                    dp[1][j]=((dp[1][j])%mod+(dp[0][k]*4)%mod)%mod;
                }
            }
        }
        for( int j = 1; j <= 6; j++ )
        {
            dp[0][j]=dp[1][j];
            dp[1][j]=0;
        }
    }
    for( int i = 1; i <= 6; i++ )
        sum=(sum%mod+dp[0][i]%mod)%mod;
    cout<<sum<<endl;
    return 0;
}

10.
这道题题意很复杂。因为讲的不是太清楚，理解了很久。大概抽象出来就是有N个村子，M条道路。现在道路全坏了，需要修路，每个道路的花费是P。但是修路只能从L到R中挑选能对K取余得到C的道路。每条路都是同时开工的，所以花费的最大时间就是所有这些道路中花费最大的一条。
从题目来看，应该是一道最短路（好像每次都有一道最短路的）。但是在如何松弛以及选择哪种方法之间抉择了很久。最开始想要用SPFA，但是后来注意到应该是一个多对多的问题，SPFA显然太复杂了。。。还是Floyed更好一点，哈哈。也就到这种程度了。那现在关键是松弛条件，其实想一想其实和纯Floyed很相似的，但是我们要找的是整条路上的最大的花费时间，而每条路最大的花费时间是等于可以松弛的另两条路的较大的那一个的。类似于Floyed，所以就很简单了，但是因为是大数据，我也不知道这种想法究竟能过多少，看人品了吧。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 5000
#define INF 0x7ffffff
using namespace std;

int N,M,Q;
int x,y,p;
int L,R,K,C;
int num,res;
int m[MAX][MAX];
int save[MAX];
void Floyed();
int main()
{
    cin>>N>>M>>Q;
    for( int i = 1; i <= N; i++ )
    {
        for( int j = 1; j <= N; j++ )
        {
            m[i][j]=INF;
        }
    }
    for( int i = 0; i < M; i++ )
    {
        cin>>x>>y>>p;
        m[x][y]=min(m[x][y],p);
        m[y][x]=min(m[y][x],p);
    }
    Floyed();
    for( int i = 0; i < Q; i++ )
    {
        cin>>L>>R>>K>>C;
        num=0;res=-1;
        memset(save,0,sizeof(save));
        for( int j = L; j <= R; j++ )
        {
            if( j % K == 0 )
            {
                save[num]=j;
                num++;
            }
        }
        for( int j = 0; j < num; j++ )
            for( int k = j; k < num; k++ )
                res = max( res,m[save[j]][save[k]]);
        cout<<res<<endl;
    }
    return 0;
}

void Floyed()
{
    for( int k = 1; k <= N; k++ )
    {
        for( int i = 1; i <= N; i++ )
        {
            for( int j = 1; j <= N; j++ )
            {
                if( m[i][j] > max(m[i][k],m[k][j]) )
                    m[i][j] = max(m[i][k],m[k][j]);
            }
        }
    }
    return ;
}