Patting Heads 轻拍牛头 bzoj-1607 Usaco-2008 Dec

题目大意：题目链接。

注释：略。

想法：我们发现，位置是没有关系的。

故，我们考虑将权值一样的牛放在一起考虑，cnt[i]表示高度为i的牛的个数。

之后考虑每个权值的牛造成的贡献即可，就是向后枚举。

时间复杂度是调和数列，$O(nlogn)$。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 100010

#define M 1000010

using namespace std; int n,ans[M],a[N],maxn,stack[M];

inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}

int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}

int main()

{

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

    for(int i=1;i<=n;i++) if(stack[a[i]])

    {

        int k=a[i];

        while(k<=maxn)

        {

            ans[k]+=stack[a[i]];

            k+=a[i];

        }

        stack[a[i]]=0;

    }

    for(int i=1;i<=n;i++) printf("%d\n",ans[a[i]]-1);

	return 0;

}

小结：无。

巴特西

[bzoj1607][Usaco2008 Dec]Patting Heads 轻拍牛头_筛法_数学

Patting Heads 轻拍牛头 bzoj-1607 Usaco-2008 Dec

最新文章

热门文章