Process

今天题目不是很难，但是该拿的分没有拿到。第一题只想出来50分暴力，第二题做过原题，会正解做法但是被卡常。。。本来用的priority_queue，本地测发现会超时，然后换成了pb_ds，本地跑出来还蛮快的，结果别人用优先队列的有50分，我的只有30分。不过这次又学到了一种新的卡常技巧:make_heap()，好像可以基于数组或者vector实现，用在第二题上的话可以拿到满分。然后第三题不会，暴力好像打挂了

Score

50 + 30 + 0 = 80

Problems

A[TODO]

看着题解想了几个小时没看懂，std也没得，决定先留着，到时候问大佬去。

B[DONE]

agc018 C题coins原题 考前两周左右刚好做过，但是被卡常 + 评测机跑得这么慢，我还能说什么。。。 具体做法不赘述，见AGC018 C

C[TODO]

Learn

学到了新的卡常技巧，make_heap() 一些基础的操作： make_heap: 

1
2
3
4
int q[Maxn], L = 0
for (int i = 1; i <= M; ++i)
    q[++L] = A[i]
make_heap(q + 1, q + L + 1);

push_heap: 

1
2
q[++L] = x;
push_heap(q + 1, q + L + 1);

pop_heap: 

1
2
pop_heap(q + 1, q + L + 1);
L --;

堆顶元素即q[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
struct heap {
    int point;
    node data[Maxk];
    heap (){};
    inline int empty()
    {
        return !point;
    }
    inline void clear()
    {
        point = 0;
    }
    inline void push(node a) {
        data[++point] = a;
        push_heap(data + 1, data + point + 1);
    }
    inline node pop() {
        node res = data[1];
        pop_heap(data + 1, data + point + 1);
        --point;
        return res;
    }
    inline node top() {
        return data[1];
    }
}Q;