HDU 4609 3-idiots

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4609

题目翻译

给N个长度，问随机选择其中三个长度能组成三角形的概率。

题解

我们可以使用FFT处理出，用任意两个长度组成 K 的数量Sum[K]。
然后接下来，把长度排序，然后根据某个长度在数组中的位置容斥（按照数字大小容斥，好复杂。。推了半天弄不出来，看到题解里按照位置一下子就懂了。）
假设我们现在有一个长度 X（假装他是最长边）
首先两边之和大于第三边，Ans += Sum[k + 1] ~ Sum[maxLen]
然后我们减去这些长度中使用了 X 组成的长度的数量 Ans -= (n – 1)
然后我们减去使大于X和小于X的组成长度的数量 Ans -= (i – 1) * (n – i)
然后我们减去均大于X组成的长度的数量 Ans -= (n – i) * (n – i -1)

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
const double Pi = acos(-1.0);
const int N = 1e5;
struct complex {
    double r, i;
    complex(double r = 0, double i = 0):r(r), i(i) {}
    complex operator + (const complex &ot) const {
        return complex(r + ot.r, i + ot.i);
    }
    complex operator - (const complex &ot) const {
        return complex(r - ot.r, i - ot.i);
    }
    complex operator * (const complex &ot) const {
        return complex(r * ot.r - i * ot.i, r * ot.i + i * ot.r);
    }
}x1[N * 2 * 4];
void change(complex *y, int len) {
    for(int i = 1, j = len / 2; i < len - 1; ++i) {
        if(i < j) swap(y[i], y[j]);
        int k = len / 2;
        while(j >= k) {
            j -= k;
            k >>= 1;
        }
        j += k;
    }
}
void FFT(complex *y, int len, int on) {
    change(y, len);
    for(int h = 2; h <= len; h <<= 1) {
        complex wn = complex(cos(on * 2 * Pi / h), sin(on * 2 * Pi / h));
        for(int j = 0; j < len; j += h) {
            complex w = complex(1, 0);
            for(int k = j; k < j + h / 2; ++k) {
                complex u = y[k];
                complex t = y[k+h/2] * w;
                y[k] = u + t;
                y[k+h/2] = u - t;
                w = w * wn;
            }
        }
    }
    if(on == -1) {
        for(int i = 0; i < len; ++i)
            y[i].r /= len;
    }
}
const int Maxn = 1e5;
int n;
int num[Maxn + 5];
int maxLen = 0;
long long cnt[Maxn * 2 + 5];
long long sum[Maxn * 2 + 5];
long long del[Maxn + 5];
long long Ans, AllAns;
inline bool cmp(int a, int b)
{
    return a < b;
}
inline void solve()
{
    memset(cnt, 0 ,sizeof(cnt));
    memset(sum, 0 ,sizeof(sum));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &num[i]);
    maxLen = num[1];
    for (int i = 1; i <= n; i++)
    {
        maxLen = max(maxLen, num[i]);
        cnt[num[i]]++;
    }
    int len = ceil(log(maxLen * 2 + 5) / log(2)) + 1;
    len = 1 << len;
    for (int i = 0; i < len; i++) x1[i] = complex(0, 0);
    for (int i = 0; i <= maxLen; i++) x1[i] = complex(cnt[i], 0);
    //printf("OK!\n");
    FFT(x1, len, 1);
    //printf("OK!\n");
    for (int i = 0; i < len; i++) x1[i] = x1[i] * x1[i];
    //printf("OK!\n");
    FFT(x1, len, -1);
    //printf("OK!\n");
    AllAns = Ans = 0;
    for (int i = 0 ; i <= maxLen * 2; i++) sum[i] = ((long long)(x1[i].r + 0.1) - (long long)(i % 2 == 0 ? cnt[i / 2] : 0)) / (long long)2;
    //for (int i = 0 ; i <= maxLen * 2; i++) if (sum[i] != 0) printf("Len = %d => %d\n", i, sum[i]);
    for (int i = 1 ; i <= maxLen * 2; i++)
    {
        cnt[i] += cnt[i - 1];
        sum[i] += sum[i - 1];
    }
    sort(num + 1, num + n + 1, cmp);
    for(int i = 1;i <= n;i++)
    {
        Ans += sum[maxLen * 2] - sum[num[i]];
        Ans -= (long long)(n - i) * (i - 1);
        Ans -= (long long)(n - 1);
        Ans -= (long long)(n - i)*(n - i - 1) / 2;
    }
    AllAns = (long long)n * (long long)(n - 1) * (long long)(n - 2) / (long long)6;
    printf("%.7f\n",(double)Ans/(double)AllAns);
}
int main()
{
    freopen("in.txt", "r", stdin);
    int T = 0;
    while(scanf("%d", &T) != EOF)
        for (int i = 1; i <= T; i++)
            solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<iostream>

using namespace std;

const double Pi = acos(-1.0);

const int N = 1e5;

struct complex {

double r, i;

complex(double r = 0, double i = 0):r(r), i(i) {}

complex operator + (const complex &ot) const {

return complex(r + ot.r, i + ot.i);

}

complex operator - (const complex &ot) const {

return complex(r - ot.r, i - ot.i);

}

complex operator * (const complex &ot) const {

return complex(r * ot.r - i * ot.i, r * ot.i + i * ot.r);

}

}x1[N * 2 * 4];

void change(complex *y, int len) {

for(int i = 1, j = len / 2; i < len - 1; ++i) {

if(i < j) swap(y[i], y[j]);

int k = len / 2;

while(j >= k) {

j -= k;

k >>= 1;

}

j += k;

}

void FFT(complex *y, int len, int on) {

change(y, len);

for(int h = 2; h <= len; h <<= 1) {

complex wn = complex(cos(on * 2 * Pi / h), sin(on * 2 * Pi / h));

for(int j = 0; j < len; j += h) {

complex w = complex(1, 0);

for(int k = j; k < j + h / 2; ++k) {

complex u = y[k];

complex t = y[k+h/2] * w;

y[k] = u + t;

y[k+h/2] = u - t;

w = w * wn;

}

if(on == -1) {

for(int i = 0; i < len; ++i)

y[i].r /= len;

}

const int Maxn = 1e5;

int n;

int num[Maxn + 5];

int maxLen = 0;

long long cnt[Maxn * 2 + 5];

long long sum[Maxn * 2 + 5];

long long del[Maxn + 5];

long long Ans, AllAns;

inline bool cmp(int a, int b)

{

return a < b;

}

inline void solve()

{

memset(cnt, 0 ,sizeof(cnt));

memset(sum, 0 ,sizeof(sum));

scanf("%d", &n);

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

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

maxLen = num[1];

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

{

maxLen = max(maxLen, num[i]);

cnt[num[i]]++;

}

int len = ceil(log(maxLen * 2 + 5) / log(2)) + 1;

len = 1 << len;

for (int i = 0; i < len; i++) x1[i] = complex(0, 0);

for (int i = 0; i <= maxLen; i++) x1[i] = complex(cnt[i], 0);

//printf("OK!\n");

FFT(x1, len, 1);

//printf("OK!\n");

for (int i = 0; i < len; i++) x1[i] = x1[i] * x1[i];

//printf("OK!\n");

FFT(x1, len, -1);

//printf("OK!\n");

AllAns = Ans = 0;

for (int i = 0 ; i <= maxLen * 2; i++) sum[i] = ((long long)(x1[i].r + 0.1) - (long long)(i % 2 == 0 ? cnt[i / 2] : 0)) / (long long)2;

//for (int i = 0 ; i <= maxLen * 2; i++) if (sum[i] != 0) printf("Len = %d => %d\n", i, sum[i]);

for (int i = 1 ; i <= maxLen * 2; i++)

{

cnt[i] += cnt[i - 1];

sum[i] += sum[i - 1];

}

sort(num + 1, num + n + 1, cmp);

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

{

Ans += sum[maxLen * 2] - sum[num[i]];

Ans -= (long long)(n - i) * (i - 1);

Ans -= (long long)(n - 1);

Ans -= (long long)(n - i)*(n - i - 1) / 2;

}

AllAns = (long long)n * (long long)(n - 1) * (long long)(n - 2) / (long long)6;

printf("%.7f\n",(double)Ans/(double)AllAns);

}

int main()

{

freopen("in.txt", "r", stdin);

int T = 0;

while(scanf("%d", &T) != EOF)

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

solve();

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑

HDU 4609 3-idiots

题目翻译

题解

代码

扫一扫支付

评论放弃治疗

创作日历

文章

标签云

最近访客

HDU 4609 3-idiots

题目翻译

题解

代码

扫一扫支付

评论 放弃治疗

评论放弃治疗