非常遗憾。当天晚上错过这一场。不过感觉也会掉分的吧。后面两题偏结论题，打了的话应该想不出来。

 

#include 
      
       using namespace std;inline int read() {    int x = 0, f = 1; char ch = getchar();    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }    return x * f;}int main() {    int a = read(), b = read();    if (a >= 13) b = b;    else if (a > 5) b /= 2;    else b = 0;    cout << b << '\n';    return 0; }
      

 

#include 
      
       using namespace std;inline int read() {    int x = 0, f = 1; char ch = getchar();    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }    return x * f;}int main() {    int r = read(), d = read(), x = read();    for (int i = 0; i < 10; i++) {        x = r * x - d;        printf("%d\n", x);    }    return 0;}
      

 

题意：有$N$张ID卡，编号为1到$N$，$M$扇门，每扇门对应着一个区间$\left[ L,R\right]$，在闭区间内的ID卡才能打开门，问有多少张ID卡能打开所有门。

思路：相当于$M$个区间求交集。然后就是求$L$的最大值和$R$的最小值，$L$大于$R$就无解，否则就是$R - L + 1$

#include 
      
       using namespace std;inline int read() {    int x = 0, f = 1; char ch = getchar();    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }    return x * f;}int main() {    int n = read(), m = read();    int l = 1, r = n;    while (m--) {        int u = read(), v = read();        l = max(l, u); r = min(r, v);    }    int ans;    if (l > r) ans = 0;    else ans = r - l + 1;    printf("%d\n", ans);    return 0;}
      

 

题意：给$N$张卡片，有$M$次操作，每次可以至多把$B$张卡片上的数改成$C$，问最后$N$个数的和最大是多少。

思路：可以证(举例)明(发现)，最后结果与操作顺序无关。

那么就把$N$个数放进小根堆，然后把操作按$C$ 的大小排，每次从最小的开始替换，如果最小的值比当前的$C$大就可以不用换了。这样保证了每个数最多进出队一次。

时间复杂度$O\left( n\log \left( n\right) \right)$(对吗?)

#include 
      
       #define ll long longusing namespace std;inline int read() {    int x = 0, f = 1; char ch = getchar();    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }    return x * f;}const int M = 1e5 + 10;struct P {    int b;ll c;    bool operator < (const P &rhs) const {        return c > rhs.c;          }} p[M];int main() {    int n = read(), m = read();    priority_queue
       
        , greater
        
          > que;    for (int i = 0; i < n; i++) {        int x = read();        que.push((ll)x);    }        for (int i = 0; i < m; i++) p[i].b = read(), p[i].c = (ll)read();    sort(p, p + m);    for (int i = 0; i < m; i++) {        int b = p[i].b;        if (p[i].c <= que.top()) break;        while (b--) {            if (que.top() < p[i].c) {                que.pop();                que.push(p[i].c);            } else {                break;            }        }    }    ll sum = 0;    while (!que.empty()) {        int x = que.top(); que.pop();        sum += x;    }    cout << sum << '\n';    return 0;}
        
       
      

 

题意：求一个网格图里面任取$K$点的曼哈顿距离之和

思路：$N\times M$的网格图里面任意两点的曼哈顿距离的平均值是$\dfrac {N+M}{3}$

答案就是$C^{k}_{N\times M}C^{2}_{k}\dfrac {N+M}{3}$

#include 
      
       #define ll long longusing namespace std;const ll MOD = 1e9 + 7;inline ll read() {    ll x = 0, f = 1; char ch = getchar();    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }    return x * f;}ll qp(ll a, ll b) {    ll ans = 1;    while (b) {        if (b & 1) ans = ans * a % MOD;        a = a * a % MOD;        b >>= 1;    }    return ans;}const int N = 2e5 + 10;ll fac[N];ll C(ll a, ll b) {    ll ans = fac[a] * qp(fac[b], MOD - 2) % MOD;    ans = ans * qp((fac[a-b] + MOD) % MOD, MOD - 2) % MOD;    return ans;}int main() {    fac[0] = 1;    for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % MOD;    ll n = read(), m = read(), k = read();    ll ans = C(n * m, k) * C(k, 2) % MOD * qp(3, MOD - 2) % MOD;    ans = ans * (n + m) % MOD;    ans %= MOD;    cout << ans << '\n';    return 0;}
      

 

题意：有函数$f\left( x\right)$初始为0，两个操作，1是给$f\left( x\right)$加上$\left| x-a\right| +b$，2是询问函数的最小值及$x$

思路：可以证(举例)明(发现)，函数的最小值一定$a$序列的中位数取到。

两个优先队列，一个降序一个升序，每次加入$a$都加入两个队列里，在比较他们的顶，降序的顶必须小于等于升序的顶，这样就能实现两个堆分别存储了序列的左半部分和右半部分。

同时，降序的顶就是取到的$x$

#include 
      
       using namespace std;inline int read() {    int x = 0, f = 1; char ch = getchar();    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }    return x * f;}int main() {    int q = read();    priority_queue
       
         l;    priority_queue
        

, greater

> r; long long ans = 0; while (q--) { int t = read(); if (t == 1) { int a = read(), b = read(); ans += b; l.push(a); r.push(a); if (l.top() > r.top()) { int x = l.top(); l.pop(); int y = r.top(); r.pop(); ans += abs(x - y); l.push(y); r.push(x); } } else { printf("%d %lld\n", l.top(), ans); } } return 0;}