51Nod 1305 Pairwise Sum and Divide

Output

输出fun(A)的计算结果。

Input示例

3

1 4 1

Output示例

4

first try:

#include "bits/stdc++.h"

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f3f

#define PI acos(-1)

#define N 100010

#define MOD 10

LL arr[N];

LL fun(int n){

    LL sum=;

    for(int i=;i<n;i++){

        for(int j=i+;j<n;j++){

            sum+=floor((arr[i]+arr[j])/(arr[i]*arr[j]));

        }

    }

    return sum;

}

int main()

{

    int n;

    while(~scanf("%d",&n)){

        for(int i=;i<n;i++){

            scanf("%d",&arr[i]);

        }

        LL ans=fun(n);

        printf("%d\n",ans);

    }

    return ;

}

time limit exceeded

second try:

(a + b)/ab = 1/a + 1/b  a>2且b>2时 不等式(a+b)/ab < 1  a,b不全为2时等号成立
取整后为0 ， 所以只用查找1和2，以及>=2的个数即可
公式：sum = 2(N1-1)*N1/2 + N1*(∑Nk  k>=2) + N2*(N2-1)/2

#include "bits/stdc++.h"

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f3f

#define PI acos(-1)

#define N 100010

#define MOD 10

int x,n;

int one, two, other;

int main()

{

    scanf("%d", &n);

    for (int i = ; i < n; i++) {

        scanf("%d", &x);

        if (x == )

            one++;

        if (x == )

            two++;

        if (x >= )

            other++;

    }

    LL sum = ;

    sum += (one-)*one + one*other + ( (two*(two-))>> );

    printf("%lld\n", sum);

    return ;

}

another:

1、观察算式：floor(A+B)/(A*B)，不难发现，如果其中A.B都是>=2的数值，那么对应的值一定是0.那么根据这个特性我们继续讨论：

①如果A=1&&B=1，那么值为2，

②如果A=1||B=1&&另外一个不是1，那么值为1，

③如果A=2&&B=2，那么值为1.

根据以上特性，我们肯定是要来判断a【i】==1||a【i】==2的个数来决定结果。

2、对于每一个1，我们考虑，其贡献出来的值为：n-1，那么我们一层for扫这个数组，如果有一个1，那么对应结果加上n-1.

接下来我们统计2的个数，对应在最终结果上加：（cont2-1+1）*（cont2-1）/2；

3、数据范围比较大，注意使用LL.

#include<stdio.h>

#include<string.h>

using namespace std;

#define ll __int64

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        ll cont2=;

        ll output=;

        for(int i=;i<n;i++)

        {

            int x;

            scanf("%d",&x);

            if(x==)

            {

                output+=n-;

            }

            if(x==)

            {

                cont2++;

            }

        }

        printf("%I64d\n",output+(cont2)*(cont2-)/);

    }

}

http://www.cnblogs.com/whileskies/p/7220026.html

http://www.voidcn.com/article/p-pymuhyiw-da.html

巴特西

51Nod 1305 Pairwise Sum and Divide | 思维数学

最新文章

热门文章

巴特西

51Nod 1305 Pairwise Sum and Divide | 思维 数学

最新文章

热门文章

51Nod 1305 Pairwise Sum and Divide | 思维数学