codeforces 198 div.1

本文从WordPress迁移而来, 查看全部WordPress迁移文章

A.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,a[N],d[N];
LL SUM;

LL gcd(LL a , LL b){
return b == 0LL ? a : gcd(b,a%b);
}

int main(){
while(cin >> n){
a[0] = 0;
for(int i = 1; i <= n; i++)
cin >> a[i];

sort(a+1,a+n+1);

SUM = 0LL;
for(int i = 1; i < n; i++){
d[i] = a[i+1] - a[i];
SUM += (LL)a[i];
}
SUM += (LL)a[n];

LL UP = 0LL , DOWN = (LL)n;
for(int i = 1; i < n; i++){
LL CNT = (LL)(n-i) * (LL)i;
UP += (CNT * (LL)d[i]);
}
//cout << SUM << endl;
//cout << UP << endl;
UP *= 2LL;
UP += SUM;
LL GCD = gcd(UP,DOWN);
UP /= GCD;
DOWN /= GCD;
cout << UP << " " << DOWN << endl;
}
return 0;
}

B.

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
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define N 100010
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,a[N],c[N];

int binary(int key){
int low = 1 , high = n , ans = -1;
while(low <= high){
int mid = (low + high) >> 1;
if(key > c[mid]){
ans = mid+1;
low = mid + 1;
}
else high = mid - 1;
}
return ans;
}

int main(){
while(cin >> n){
for(int i = 1; i <= n; i++)
cin >> a[i];
cl(c,0x3f);
c[1] = a[1];
int ans = 1;
for(int i = 2; i <= n; i++){
int id = binary(a[i]);
if(id == -1) c[1] = a[i];
c[id] = a[i];
ans = max(ans,id);
}
cout << ans << endl;
}
return 0;
}