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

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

Time limit 10000 ms

Memory limit 131072 kB

OS Linux

Source Jsoi2009

吐槽

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

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

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

解题思路

题目应该再加一句话：\(k\leqslant n\)。倒燃料的方式类似更相减损，减到不能减就是火星人付出的最少的燃料了。我看这里看懂的

由于数据范围不大，\(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;

}

巴特西

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

吐槽

解题思路

源代码

最新文章

热门文章