codeforces 340C Tourist Problem(简单数学题)

时间:2023-02-06 18:28:19

题意:固定起点是0,给出一个序列表示n个点,所有点都在一条直线上,其中每个元素代表了从起点到这个点所走的距离。已知路过某个点不算到达这个点,则从起点出发,到达所有点的方案有许多种。求所有方案走的总路程/方案数,输出分子、分母,要求不含约数。

e.g:n=3 {2,3,5},{2,3,5}{2,5,3}{3,2,5}{3,5,2}{5,2,3}{5,3,2},总路程(5+7+7+8+9+8)=44,答案44/6=22/3,输出“22 3”。

分析:

1、以n=3序列{a1,a2,a3}为例,实际上是{0,a1,a2,a3},起点确定,总共有n!中方案。

2、经过简单的思考就可以发现,每种方案的第一步比较特殊,因此分类讨论:

  一、0->ak:这条线段会出现(n-1)!次,那么所有方案的第一步之和=(0->a1)*(n-1)!+(0->a2)*(n-1)!+(0->a3)*(n-1)!=(a1+a2+a3)*(n-1)!

  二、ai->aj:既然是线段,在序列上必然是连续出现。形如ai->aj的线段会出现在第2步~第n步的任意一处位置,出现的次数为(n-2)!,所以ai->aj出现的总次数为(n-1)*(n-2)!=(n-1)!,那么所有方案的第2步~第n步之和=(a1->a2)*(n-1)!+(a2->a1)*(n-1)!+(a1->a3)*(n-1)!+(a3->a1)*(n-1)!+(a2->a3)*(n-1)!+(a3->a2)*(n-1)!=2*(|a1-a2|+|a1-a3|+|a2-a3|)*(n-1)!

3、“一”与“二”之和就是总路程,约掉(n-1)!后,答案就是:[(a1+...+an)+2*(∑|ai-aj|)]/n,(i!=j)

4、由于数据范围是105,直接枚举计算|ai-aj|会超时。

  注意:计算|ai-aj|实际上就是计算序列{a1,a2,a3,a4}任意两条线段的长度之和。利用ai->aj覆盖了ai->a(j-1),从左向右观察,则以a2结束的线段只有S1=a1->a2,以a3结束的线段有a1->a3,a2->a3,其中a1->a3可以看做a1->a2+a2->a3,这里a1->a2已经计算好了,所以S2=S1+2*(a2->a3)。同理,以a4结束的线段有a1->a4,a2->a4,a3->a4,不考虑a3->a4,其余的均是将以a3结束的线段延长a3->a4,所以S3=S2+3*(a3->a4)。

  状态方程:Si=S(i-1)+i*|ai-a(i+1)|

注意:

1、long long T^T

2、给出的序列是乱序的

codeforces 340C Tourist Problem(简单数学题)codeforces 340C Tourist Problem(简单数学题)
 1 #include<stdio.h>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #define LL long long
 6 using namespace std;
 7 
 8 const int MAXN=111111;
 9 
10 int cmp(int a,int b)
11 {
12     return a<b;
13 }
14 
15 LL gcd(LL a,LL b)
16 {
17     if(a%b==0)return b;
18     gcd(b,a%b);
19 }
20 
21 int a[MAXN];
22 
23 int main()
24 {
25     LL n,cnt=0;
26     scanf("%lld",&n);
27     for(int i=1;i<=n;i++)
28     {
29         scanf("%d",&a[i]);
30         cnt+=a[i];
31     }
32     a[0]=0;
33     sort(a,a+n+1,cmp);
34     LL ans=0,s=0;
35 
36     for(int i=1;i<n;i++)
37     {
38         s+=(a[i+1]-a[i])*i;
39         ans+=s*2;
40     }
41 
42     LL x=gcd(ans+cnt,n);
43     printf("%lld %lld\n",(ans+cnt)/x,n/x);
44     return 0;
45 }
View Code