除草向

博客好久没有更新了，自从打完补选赛之后就一直一副颓废状态，外加要期末考，得预习课内知识(虽然我到最后还是。。。)，不管怎么样，现在以及放假了，所以我打算兑现之前对自己的承诺，暑假好好做题，所以这段时间应该会比较经常更新一些水题的题解啦( ´ ▽ ` )ﾉ。昨天选拔赛第一场就爆零滚粗，作为一名候补选手，我只剩下今天这个最后一次机会了，好伤感的说T^T，希望写一写题解涨张RP。。。

吐槽完毕，接下来进入正题啦～ ，虽然以前偶尔也又写过树状数组的题目，不过基本就没去记住，然后每次都得看模版。。。这两天写了两三次，终于记住啦啦啦啦

  1. Star

题目大衣：一个二维平面上又N (1 ≤ N ≤ 15000)个点(0 ≤ X,Y ≤ 32000)，然后定义每个点的level，对于点i，它的level为横纵坐标均不大于点i的点的个数。要求输出0～N-1的各个level的的点数。

这道题的只要求出每个点的level，统计一下就行了。然后就是求level的办法了，我们首先可以把每个点先按x递增，然后y递增的顺序排序。这样x就有序了，然后我们顺序处理每个点，对一个点Pi，已知点Pj(j<i)的x不大于Pi的x，然后要做的就是统计一下Pj中y小于等于Pi的y的个数。我们用c[i]表示y为i的点的个数，Pi的level值就为sum＝ c[0] + c[1] + .. + c[y-1], 然后再更新一下c数组，c[y]+1,以上都可以用树状数组来解决。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int MN = 32001;

struct pt{
    int x, y;
};

pt a[MN/2];
int level[MN/2];
int t[MN+10];

bool comp(const pt &a, const pt &b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

inline int lowbit(int x) {
    return (x & -x);
}

void add(int x, int value) {
    for (int i = x; i <= MN; i += lowbit(i))
        t[i] += value;
}

int get(int x) {
    int sum = 0;
    for (int i = x; i; i -= lowbit(i))
        sum += t[i];
    return sum;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
    }
    sort(a, a+n, comp);
    for (int i = 0; i < n; i++) {
        int k = a[i].y+1;
        level[get(k)]++;
        add(k, 1);
    }
    for (int i = 0; i < n; i++)
        printf("%d\n", level[i]);
    return 0;
}
  1. Electronic Auction

题目大衣：好像是拍卖铁猪来着，价格0.01～10000.00，最多两位小数。然后有几个操作：

  • BID X 以X元竞标一头猪
  • DEL X 取消一个价格为X的竞标
  • SALE X K 以X元卖掉K头猪
  • QUIT 结束输入

对于每一个SALE，前K个出价不小于X的客户可以得到一头猪，如果不够K个客户满足条件，自然是能买出多少就多少了，每卖出一头获利0.01，求最大获利好像差不多就是这样了把。

然后其实我们可以把每个数乘上100，就变成整数，不过直接这样好像会有精度问题，我因此WA了几次，后来看了讨论区，弄了个修正的办法。数组a[i]表示出价X的客户数，然后就直接套树状数组了吧，SALE的时候就是求a[i]~a[maxn],这个一个除法也就出来了。

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

const int MN = 1000000;

char str[5];
double d;
int f[MN+10] = {0};

inline int lowbit(int x) {
    return (x & -x);
}

void add(int x, int value) {
    for (int i = x; i <= MN; i += lowbit(i))
        f[i] += value;
}

int get(int x) {
    int sum = 0;
    for (int i = x; i; i -= lowbit(i))
        sum += f[i];
    return sum;
}

int main() {
    cin >> str;
    double ans = 0;
    int k;
    while (str[0] != 'Q') {
        if (str[0] == 'B') {
            scanf("%lf", &d);
            add(int(d*100 + 0.5), 1);
        } else if (str[0] == 'D') {
            scanf("%lf", &d);
            add(int(d*100 + 0.5), -1);
        } else if (str[0] == 'S') {
            scanf("%lf%d", &d, &k);
            int t = int(d*100 + 0.5);
            int ts = get(MN) - get(t-1);
            ans += min(k, ts);
        }
        scanf("%s", str);
    }
    ans /= 100.0;
    printf("%.2f\n", ans);
    return 0;
}

因为赶着要去吃饭然后打选拔赛去了，所以后面没怎么想好表达就乱写了，实在想在比赛前写完。故事不会就这样终结的，