Codeforces Round #198 (Div. 2)C,D题解

接着是C,D的题解

C. Tourist Problem

Iahub is a big fan of tourists. He wants to become a tourist himself, so he planned a trip. There are n destinations on a straight road that Iahub wants to visit. Iahub starts the excursion from kilometer 0. The n destinations are described by a non-negative integers sequence a1, a2, ..., an. The number ak represents that the kth destination is at distance ak kilometers from the starting point. No two destinations are located in the same place.

Iahub wants to visit each destination only once. Note that, crossing through a destination is not considered visiting, unless Iahub explicitly wants to visit it at that point. Also, after Iahub visits his last destination, he doesn't come back to kilometer 0, as he stops his trip at the last destination.

The distance between destination located at kilometer x and next destination, located at kilometer y, is |x - y| kilometers. We call a "route" an order of visiting the destinations. Iahub can visit destinations in any order he wants, as long as he visits all n destinations and he doesn't visit a destination more than once.

Iahub starts writing out on a paper all possible routes and for each of them, he notes the total distance he would walk. He's interested in the average number of kilometers he would walk by choosing a route. As he got bored of writing out all the routes, he asks you to help him.

input

3
2 3 5

output

22 3

Note

Consider 6 possible routes:

• [2, 3, 5]: total distance traveled: |2 – 0| + |3 – 2| + |5 – 3| = 5;
• [2, 5, 3]: |2 – 0| + |5 – 2| + |3 – 5| = 7;
• [3, 2, 5]: |3 – 0| + |2 – 3| + |5 – 2| = 7;
• [3, 5, 2]: |3 – 0| + |5 – 3| + |2 – 5| = 8;
• [5, 2, 3]: |5 – 0| + |2 – 5| + |3 – 2| = 9;
• [5, 3, 2]: |5 – 0| + |3 – 5| + |2 – 3| = 8.

The average travel distance is  =  = .

一句话题意:(呃呃好像有点麻烦)

给定n个数,以样例来看,求出所有的全排列,然后在序列前面加一个0,

再求出序列中每个相邻的数的差值的绝对值之和(大概根据样例意会一下)

然后做法的话,我选择了直接推公式

首先n个数的全排列一共有n!种

如果我们抛去第一个数和0的差值,只计算后面的值

就比如 0 2 3 5, 只计算|3 – 2| + |5 – 3| = 3

那么每一种排列一共有n-1个间隔,那么总间隔数就是n!*(n-1)

其次这n个数一共可以组成n*(n-1)/2种不同的间隔

因此每一种不同的间隔一共会有n!*(n-1)/n/(n-1)*2=(n-1)!*2种

最后我们在加上每个数和0的差值,每个差值的个数为n!/n=n-1

我们用2 3 5来举例

[2, 3, 5]: |2 – 0| + |3 – 2| + |5 – 3|

[2, 5, 3]: |2 – 0| + |5 – 2| + |3 – 5|

[3, 2, 5]: |3 – 0| + |2 – 3| + |5 – 2| 

[3, 5, 2]: |3 – 0| + |5 – 3| + |2 – 5| 

[5, 2, 3]: |5 – 0| + |2 – 5| + |3 – 2| 

[5, 3, 2]: |5 – 0| + |3 – 5| + |2 – 3| 

首先不同的间隔为(2,3),(2,5),(3,5),每种间隔一共有(n-1)!*2=4种

然后和0之间的间隔(0,2),(0,3),(0,5),一共有n-1=2种

因此将所有的间隔和相加就行了

***另外你需要用O(a[i])的复杂度而不是O(n^2)的

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
#define N 10000010
ll a[N],sum=0,s=0,ans=0,x; int n;
bool bo[N];
int main(){
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    memset(bo,0,sizeof(bo));
    for(int i=1;i<=n;++i)
        scanf("%lld",&x),s+=x,a[x+1]++,bo[x]=1;
    for (int i=1;i<=N;++i){
        a[i]+=a[i-1];
        if (bo[i]) ans+=a[i]*i-sum+abs(i*(n-a[i])-(s-sum)),sum+=i;
    }
    ll x=ans+s,y=n,gcd=__gcd(x,y);
    x/=gcd; y/=gcd;
    printf("%lld %lld",x,y);
}

D. Bubble Sort Graph

Iahub recently has learned Bubble Sort, an algorithm that is used to sort a permutation with n elements a1, a2, ..., an in ascending order. He is bored of this so simple algorithm, so he invents his own graph. The graph (let's call it G) initially has n vertices and 0 edges. During Bubble Sort execution, edges appear as described in the following algorithm (pseudocode).

procedure bubbleSortGraph()
    build a graph G with n vertices and 0 edges
    repeat
        swapped = false
        for i = 1 to n - 1 inclusive do:
            if a[i] > a[i + 1] then
                add an undirected edge in G between a[i] and a[i + 1]
                swap( a[i], a[i + 1] )
                swapped = true
            end if
        end for
    until not swapped 
    /* repeat the algorithm as long as swapped value is true. */ 
end procedure

For a graph, an independent set is a set of vertices in a graph, no two of which are adjacent (so there are no edges between vertices of an independent set). A maximum independent set is an independent set which has maximum cardinality. Given the permutation, find the size of the maximum independent set of graph G, if we use such permutation as the premutation a in procedure bubbleSortGraph.

input

3
3 1 2

output

2

Note

Consider the first example. Bubble sort swaps elements 3 and 1. We add edge (1, 3). Permutation is now [1, 3, 2]. Then bubble sort swaps elements 3 and 2. We add edge (2, 3). Permutation is now sorted. We have a graph with 3 vertices and 2 edges (1, 3) and (2, 3). Its maximal independent set is [1, 2].

一句话题意:O(nlogn)求出最长不下降子序列

下面我们来解释为什么是最长不下降子序列

它所给的这段程序,大意是将将所有i<j,a[i]>a[j]中的i和j连上一条边,那么我们想如果没有连上的

是不是就是i<j,a[i]<=a[j]的所有序号,那么这不就是裸的最长严格不下降子序列,

***因为n为1e5,所以你得用O(nlogn)来处理,我是用树状数组来维护

简单的讲一下,就是从前往后add(a[i],f[i]),那么ask时就是求从1到a[i]的前缀和,

因为1到a[i]内的数都是比a[i]小的QAQ

#include<bits/stdc++.h>
using namespace std;
int ans,a[100010],c[100010],n,t;
void add(int pos,int x){
    while (pos<=n) 
        c[pos]=max(c[pos],x),pos+=pos&-pos;
}

int ask(int pos){
    int res=0;
    while (pos) 
        res=max(res,c[pos]),pos-=pos&-pos;
    return res;
}

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;++i){
        scanf("%d",&a[i]); t=ask(a[i]-1)+1;
        ans=max(ans,t); add(a[i],t);
    }
    printf("%d",ans);
}