[算进] 巴士

Problem

ACwing 题目地址

Preface

~~我是真的想 bb 两句了~~，，，这个题目超级简单，但是因为看错题目x2 导致影响我一天的心情。。。

当然我要把好的题解和心情带给你们呀 qwq！

Solution

首先注意：这题的公交线路是一个严格在 (0-59) 范围内的等差数列，比如 (3,6,9,12) 就是一个不合法的公交路线，而 (3,6,9,...,57) 就是一个合法的公交路线

完全读懂题目后，我们可以很快想到解题思路————

(1.) 预处理出来所有合法的公交路线，每个公交路线是一个等差数列，用二元组 ((x,d)) 来表示，(x) 是首项，(d) 是公差，说明这个路线的公交车到站时刻分布在 (x+d,x+2d,...,x+kd)（(k) 是满足 (x+kd<60) 的最大非负整数）这些时刻。

预处理这里有一个细节：注意 (3,6,9,...,57) 和 (6,9,...,57)，后者甚至不是一个合法的公交路线。我们要避免枚举这种情况，就要保证 (x-d<0 => d>x) （这样就保证了 (x-d) 不在 (0-59)，没有更小的起点）

(2.) Dfs实现组合型枚举 + IDfs，我们枚举哪些公交路线叠加起来可以刚好填满所有的时刻。
(3.) 剪枝优化：

1. ~~喜闻乐见~~ 的优化枚举顺序：我们要尽可能地在每一次枚举公交路线的时候多影响一些点，那么我们可以按每一条公交路线影响的点从大到小排序

2. 附加剪枝（很有用）：如果我们还可以枚举 (k) 个公交路线，又因为我们已经把公交路线从大到小排序，假设当前我们从 (now) 开始枚举，(now) 这条公交路线有 (m) 个点，当前已经影响了 (s) 个点，总共有 (n) 个点，如果 (s+k*m < n) 的话，那么直接 return（因为最多还能影响 (k*m) 个点，加起来都还不够的话，这条分支就不能成功）

我不会分析时间复杂度qwq，本来是组合型枚举的Dfs复杂度，加上剪枝后就跑得飞快了 %>_<%

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
using namespace std;
inline int read() {
	int x=0,f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
	return x * f;
}
const int N = 67, MAXN = 3607;
int n,cnt,idt;
int bus[N];
struct Node {
	int x,d,nums;
	bool operator < (const Node &el) const {
		return nums > el.nums;	//经典剪枝：优化搜索顺序，从大到小搜 
	}
}route[MAXN];	//route 线路 
inline bool check(int x,int d) {
	for(int i=x;i<60;i+=d)
		if(!bus[i]) return false;
	return true;
}
bool Dfs(int dep,int now,int res) {
	if(dep == idt) return (res == n);
	if(res+(idt-dep)*route[now].nums < n) return false;	//在线剪枝 
	for(int i=now;i<=cnt;++i) {
		int x = route[i].x, d = route[i].d, nums = route[i].nums;
		if(check(x,d)) {
			for(int j=x;j<60;j+=d) bus[j]--;
			if(Dfs(dep+1,i,res+nums)) return true;
			for(int j=x;j<60;j+=d) bus[j]++;
		}
	}
	return false;
}
int main()
{
	n = read();
	for(int i=1,pos;i<=n;++i) {
		pos = read(); ++bus[pos];
	}
	for(int i=0;i<60;++i)
		for(int j=i+1;i+j<60;++j)
			if(check(i,j)) route[++cnt] = (Node)<%i,j,(59-i)/j+1%>;
	//printf("test cnt = %d
",cnt);
	sort(route+1, route+1+cnt);
	idt = 0;
	while(!Dfs(0,1,0)) {
		++idt;
		if(idt > 17) {
			puts("Unkown Problems!");
			return 0;
		}
	}
	printf("%d
",idt);
	return 0;
}

Summary

认真看题，认真分析，认真思考！！！

组合型枚举模型 Get
等差数列 Get
优化搜索顺序大法 Get