P8691 [蓝桥杯 2019 国 C] 填空问题 - 题解

· · 题解

冬令营结束了，做几道提答放松一下

没有题解，来写一篇（为什么通过率那么低？！）

题目传送门

试题 \mathrm{A} ：奇数倍数

从小到大枚举 2019 的整数倍，并拆分开来看一下是否仅由奇数组成即可。代码如下：

#include<iostream>
using namespace std;
bool judge(int x) {
    while (x) {
        if (x%2==0) return false;
        else x/=10;
    }
    return true;
}
int main() {
    int x=1;
    while (!judge(2019*x)) x++;
    cout<<2019*x<<endl;
    return 0;
}

答案：139311。

试题 \mathrm{B} : 递增序列

对于每一个字符，往右、下、右下、左下、右上看一看，数出分别能组成多少递增对，全部统计起来即可。代码如下：

#include<iostream>
using namespace std;
char c[35][55];
int cnt,n=30,m=50;
int main() {
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            cin>>c[i][j];
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) {
            for (int k=j+1;k<=m;k++)
                if (c[i][j]<c[i][k])
                    cnt++;
            for (int k=i+1;k<=n;k++)
                if (c[i][j]<c[k][j])
                    cnt++;
            for (int d=1; i+d<=n && j+d<=m; d++)
                if (c[i][j]<c[i+d][j+d])
                    cnt++;
            for (int d=1; i+d<=n && j-d>=1; d++)
                if (c[i][j]<c[i+d][j-d])
                    cnt++;
            for (int d=1; i-d>=1 && j+d<=m; d++)
                if (c[i][j]<c[i-d][j+d])
                    cnt++;
        }
    cout<<cnt<<endl;
    return 0;
}

答案：52800。

试题 \mathrm{C} : 平方拆分

难度开始慢慢上去了。我一开始还看错题

考虑 DP。设 f_{i,j} 表示对 i 拆分，且每个数严格大于 j^2 的拆法数。则：

f_{i,j}=\sum_{k=j+1}^{k^2\le i}{f_{i-k^2,k}}

边界为 f_{0,j}=1。由于 n=2019 不大，跑的很快。代码如下：

#include<iostream>
using namespace std;
int n=2019,f[2020][50];
int main() {
    for (int i=0;i*i<=n;i++)
        f[0][i]=1;
    for (int i=1;i<=n;i++)
        for (int j=0;j*j<=i;j++)
            for (int k=j+1;k*k<=i;k++)
                f[i][j]+=f[i-k*k][k];
    cout<<f[n][0]<<endl;
    return 0;
}

答案：26287。

试题 \mathrm{D} : 最优旅行

一看到这题，我脑子里一声响。现实中的旅行商？！

图呢？别急，有个附件，下载下来。脑子里又一声响。

中文地名！？并且给的还不是边权，是起止时间？！

再仔细一看，（文件头两行表明）能有重边！？搞得我瞬间不想做了。。。

做完了“骰子制造”以后回来，静下心仔细想想，好像也没有那么恐怖。一共就 20 个地方，把地名转成 0 到 19 的编号即可，中文完全可以处理。至于给的时间，就转成 0 到 1439 间的数即可。扫一遍文档下来，除了头两行“北京到上海”以外，其余根本没有重边，也没有自环，只有两点之间的双向边。

对于头两行，我们完全可以忽略第二行。因为如果我们第一站是从北京到上海，这两班车都可以乘坐（时间在十二点之后），而第一班车的到达时间比第二班早；如果不是，那么头两行就都不用考虑了。这样就解决了重边的问题。

题目中让我们求最小时间，限制了每个地点都要呆至少 24 小时，那其实我们完全可以把这 19 天单独拿出来，到最后再统计；现在就相当于不停搭高铁，从北京出发，绕一遍其他 19 个城市后回到北京。更好的是，给出的车次中出发时间都小于到达时间，不会有卧铺。

妥妥的旅行商变种，用状压 DP 处理一下即可。注意在换高铁的时候可能要等到第二天，也可能在同一天，取决于上一辆车的到达时间与下一辆车的起始时间的大小关系。

代码如下：

