首页 模拟赛

树状数组，dp + 矩阵乘法

# A. 空

O(n2)O(n^2) 暴力就不多说了。

分两种情况讨论。

  • 线段 i,ji, j 不包含，且 ii 在 jj 右边，线段异或值为 (ri−lj)−(rj−li)(r_i - l_j) - (r_j - l_i)，开括号得 (li+ri)−(lj+rj)(l_i + r_i) - (l_j + r_j)，这里 li+ril_i + r_i 是定值，如果我们想让整体最大，那么 lj+rjl_j + r_j 最小，树状数组维护即可。
  • 线段 jj 包含线段 ii，那么异或值为 (rj−lj)−(ri−li)(r_j - l_j) - (r_i - l_i)，要使异或值最大，那么 rj−ljr_j - l_j 最大，同样使用树状数组维护即可。

时间复杂度 O(nlog⁡n)O(n\log n)

codecode

我这里为了方便，第一种情况维护的 −lj−rj-l_j - r_j 的最大值，这样写一个结构体就行了。

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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 4e5 + 10;
int n, ans;
struct node{
    int l, r;
    inline bool operator < (const node &b) const{
        return l != b.l ? l < b.l : r < b.r;
    }
}p[N];
int b[N], tot;

inline void init(){
    for(int i = 1; i <= n; ++i){
        p[i] = (node){read(), read()};
        b[++tot] = p[i].l, b[++tot] = p[i].r;
    }
    sort(b + 1, b + 1 + tot);
    tot = unique(b + 1, b + 1 + tot) - b - 1;
    sort(p + 1, p + 1 + n);
    for(int i = 1; i <= n; ++i){
        p[i].l = lower_bound(b + 1, b + 1 + tot, p[i].l) - b;
        p[i].r = lower_bound(b + 1, b + 1 + tot, p[i].r) - b;
    }
}

struct BIT{
    int c[N];
    BIT() {memset(c, -0x3f, sizeof(c));}

    inline void add(int x, int y){
        for(; x; x -= x & (-x)) c[x] = max(c[x], y);
    }

    inline int qry(int x){
        int res = -1e9;
        for(; x <= tot; x += x & (-x)) res = max(res, c[x]);
        return res;
    }
}c1, c2;

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), init();
    for(int i = 1; i <= n; ++i){
        ans = max(ans, b[p[i].l] + b[p[i].r] + c1.qry(p[i].l));
        ans = max(ans, c2.qry(p[i].l) - (b[p[i].r] - b[p[i].l]));
        c1.add(p[i].r, -b[p[i].l] - b[p[i].r]);
        c2.add(p[i].r, b[p[i].r] - b[p[i].l]);
    }
    write(ans), puts("");
    return 0;
}

# B. 早苗

套路的设 fi,jf_{i, j} 表示到了第 ii 天，连续 jj 天刮不同的风的方案数。

转移方程：

fi+1,j+1+=fi,j×(m−j)fi+1,k+=fi,j(k∈[1,j])f_{i + 1, j + 1} += f_{i, j} \times (m - j) \\ f_{i + 1, k} += f_{i, j}(k \in [1, j])

这个比较好理解吧。

然后就能拿到 80pts\text{80pts} 的好成绩了。

其实 dp\text{dp} 到这里使用矩阵乘法优化也很显然了，随便构造个矩阵快速幂一下即可。

codecode

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
#include <bits/stdc++.h>
#define pb push_back
#define int long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 10;
const int M = 110;
const int mod = 1e9 + 7;
int n, m;

inline int add(int x) {return x >= mod ? x - mod : x;}

struct Matrix{
    int num[M][M];
    Matrix() {memset(num, 0, sizeof(num));}

    Matrix operator * (const Matrix &b) const{
        Matrix r;
        for(int i = 1; i < m; ++i)
            for(int j = 1; j < m; ++j)
                for(int k  = 1; k < m; ++k)
                    r.num[i][j] = add(r.num[i][j] + num[i][k] * b.num[k][j] % mod);
        return r;
    }

    Matrix operator ^ (int p) const{
        Matrix r, a;
        memcpy(a.num, num, sizeof(num));
        for(int i = 0; i <= m + 2; ++i) r.num[i][i] = 1ll;
        for(; p; a = a * a, p >>= 1ll)
            if(p & 1) r = r * a;
        return r;
    }
}f, A;

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin); 
    freopen("test.out", "w", stdout);
#endif
    n = read(), m = read();
    for(int i = 1; i < m; ++i) A.num[i][i + 1] = m - i;
    for(int i = 1; i < m; ++i)
        for(int j = 1; j <= i; ++j) A.num[i][j]++;
    f.num[1][1] = m;
    f = f * (A ^ (n - 1));
    int ans = 0;
    for(int i = 1; i < m; ++i) ans = add(ans + f.num[1][i]);
    write(ans), puts("");
    return 0;
}

# C. 棋盘

完全不会，咕咕。

更新于 阅读次数 次