2018牛客多校赛第五场

A-gpa

题意

有n个课程,每个课程的学分是s[i],相应的绩点是c[i], 现在要去掉k门课,使得$\frac{\sum s[i]c[i]}{\sum s[i]}$ 最大

1≤ n≤ 105

0≤ k < n

1≤ s[i],c[i] ≤ 103

分析

分数规划问题

二分答案D,那么对于D有

$\sum si \geq 0$

浮点数二分这个答案,然后nlogn检查

代码

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
51
52
53
54
55
56
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define first fi
#define second se
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1e5 + 5;
const double eps = 1e-6;
int c[maxn], s[maxn], id[maxn];
int n, k;
double ans;

bool check(double x) {
vector<double> foo(n);
for (int i = 0; i < n; i++) foo[i] = s[i] * (c[i] - x);
sort(foo.begin(), foo.end(), greater<double>());
double ret = 0;
for (int i = 0; i < n - k; i++) {
ret += foo[i];
}
return ret > 0;
}
int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) scanf("%d", &s[i]);
for (int i = 0; i < n; i++) scanf("%d", &c[i]);
double l = 0, r = 1e3 + 4;
while (fabs(r - l) > eps) { // 这里也可以写成循环50次
double mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
l = mid;
} else
r = mid;
}
printf("%.8lf\n", ans);
}

B-div

题意

一个数 n 是好的,当且仅当 n^4 在 [n^2+1,n^2+2n] 之间有一个约数
给定 m,求>=m 的最小的好的 n

1<=m<=10^(1000)

分析

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# your code goes here
m = int(input())
a = [0,2,0]
i = 1
while(a[i] < m):
i = (i + 1) % 3
a[i] = a[(i-1 + 3) % 3] * 6 - a[(i-2+3) % 3]
ans = a[i]
i = 1
a = [0,6,0]
while(a[i] < m):
i = (i + 1) % 3
a[i] = a[(i-1 + 3) % 3] * 14 - a[(i-2+3) % 3]
ans = min(ans,a[i])
print(ans)

I-vcd

题意

有 n 个点,一个点集 S 是好的,当且仅当对于他的每个子集 T,存在一个右边无限长的
矩形,使得这个矩形包含了 T,但是和 S-T 没有交
求这 n 个点里有几个好的点集

1<=n<=10^5

分析

对于 |S|=1,他显然是好的

对于 |S|=2,只要两个点的 y 坐标不相同,那么这个集合也是好的

对于 |S|=3,三个点的形状必须是 < 型

对于 |S|>3,不可能任何三个点都是 < 型,所以一定不是好的

主要是对于|S|=3情况的统计

对于一个点(x,y),我们需要知道{(x1,y1) | x1 > x, y1 > y}的个数,和{(x1,y1) | x1 > x, y1 < y}的个数

这两个数相乘就是(x,y)对答案的贡献。

其实这个只要倒着统计,因为倒着统计就可以保证(x1 > x) 这个条件,然后用权值树状数组每次查大于y的数量和小于y的数量。 注意横坐标相等的情况是不合法的。

代码

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1e5 + 5;
const int mod = 998244353;
struct P {
int x, y;
bool operator<(const P& A) const {
if (x == A.x) return y < A.y;
return x < A.x;
}
};
P p[maxn];

int BIT[maxn];
inline int lowb(int x) { return x & (-x); }
inline int query(int l, int r) {
int ret = 0;
for (int i = l - 1; i > 0; i -= lowb(i)) ret -= BIT[i];
for (int i = r; i > 0; i -= lowb(i)) ret += BIT[i];
return ret;
}
inline void update(int x, int y, int n) {
for (int i = x; i <= n; i += lowb(i)) BIT[i] += y;
}

int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int n;
while (~scanf("%d", &n)) {
vector<int> x(n), y(n), tx(x), ty(n);
map<int, int> cnt;
for (int i = 0; i < n; i++) {
scanf("%d%d", &x[i], &y[i]);
tx[i] = x[i];
ty[i] = y[i];
}
my_sort_unique(x);
my_sort_unique(y);
for (int i = 0; i < n; i++) {
p[i].x = lower_bound(x.begin(), x.end(), tx[i]) - x.begin() + 1;
p[i].y = lower_bound(y.begin(), y.end(), ty[i]) - y.begin() + 1;
cnt[p[i].y]++;
}
ll ans = 0;
for (auto& v : cnt) {
ans += 1LL * (n - v.second) * v.second;
}
ans /= 2;
ans = (ans + n) % mod;
clr(BIT, 0);
sort(p, p + n);
int last = 0;
for (int i = n - 1; i >= 0; i--) {
int l = query(1, p[i].y - 1);
int r = (n - i - 1 - query(1, p[i].y));
if (i < n - 1 && p[i].x == p[i + 1].x)
last++;
else
last = 0;
ans += 1LL * l * (r - last);
ans %= mod;
// while (ans >= mod) ans -= mod;
update(p[i].y, 1, maxn - 1);
}
printf("%lld\n", ans);
}
}
Thank you for your support!