#include<iostream>
#include<string>
using namespace std;
const int n=20, INF=0x3f3f3f3f;
string city[n]={"北京","上海","广州","长沙","西安","杭州","济南","成都","南京","昆明","郑州","天津","太原","武汉","重庆","南昌","长春","沈阳","贵阳","福州"};
int id(string s) {
    for (int i=0;i<n;i++)
        if (city[i]==s)
            return i;
    return -1;
}
int tim(string s) {
    return ((s[0]-'0')*10+(s[1]-'0'))*60+((s[3]-'0')*10+(s[4]-'0'));
}
struct Train {
    int st,en;
} g[n][n];
int dp[1<<n][n];
int dis(int now,int x,int y) { //重点！处理时间的函数
    int t=now%1440; //上一班车的下车时间
    int goal=now-t+g[x][y].en;
    if (t>g[x][y].st) goal+=1440; //是否要多等一天，取决于上班车的下车时间和这班车的上车时间的大小关系
    return goal;
}
int main() {
    freopen("trip.txt","r",stdin);
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            g[i][j].st=g[i][j].en=-1;
    string s;
    cin>>s>>s>>s>>s>>s;
    while (cin>>s) {
        int x,y;
        cin>>s; x=id(s);
        cin>>s; y=id(s);
        cin>>s; if (g[x][y].st==-1) g[x][y].st=tim(s);
        cin>>s; if (g[x][y].en==-1) g[x][y].en=tim(s); //若有重边，之后读的丢弃，对应了头两行中保留第一行
    }
    for (int s=0;s<(1<<n);s++)
        for (int i=0;i<n;i++)
            dp[s][i]=INF;
    dp[1][0]=720; //第一天中午
    for (int s=0;s<(1<<n);s++)
        for (int i=1;i<n;i++)
            if (s&(1<<i))
                for (int j=0;j<n;j++)
                    if ((s&(1<<j)) && g[j][i].st!=-1 && dp[s^(1<<i)][j]!=INF) {
                        int rec=dis(dp[s^(1<<i)][j],j,i); //利用 dis() 算出到达时间
                        if (rec<dp[s][i])
                            dp[s][i]=rec;
                    }
    int ans=INF;
    for (int i=1;i<n;i++)
        if (g[i][0].st!=-1)
            ans=min(ans,dis(dp[(1<<n)-1][i],i,0));
    cout<<ans-720+1440*(n-1)<<endl; // 去掉多加的头半天，补上在每个城市各呆的一天
    return 0;
}

结果：41613。

试题 \mathrm{E} : 骰子制造

这是一道数学题，不需要写代码。

首先，两个骰子任意旋转之后不会相同，当且仅当：

  1. 两个骰子的面点的相对位置关系不同，或者

  2. 某一面的方向不同，导致点排列的形状不同。

两个骰子的面点的相对位置关系共有 30 种。这是因为，不妨设 1 在上，则与 1 相对的有五种选法，不妨为 2；再设 3 在前，则与 3 相对的有三种选法，不妨为 4；则 5 和 6 在左右两边，有两种选法。共 5\times3\times2=30 种。

在确定了骰子的面的位置关系后，我们知道，数 2，3，6 可以旋转九十度而使形状改变；而数 1，4，5 不论如何旋转，形状不变。因此，有三个数可以旋转出各两种形状，在位置关系确定后，会有 2^3=8 种不同形状。

因此，总的骰子数为 30\times8=240。

答案：240。

最后提交的代码：

#include<iostream>
using namespace std;
int ans[5]={139311,52800,26287,41613,240};
int main() {
    char c; cin>>c;
    cout<<ans[c-'A']<<endl;
    return 0;
}

结束了……吗？

然后我们惊讶地发现，第四个测试点错了！

我找出了测试点的正确输出：47373。怎么回事呢？

（正文开始）

我花了大量的时间，调试测试点四，但就是找不出问题。

最终，我决定：让程序打印出路线，然后手算验证！

得到的结果为：

北京 天津 太原 郑州 西安 重庆 程度 昆明 南昌 福州
杭州 上海 南京 长沙 广州 贵阳 武汉 沈阳 长春 济南 北京

以下为涉及到的车次（全部出自附件）：

G8901  北京   天津   22:10   22:45
G2609  天津   太原   10:40   14:15
G688   太原   郑州   17:38   21:38
G2001  郑州   西安   07:52   10:24
G2231  西安   重庆   17:06   22:56
G8594  重庆   成都   06:50   08:07
G2883  成都   昆明   08:51   14:29
G1514  昆明   南昌   16:00   22:54
G5314  南昌   福州   08:13   11:09
G1642  福州   杭州   14:45   18:32
G7558  杭州   上海   07:06   08:12
G7180  上海   南京   10:05   11:29
G579   南京   长沙   09:27   14:10
G6117  长沙   广州   17:55   20:39
G2960  广州   贵阳   07:27   13:43
G1524  贵阳   武汉   14:23   19:33
G1274  武汉   沈阳   07:23   19:03
G8033  沈阳   长春   06:42   08:40
G1242  长春   济南   15:33   22:35
G336   济南   北京   07:45   09:33

经过手算验证，小明于第一天十二点从北京出发，在第三十天九点三十三分回到北京，当中经过了 41613 分钟。（后来又写了个暴力加剪枝，也是这个结果）

这个数值，已经小于答案 47373 分钟了。

然后我又观察到，答案 47373，比我们得到的结果 41613 正好多出 5760（也就是四天）！

于是我认为，有两种可能：

  1. 答案错了；

  2. 题意表述不明，或者漏了条件，导致理解上的错误

不管哪种情况，都希望题目能修正吧。这也是我写这篇题解的动机之一。经过观察，提交记录中很多人都是试错的，也有人做出 41613 的。

最后：本人第三篇题解，如有错误和建议欢迎指出（尤其是“最优旅行”）

我这篇题解或许大胆了一些，希望别出事。