洛谷 P4571 BZOJ 2257 [JSOI2009]瓶子和燃料

淡淡的烟草味﹌ 2021-11-02 00:20 232阅读 0赞

[bzoj题目链接][bzoj]

> 上面hint那里是选择第2个瓶子和第3个瓶子

Time limit 10000 ms

Memory limit 131072 kB

OS Linux

Source Jsoi2009

## 吐槽 ##

故事是这样的：我本来要写下面列表最后那题题树剖，然后草稿纸上思考了好久也没有想出来怎么在区间更新的同时维护gcd，于是查了查，找到了下面列表的倒数第二题，各处题解都说题意显然是区间gcd，但盯着题面并没有看出哪里有gcd，反而想到的是这题——[\[USACO1.4\]母亲的牛奶 Mother's Milk][USACO1.4_ Mother_s Milk]。记搜？之后又找到了这题，终于知道小z的加油站怎么倒油了。

*  \[x\] BZOJ 2257 \[[JSOI2009\]瓶子和燃料][JSOI2009]
 *  \[ \] BZOJ 5028 [小z的加油站][z]
 *  \[ \] CodeChef DGCD [Dynamic GCD][]

博客园居然不支持markdown待办事项

## 解题思路 ##

题目应该再加一句话：\\(k\\leqslant n\\)。倒燃料的方式类似更相减损，减到不能减就是火星人付出的最少的燃料了。[我看这里看懂的][Link 1]  
由于数据范围不大，\\(n\\) 最大才1k，每个数字最大为\\(10^9\\)，所以可以暴力找因数，复杂度为\\(O(n\\sqrt\{\\max \{a\_i\}\})\\)。另外还需要统计所有因数的出现次数，直接用map就好，复杂度就再加个\\(\\log n\\times \\sum d(a\_i)\\)，其中\\(d(a\_i)\\)表示\\(a\_i\\)的因子总数。

## 源代码 ##

#include<map> #include<cstdio> int n,k; std::map<int,int> m;//离散化因数 std::map<int,int>::iterator it; int main() { scanf("%d%d",&n,&k); while(n--) { int a; scanf("%d",&a); for(int j=1;j*j<=a;j++)//枚举因子 { if(a%j==0) { m[j]++; if(a!=j*j) m[a/j]++; } } } for(it=m.end(),it--;it!=m.begin();it--)//一开始居然把这个循环放到了上面那个while里，WA了两发 { if(it->second>=k) { printf("%d\n",it->first); return 0; } } return 0; }

转载于:https://www.cnblogs.com/wawcac-blog/p/11315717.html

[bzoj]: https://vjudge.net/problem/197668/origin
[USACO1.4_ Mother_s Milk]: https://www.luogu.org/problem/P1215
[JSOI2009]: https://www.cnblogs.com/wawcac-blog/p/11315717.html
[z]: https://www.cnblogs.com/wawcac-blog/p/11317690.html
[Dynamic GCD]: https://www.cnblogs.com/wawcac-blog/p/11321076.html
[Link 1]: https://blog.csdn.net/clover_hxy/article/details/55504675