自动搬运

查看原文

来自洛谷，原作者为

	MTFlowCzq 我是心流czq

搬运于2025-08-24 22:41:30，当前版本为作者最后更新于2024-02-07 17:33:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

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

题目传送门

试题 $\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$ 的。

---

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

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