浅谈桶排思想及[USACO08DEC]Patting Heads 题解

一、桶排思想

1.通过构建n个空桶再将待排各个元素分配到每个桶。而此时有可能每个桶的元素数量不一样，可能会出现这样的情况：有的桶没有放任何元素，有的桶只有一个元素，有的桶不止一个元素可能会是2+；

2.按照下标对内容非0的桶按个数输出下标；

二、[USACO08DEC]Patting Heads题解

Description

Solution

1.题目意为输出所有当前手上纸条数为当前牛手上纸条数因子的牛的序号。

2.因为数据规模到了1e6所以有很大概率有重复标记，使用桶排思路，a数组记地址，num数组用桶排计数，ans数组记录因子个数；

3.从较小的数开始对其倍数进行ans数组中因数的累加；

4.因为自己作为自己的因子也会被累加记得最后对结果-1，用a数组记地址作下标输出ans[a[i]]-1;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

inline int rd()

{

	int x=0;

	char c;

	c=getchar();

	while(c<'0'||c>'9') c=getchar();

	while(c<='9'&&c>='0')                                    //邢神的读入优化

	{

		x=(x<<1)+(x<<3)+(c^48);

		c=getchar();

	}

	return x;

}

int n,Max,a[100005],num[1000005],ans[1000005];

int main()

{

    n=rd();

    for (int i=1;i<=n;i++) a[i]=rd(),num[a[i]]++,Max=max(Max,a[i]);

    for (int i=1;i<=Max;i++)

	{

        if (num[i]==0) continue;

        for (int j=i;j<=Max;j+=i) ans[j]+=num[i];  //桶排思想对Max内i的倍数进行因数的累加

    }

    for (int i=1;i<=n;i++) printf("%d\n",ans[a[i]]-1);   //(因为自己作为自己的因子也会被累加记得最后对结果-1)用a数组记地址作下标输出ans[a[i]]-1

    return 0;

}