做app模板网站,怎么制作网站外链,提供手机自适应网站公司,四川建设人员信息查询题目#xff1a;洛谷 P9234 [蓝桥杯 2023 省 A] 买瓜 折半搜索
一开始觉得像dp#xff0c;试着写了#xff0c;显然过不了#xff0c;但我实在觉得搜索也过不了啊#xff0c;去看题解#xff0c;发现使用了折半搜索#xff08;每天都觉得啥都不会捏 折半搜索就是先搜一…题目洛谷 P9234 [蓝桥杯 2023 省 A] 买瓜 折半搜索
一开始觉得像dp试着写了显然过不了但我实在觉得搜索也过不了啊去看题解发现使用了折半搜索每天都觉得啥都不会捏 折半搜索就是先搜一半记录下答案再搜一半最后把答案整合在一起 比如这题每个数有三种选法复杂度3n折半后就是2*3n/2大大降低了 但是这个复杂度还是过不了后面就是不停优化剪枝
剪枝
剪枝1
当前和已经超过m (sum m)
剪枝2
当前劈瓜次数已经超过历史最优 (k ans)
剪枝3
达到同样的和曾经有过劈瓜数更小的方案 (mp.count(sum) mp[sum] k)
折半剪枝76分 用unordered_map更快
#include vector
#include iostream
#include cstdio
#include map
#include unordered_map
#include ctime
using namespace std;typedef long long ll;
const int N 35;ll a[N];
int ans N;
unordered_mapll, int mp;//unordered_map更快
ll n, m;void dfs1(int i, int k, ll sum)
{if (sum m) return;//超了剪if (k ans) return;if (sum m)//到了走了{ans min(ans, k);return; }if (mp.count(sum) mp[sum] k) return;//有过更优情况剪if (i n / 2)//到头了把搜到的东西记一下{//用map记录达到sum的砍刀数最小值if (mp.count(sum)) mp[sum] min(mp[sum], k);else mp[sum] k;return;}//先搜贡献大的更容易找到答案大概吧dfs1(i 1, k, sum a[i] a[i]);//整个dfs1(i 1, k 1, sum a[i]);//半个dfs1(i 1, k, sum); //不要
}void dfs2(int i, int k, ll sum)
{if (sum m) return;if (k ans) return;if (sum m){ans min(ans, k);return; }if (i n){//如果另一半有匹配的就更新答案if (mp.count(m - sum)) ans min(ans, k mp[m - sum]);return;}dfs2(i 1, k, sum a[i] a[i]);dfs2(i 1, k 1, sum a[i]);dfs2(i 1, k, sum);
}
int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin n m;m m;//为了不出现小数把a[i]当半个瓜用那么m也要翻倍for (int i 1; i n; i){cin a[i];}dfs1(1, 0, 0);dfs2(n/21, 0, 0);if (ans N) cout -1;else cout ans;return 0;
}继续看题解发现很重要的一点是要给数组排序 为什么呢不知道大家都不说 好像挺有道理的但是我说不出道理先放着
加上sort之后A了 觉得自己无敌了吧来看看这个 题目 3145: 蓝桥杯2023年第十四届省赛真题-买瓜 欸~一模一样的代码只有82分 最后是怎么过的呢要把数组从大到小排序 为什么呢 我的理解是在搜第二段的时候前面已经出现很多凑到m的情况使ans变小了所以第二段会被剪得更狠相比之下第一段则几乎都要搜到头所以重点在于要把第一段剪了。那有没有办法让第一段多剪掉一点呢就让第一段都是大数sum容易超过m就会多多被剪了
加上从大到小排序
sort(a 1, a n 1, greaterint()); 正当我欢天喜地地准备结束这题的时候我手欠地把从大到小版交到了洛谷 嘿——您猜怎么着TLE了 好吧我前边都是一顿瞎说但我真是觉得有道理啊 那只能是数据问题了但是数据问题要怎么A啊
剪枝4
后面我又翻看题解发现了一个新的剪枝 预处理后缀和当前sum加上后缀和也够不到m的话就直接剪 注意这个剪枝只能在第一段中使用因为第二段本身就要匹配第一段的答案没法判断会不会不够
void dfs1(int i, int k, ll sum)
{if (sum m) return;if (k ans) return;if (sum suf[i] m) return;//注意第i个还没加过所以是判断sum suf[i]if (sum m){ans min(ans, k);return; }if (i n / 2){if (mp.count(sum)) mp[sum] min(mp[sum], k);else mp[sum] k;return;}dfs1(i 1, k, sum a[i] a[i]);dfs1(i 1, k 1, sum a[i]);dfs1(i 1, k, sum);
}还有个注意点要sort之后再算后缀和对就是我这么傻 以及因为我存的a[i]算半个瓜算后缀和要算整个瓜所以要加两次
sort(a 1, a n 1, greaterint()); suf[n 1] 0;for (int i n; i 1; i--){suf[i] suf[i 1] a[i] a[i];}贴一个两边都能A的代码
#include vector
#include iostream
#include cstdio
#include map
#include unordered_map
#include ctime
#include algorithm
using namespace std;typedef long long ll;
const int N 35;ll a[N], suf[N];
int ans N;
unordered_mapll, int mp;
ll n, m;void dfs1(int i, int k, ll sum)
{if (sum m) return;//超了剪if (k ans) return;if (sum suf[i] m) return;//注意第i个还没加过所以是判断sum suf[i]if (sum m)//到了走了{ans min(ans, k);return; }if (mp.count(sum) mp[sum] k) return;//有过更优情况剪if (i n / 2)//到头了把搜到的东西记一下{//用map记录达到sum的劈瓜数最小值if (mp.count(sum)) mp[sum] min(mp[sum], k);else mp[sum] k;return;}//先搜贡献大的更容易找到答案大概吧dfs1(i 1, k, sum a[i] a[i]);//整个dfs1(i 1, k 1, sum a[i]);//半个dfs1(i 1, k, sum); //不要
}void dfs2(int i, int k, ll sum)
{if (sum m) return;if (k ans) return;if (sum m){ans min(ans, k);return; }if (i n){//如果另一半有匹配的就更新答案if (mp.count(m - sum)) ans min(ans, k mp[m - sum]);return;}dfs2(i 1, k, sum a[i] a[i]);dfs2(i 1, k 1, sum a[i]);dfs2(i 1, k, sum);
}
int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin n m;m m;//为了不出现小数把a[i]当半个瓜用那么m也要翻倍for (int i 1; i n; i){cin a[i];}//sort(a 1, a n 1); sort(a 1, a n 1, greaterint()); suf[n 1] 0;for (int i n; i 1; i--){suf[i] suf[i 1] a[i] a[i];}dfs1(1, 0, 0);dfs2(n/21, 0, 0);if (ans N) cout -1;else cout ans;return 0;
}结果就是加上这个剪枝从大到小排序洛谷能过了但是从小到大c语言网不行继续看 其他优化
我就不写了感觉好麻烦要把之前写的推翻重来orz
二分
不直接搜i1而是根据还需要的斤数在剩下的瓜里二分因为已经排序了嘛大于还需要的斤数的瓜可以不用考虑 这样二分甚至可以不用折半搜索 见 P9234 [蓝桥杯 2023 省 A] 买瓜 题解
手写哈希表
大概是因为unordered_map还是常数大了吧 见 买瓜 题解 参考
P9234 [蓝桥杯 2023 省 A] 买瓜 题解 买瓜 题解 买瓜题解 菜死我算了真在赛场上碰到这种题我就拿个30分吧默哀
