2 条题解
-
0
题意
给定 n 个数，求最少的等差数列个数，恰好覆盖 n 个数各一次;
至少 2 项，数值在 0 到 59 之间;
允许有重复的等差数列;
X 等差数列必须按规律在 [0,59] 之间出现;
分析
考虑到 DFS 超时，而答案在 17 以内，尝试 IDDFS;
预处理可能的等差数列，使得等差数列的每一项都在输入中出现;
维护 check 函数检查第 i 个等差数列的每一项是否都有出现，设找到 cnt 条;
将等差数列按项数从多到少排序，贪心选取，从而使得需要的公交路线最少;
维护 cnt_i 表示时间点 i 出现的车的数量;
/* 题意 给定 n 个数，求最少的等差数列个数，恰好覆盖 n 个数各一次; 至少 2 项，数值在 0 到 59 之间; 允许有重复的等差数列; X 等差数列必须按规律在 [0,59] 之间出现; 分析： 考虑到 DFS 超时，而答案在 17 以内，尝试 IDDFS; 预处理可能的等差数列，使得等差数列的每一项都在输入中出现; 维护 check 函数检查第 i 个等差数列（的每一项是否都有出现，设找到 cnt 条; 将等差数列按项数从多到少排序，贪心选取，从而使得需要的公交路线最少; 维护 cnt_i 表示时间点 i 出现的车的数量; */ #include<iostream> #include<bits/stdc++.h> using namespace std; const int maxn = 305; int cnt, dep, n, s[65]; struct node { int x, d, num; bool operator < (const node &a) const { return num > a.num; } }route[3600]; bool check(int x, int d) { for(int i = x; i < 60; i += d) if(s[i] == 0) return False; return True; } bool dfs(int cur, int k, int sum) //cur 层次，k线路， sum已经覆盖的车的数量 { if(cur == dep) return sum == n; if(sum + (dep-cur) * route[k].num < n) //可行性剪枝 return False; for(int i = k; i <= cnt; i++) { if(check(route[i].x, route[i].d) == True) { for(int j = route[i].x; j < 60; j += route[i].d) s[j]--; if(dfs(cur+1, i, sum + route[i].num) == True) //第i条路线还可以选!! return True; for(int j = route[i].x; j < 60; j += route[i].d) //回溯 s[j]++; } } return False; } int main() { cin >> n; //n车 for(int i = 1; i <= n; i++) { int x; cin >> x; //时间 s[x]++; //计数器 } for(int i = 0; i < 60; i++) //首项 { for(int d = i + 1; i + d < 60; d++) //公差 { if(check(i, d) == True) //找到可行的线路 { cnt++; route[cnt].x = i; //首项 route[cnt].d = d; //公差 route[cnt].num = (59-i) / d + 1; //覆盖的公交车数量 } } } sort(route + 1, route + cnt + 1); //按照覆盖的公交车数量从大到小排序 dep = 0; while(dfs(0, 1, 0) == False) //当前的深度，选择线路编号， 覆盖的总公交 dep++; cout << dep; return 0; } //注意这组数据 0 4 4 8 8 12 12 …… -
0
huangzheng
LV 6
@ 2025-10-8 16:55:22
/* 题意 给定 n 个数，求最少的等差数列个数，恰好覆盖 n 个数各一次; 至少 2 项，数值在 0 到 59 之间; 允许有重复的等差数列; X 等差数列必须按规律在 [0,59] 之间出现; 分析： 考虑到 DFS 超时，而答案在 17 以内，尝试 IDDFS; 预处理可能的等差数列，使得等差数列的每一项都在输入中出现; 维护 check 函数检查第 i 个等差数列的每一项是否都有出现，设找到 cnt 条; 将等差数列按项数从多到少排序，贪心选取，从而使得需要的公交路线最少; 维护 cnt_i 表示时间点 i 出现的车的数量; */ #include<bits/stdc++.h> using namespace std; const int maxn = 305; int cnt, dep, n, s[65]; struct node { int x, d, num; bool operator < (const node &a) const { return num > a.num; } }route[3600]; bool check(int x, int d) { for(int i = x; i < 60; i += d) if(s[i] == 0) return False; return True; } bool dfs(int cur, int k, int sum) //cur 层次，k线路， sum已经覆盖的车的数量 { if(cur == dep) return sum == n; if(sum + (dep-cur) * route[k].num < n) //可行性剪枝 return False; for(int i = k; i <= cnt; i++) { if(check(route[i].x, route[i].d) == True) { for(int j = route[i].x; j < 60; j += route[i].d) s[j]--; if(dfs(cur+1, i, sum + route[i].num) == True) //第i条路线还可以选!! return True; for(int j = route[i].x; j < 60; j += route[i].d) //回溯 s[j]++; } } return False; } int main() { cin >> n; //n车 for(int i = 1; i <= n; i++) { int x; cin >> x; //时间 s[x]++; //计数器 } for(int i = 0; i < 60; i++) //首项 { for(int d = i + 1; i + d < 60; d++) //公差 { if(check(i, d) == True) //找到可行的线路 { cnt++; route[cnt].x = i; //首项 route[cnt].d = d; //公差 route[cnt].num = (59-i) / d + 1; //覆盖的公交车数量 } } } sort(route + 1, route + cnt + 1); //按照覆盖的公交车数量从大到小排序 dep = 0; while(dfs(0, 1, 0) == False) //当前的深度，选择线路编号， 覆盖的总公交 dep++; cout << dep; return 0; } //注意这组数据 0 4 4 8 8 12 12 ……
- 1