百度之星初赛一

A: 每次贪心打能打的最大的就好了。

B: 离散化之后直接暴力枚举,复杂度1000 × 10000,我比较逗,用了单调队列维护最值

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
90
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 100010;
int a[N],b[N],vis[N];
struct DQ{
    int f,r;
    int c[N];
    int v[N];
    void init(){f=0;r=-1;}
    inline void pop(int cc) {
        while(f<=r && c[f]<=cc) f++; 
    }
    inline void pop() {
        f++;
    }
    inline void push(int cc,int vv,bool flag=true) {
        if(flag) while(f<=r && vv>=v[r]) r--;
        else     while(f<=r && vv<=v[r]) r--;
        ++r;
        c[r]=cc;
        v[r]=vv;
    }
    inline int top()//取队首元素
    {
        if(f>r) return -1;
        return v[f];
    }
    inline bool empty()//判队列是否为空
    {
        return f>r;
    }
    int size()//队首与队尾之间的距离
    {
        return c[r]-c[f]+1;
    }
}q1, q2;
int id[N];
int cmp(int i, int j)
{
    return a[i] < a[j];
}
int main()
{
    int n, m,ca=1;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        id[i] = i;
    }
    std::sort(id, id + n, cmp);
    b[id[0]] = 0;
    for(int i = 1; i < n; i++) if(a[id[i]]-a[id[i-1]]>1) {
        b[id[i]] = b[id[i-1]] + 2;
    } else {
        b[id[i]] = b[id[i-1]] + ((a[id[i]] == a[id[i - 1]]) ? 0 : 1);
    }
//for(int i = 0; i < n; i++) printf("%d ", b[i]);puts("");
    printf("Case #%d:\n", ca++);
    for(int i = 0; i < m; i++) {
        int k;
        scanf("%d", &k);
        q1.init(); q2.init();
        memset(vis, false, sizeof(vis));
        int tot = 0, ret = 0;
        for(int j = 0; j < n; j++) {
            vis[b[j]]++;
            if(vis[b[j]] == 1) {
                tot++;
            }
            if(j >= k) {
                vis[b[j - k]]--;
                if(vis[b[j - k]] == 0) {
                    tot--;
                }
            }
            q1.push(j, b[j], true);
            q2.push(j, b[j], false);
            q1.pop(j - k);
            q2.pop(j - k);
            int mx = q1.top(), mi = q2.top();
        //    printf("mx=%d mi=%d tot=%d\n", mx, mi, tot);
            if(tot == k && mx - mi == k - 1) {
                ret++;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

 

C: 二分 ,验证的时候应该尽可能使得前一个数尽可能小。

D: 离线离散化之后用线段树找第k大。或者直接用set,因为中位数的偏移位置最多为1.

E:模拟一轮之后,求出所有环的长度的最小公倍数即可。

比如一开始的颜色块是1 2 3 4 5 ,旋转后变成了2 1 5 3 4

那么需要六次。

F:求出凸包后暴力枚举长方形的某条边(肯定和凸包的某条边靠在一起),然后找到离这条边最远的点,然后再往这条高的垂直方向找最远的,更新答案。

发表评论

电子邮件地址不会被公开。 必填项已用*标注