前言

之前打完网络赛，麻了，停更了一会…

正在顺便考虑重新组队…前队友准备弃暗（ACM）投明（Offer）了…

然后29号和30号肝了个新生赛题目（原题大赛），不过好像有点难了…

随缘了…明天开学，今天最后更完这十场。

复盘

B - Boxes

刚看的时候，以为是期望$DP$​，仔细推了一下，发现貌似并不需要写比较复杂的$DP$。

因为在取到某一个盒子时，是否需要再取的概率是可以轻易计算出来的（由题意，剩下部分同色则停止，则概率为$P=1-2 * (\frac{1}{2})^k$​）。

接着，题目要求代价最小，只需要排个序就可以了，因为代价大小和颜色这些变量是独立的。

对于花费代价获得提示的情况，可以设$dp[i]$​​的意义是已经打开了$i$​​​个箱子时就结束，所需的最小数学期望是多少。然后我们逆序从结束的情况（是否需要打开第$n-1$​​​​个箱子）到只打开一个箱子时（只有初始完全同色才一个箱子都不需要打开），按照$P[i] \times C[i]$的方式推导即可。

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
/ *  vegetable1024 | liushan.site | Maybe Lovely?  * /

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
    std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
    std::cout << head << ", ";
    Print(rail...);
}

int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x  *  10 + ch - '0', ch = getchar();
    return x;
}
int n;
double C, sans, w[maxn], dp[maxn];
signed main(void)
{
    scanf("%lld %lf", &n, &C);
    for(int i = 1; i <= n; i++)    
        scanf("%lf", &w[i]), sans += w[i];
    
    sort(w + 1, w + n + 1);

    for(int i = n - 1; i >= 0; i--)
        dp[i] = w[i]  *  (1 - pow(0.5, n - i)) + dp[i + 1];

    printf("%.10lf\n", min(sans, dp[0] + C));
    return 0;
}

D - Double Strings

首先这个题面看起来非常的劝退。

image-20210903005443369

仔细读一下后，发现大概是要做这几件事：

  • 在$A=(1,2,\dots,|A|)$和$B=(1,2,\dots,|B|)$中分别选取一个子序列$a,b$
  • 子序列$a,b$的长度要相等，即$|a|=|b|$
  • 在子序列$a$​中存在一个位置$pos$​，其$A_{a_{pos} } < B_{b_{pos} }$
  • 对于$1,2,\dots,pos-1$这些位置，均有$A_{a_{i} } == B_{b_{i} }$

人话：

在$A$​中选一个长度为$len$​的子序列，$B$​中选一个长度为$len$​的子序列，要保证前$k-1$​位相等，第$k$​位满足$A_k<B_k$​，其余位置随意，求选取方案数$mod \ 10^9+7$​​的结果。

观察数据范围，猜测复杂度大概是$O(n^2)$​的。

然后开始分拆问题。

对于 相等 的情况，我们可以设$dp[i][j]$​​是在字符串$A$​​中$[1, i]$​​中选择，在字符串$B$​​中$[1,j]$​​中选择的 公共子序列 相等的 方案数 。

这貌似是一个很经典的$DP$（

  • 如果$A[i]$和$B[j]$不相等，$dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]$​
  • 如果$A[i]$和$B[j]$相等，$dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1] + dp[i - 1][j - 1] + 1$
  • 其中，$+ dp[i - 1][j - 1] + 1$代表$A[i]$和$B[j]$自己组成一个子序列的方案数，以及与$[1, i-1]$和$[1, j-1]$中的公共子序列相接得到的子序列的方案数。

而后，我们需要比较$A[i+1]$​和$B[j+1]$​是否满足$A[i + 1] < B[j+1]$​。

最后，我们需要得到，在字符串$A$的后半部分$[i+2,A_{len}]$和字符串$B$的后半部分$[j+2, B_{len}]$中，有多少种不同的选择方案，使得最后得到的子序列$a,b$长度相等。

在前面两个情况中，我们得到的子序列$a,b$的长度都是相同的。也就是说，对于最后一种情况，我们要枚举长度为$1,2,3,\dots$的选择方案。

更准确的，设完成了前两种情况的选择后，字符串$A$​​的后半部分长度为$len1$​​，字符串$B$​​的后半部分长度为$len2$​​​，我们需要求出：

我们可以等价一下，由组合数定义​，上面的式子可以转化为：

​​

此时，问题其实等价于：在一个有$len1+len2$​​​​​​个球的盒子中取出$min ( len1, len2 ) $​​​​​​个球的方案数的和。

式子的意义转为：

  • $C_{len1}^0 * C_{len2} ^ { min(len1, len2) } \rightarrow $​​​​​ 在取出的$ min(len1,len2) $​​​​个球中，有$0$​​​​个球在前$len1$​​​​个球中被取出，有$min( len1, len2 )$​​​​个球在后$len2$​​​​个球中被取出。
  • $C_{len1}^1 * C_{len2} ^ { min ( len1, len2 ) - 1}\rightarrow$​​​​ 在取出的$min(len1,len2)$​​​​个球中，有$1$​​​​​个球在前$len1$​​​​​个球中被取出，有$min{ (len1,len2) - 1}$​​​​​个球在后$len2$​​​​个球中被取出。
  • …

由此即可推导得到：

​​

由于$len1+len2 \leq 10^4$，因此使用杨辉三角递推会导致空间过大。我们考虑通过递推阶乘逆元来计算组合数。

到此这道题就解决了。

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
/ *  vegetable1024 | liushan.site | Maybe Lovely?  * /

#include <bits/stdc++.h>
#define maxn 5005
#define int long long
using namespace std;

const int mod = 1e9 + 7;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
    std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
    std::cout << head << ", ";
    Print(rail...);
}

int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x  *  10 + ch - '0', ch = getchar();
    return x;
}

string str1, str2;
int len1, len2, fac[maxn + maxn], inv[maxn + maxn], dp[maxn][maxn];
int qpow(int a, int b, int p){
    if(b == 0)    return 1;
    int tmp = qpow(a, b / 2, p);
    tmp = (tmp  *  tmp) % p;
    if(b & 1)    tmp = (tmp  *  a) % p;
    return tmp;
}
void init_inv(int lim){
    fac[0] = 1;
    for(int i = 1; i <= lim; i++)    fac[i] = (fac[i - 1]  *  i) % mod;
    inv[lim] = qpow(fac[lim], mod - 2, mod);
    for(int i = lim - 1; i >= 1; i--)    inv[i] = (inv[i + 1]  *  (i + 1)) % mod;
}
int Calc_C(int n, int m){
    if(n == m || m == 0)    return 1;
    return (((fac[n]  *  inv[m]) % mod)  *  inv[n - m]) % mod;
}
signed main(void)
{
    init_inv(10000);
    cin >> str1 >> str2;
    str1 = "#" + str1; 
    str2 = "#" + str2;
    len1 = str1.length();
    len2 = str2.length();
    for(int i = 1; i < len1; i++)
        for(int j = 1; j < len2; j++)
        {
            if(str1[i] == str2[j])
                dp[i][j] = (1LL  *  dp[i - 1][j] + dp[i][j - 1] + 1) % mod;
            else
                dp[i][j] = (((1LL  *  dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % mod) + mod) % mod;
        }
    int ans = 0;
    for(int i = 1; i < len1; i++)
        for(int j = 1; j < len2; j++)
        {
            if(str1[i] < str2[j])
            {
                int r1 = len1 - i - 1;
                int r2 = len2 - j - 1;
                ans = (1LL  *  ans + ((1LL  *  dp[i - 1][j - 1] + 1)  *  1LL  *  Calc_C(r1 + r2, r1)) % mod) % mod;
            }
        }
    printf("%lld\n", ans);
    return 0;
}

H - Holding Two

构造题，第一次读题读错了送了一发，第二次就好了。

题意是构造一个矩阵，使得在某一方向上（横，竖，斜），不能有连续三个元素是相同的。

只需要：

1
2
3
4
5
0011001100110011
1100110011001100
0011001100110011
1100110011001100
...

这样构造即可。

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
/ *  vegetable1024 | liushan.site | Maybe Lovely?  * /

#include <bits/stdc++.h>
#define maxn 1005
#define int long long
using namespace std;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
    std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
    std::cout << head << ", ";
    Print(rail...);
}

int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x  *  10 + ch - '0', ch = getchar();
    return x;
}
int n, m, board[maxn][maxn];
signed main(void)
{
    n = read();
    m = read();
    for(int i = 1; i <= n; i++)
    {
        int flag = i & 1;
        for(int j = 1; j <= m; j += 2)
        {
            board[i][j] = board[i][j + 1] = flag;
            flag ^= 1;
        }
        
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            printf(j == m ? "%d\n" : "%d", board[i][j]);
    return 0;
}

J - Jewels

$KM$模板题，最开始时候想过反悔贪心，但是好像搞不出来（

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/ *  vegetable1024 | liushan.site | Maybe Lovely?  * /

#include <bits/stdc++.h>
#define maxn 305
#define int long long
using namespace std;

//DEBUG TEMPLATE
template <typename T>
void Print(T value){
    std::cout << value << '\n';
}
template <typename Head, typename... Rail>
void Print(Head head, Rail... rail){
    std::cout << head << ", ";
    Print(rail...);
}

int read(){
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x  *  10 + ch - '0', ch = getchar();
    return x;
}

int n;
struct Node{
    int xi, yi, zi, vi, ti;
}P[maxn];

//INT范围内使用，使用longlong时记得改掉INF
//要根据所求是最大权匹配还是最小权匹配修改init中G[i][j]的初始化。
struct KM{
    const int inf = 1LL << 60;
    int G[maxn][maxn], hl[maxn], hr[maxn], dt[maxn];
    int fl[maxn], fr[maxn], vl[maxn], vr[maxn], pre[maxn], q[maxn], ql, qr, n;
    void init(int nl, int nr){
        n = max(nl, nr);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                G[i][j] = -inf;
    }
    void add(int u, int v, int w){
        G[u][v] = max(G[u][v], w);
    }
    int check(int i){
        if (vl[i] = 1, fl[i] != -1)
            return vr[q[qr++] = fl[i]] = 1;
        while (i != -1)
            swap(i, fr[fl[i] = pre[i]]);
        return 0;
    }
    void bfs(int s){
        for (int i = 1; i <= n; ++i)
            vl[i] = vr[i] = 0, dt[i] = inf;
        for (vr[q[ql = 0] = s] = qr = 1;;)
        {
            for (int d; ql < qr;)
            {
                for (int i = 1, j = q[ql++]; i <= n; ++i)
                    if (!vl[i] && dt[i] >= (d = hl[i] + hr[j] - G[i][j]))
                    {
                        if (pre[i] = j, d)
                            dt[i] = d;
                        else if (!check(i))
                            return;
                    }
            }
            int d = inf;
            for (int i = 1; i <= n; ++i)
                if (!vl[i] && d > dt[i])    d = dt[i];
            for (int i = 1; i <= n; ++i)
            {
                if (vl[i])    hl[i] += d;
                else          dt[i] -= d;
                
                if (vr[i])    hr[i] -= d;
            }
            for (int i = 1; i <= n; ++i)
                if (!vl[i] && !dt[i] && !check(i))    return;
        }
    }
    int solve(){
        for (int i = 1; i <= n; ++i)
            fl[i] = fr[i] = -1, hr[i] = 0;
        for (int i = 1; i <= n; ++i)
            hl[i] =  * max_element(G[i] + 1, G[i] + 1 + n);
        for (int i = 1; i <= n; ++i)    bfs(i);
        int ret = 0;
        for (int i = 1; i <= n; ++i)
            if (G[i][fl[i]])
                ret += G[i][fl[i]];
            else
                fl[i] = 0;
        return ret;
    }
}km;
int calc(Node A){
    return A.xi  *  A.xi + A.yi  *  A.yi + (A.zi + A.ti  *  A.vi)  *  (A.zi + A.ti  *  A.vi);
}
signed main(void)
{
    n = read();
    for (int i = 1; i <= n; i++)
        P[i].xi = read(), P[i].yi = read(), P[i].zi = read(), P[i].vi = read();
    km.init(n, n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            P[j].ti = i - 1, km.add(i, j, -calc(P[j]));
    printf("%lld\n", -km.solve());
    return 0;
}

K - King of Range

单调队列+双指针。

最开始的时候想的是做一个$ST$表，枚举左端点，二分右端点，寻找最大值减去最小值满足题意的最大区间，然后再套一个主席树上去做区间第$k$大，统计有多少个答案。

撇开时间复杂度不说，这个做法本来也是有漏洞的。因为只需要区间内存在一对最大值减去最小值满足题意的数，其拓展得到的区间也是一定满足条件的。而区间第$k$大会漏掉一些情况无法统计。

错误代码：

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
/ *  vegetable1024 | liushan.site | Maybe Lovely?  * /

#include <bits/stdc++.h>
#define maxn 500005
#define int long long
using namespace std;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
    std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
    std::cout << head << ", ";
    Print(rail...);
}

struct RMQ{
    int fl;
    int mm[maxn];
    int ST[maxn][25];
    void init(int n, int b[], int flag){
        fl = flag; mm[0] = -1;
        for(int i = 1; i <= n; i++)
        {
            mm[i] = (i & (i - 1)) == 0 ? mm[i - 1] + 1 : mm[i - 1];
            ST[i][0] = b[i];
        }
        for(int j = 1; j <= mm[n]; j++)
            for(int i = 1; i + (1 << j) - 1 <= n; i++)
            {
                if(fl)
                    ST[i][j] = max(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
                else
                    ST[i][j] = min(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
            }
    }
    int query(int lf, int rt){
        int k = mm[rt - lf + 1];
        return fl ? max(ST[lf][k], ST[rt - (1 << k) + 1][k]) : min(ST[lf][k], ST[rt - (1 << k) + 1][k]);
    }
}maxx, minn;

struct TemplateTree{
    struct Node {
        int lson, rson;
        int cnt;
    } tree[maxn  *  20];
    int root[maxn], b[maxn], m, tot;
    int build(int l, int r) {
        int i = tot++;
        tree[i].cnt = 0;
        if (l != r) {
            int mid = l + r >> 1;
            tree[i].lson = build(l, mid);
            tree[i].rson = build(mid + 1, r);
        }
        return i;
    }
    int add(int pre, int l, int r, int index) {
        int i = tot++;
        tree[i] = tree[pre];
        tree[i].cnt++;
        if (l != r) 
        {
            int mid = l + r >> 1;
            if(index <= mid) 
                tree[i].lson = add(tree[pre].lson, l, mid, index);
            else 
                tree[i].rson = add(tree[pre].rson, mid + 1, r, index);
        }
        return i;
    }
    int sum(int i, int l, int r, int index) {
        if (r <= index) 
            return tree[i].cnt;
        int mid = l + r >> 1;
        int ans = sum(tree[i].lson, l, mid, index);
        if (index > mid) 
            ans += sum(tree[i].rson, mid + 1, r, index);
        //Print(ans);
        return ans;
    }
    int LRN_query(int l, int r, int x){
        //l++, r++;
        int index = upper_bound(b + 1, b + 1 + m, x) - b - 1;
        if (index < 1 || index > m)
            return 0;
        else
            return sum(root[r], 1, m, index) - sum(root[l - 1], 1, m, index);
    }
    void initTree(int n, int a[]){
        for (int i = 1; i <= n; i++)    b[i] = a[i];
        sort(b + 1, b + 1 + n);
        m = unique(b + 1, b + 1 + n) - b - 1;
        root[0] = build(1, m);
        for (int i = 1; i <= n; i++) {
            int index = lower_bound(b + 1, b + 1 + m, a[i]) - b;
            root[i] = add(root[i - 1], 1, m, index);
        }
    }
}tr;

int n, m, k, a[maxn];

int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x  *  10 + ch - '0', ch = getchar();
    return x;
}

bool check(int s, int pos, int val, int fl){
    return fl ? maxx.query(s, pos) == val : minn.query(s, pos) == val;
}

signed main(void)
{
    n = read(); m = read();
    for(int i = 1; i <= n; i++)    a[i] = read();

    tr.initTree(n, a);
    maxx.init(n, a, 1);
    minn.init(n, a, 0);
    
    for(int i = 1; i <= m; i++)
    {
        k = read();   
        int ans = 0;
        for(int s = 1; s <= n; s++)
        {
            int maxxans = -1, minnans = -1;
            int lf = s, rt = n;
            while(lf <= rt)
            {
                int mid = (lf + rt) / 2;
                check(s, mid, a[s], 1) ? maxxans = mid, lf = mid + 1 : rt = mid - 1;
            }
            if(s < maxxans)
                ans += tr.LRN_query(s + 1, maxxans, a[s] - k - 1);
            //Print("debug", s, maxxans, a[s] - k);
            //Print("ANS", s, maxxans, a[s] - k, tr.LRN_query(s, maxxans, a[s] - k));
            
            lf = s, rt = n;
            while(lf <= rt)
            {
                int mid = (lf + rt) / 2;
                check(s, mid, a[s], 0) ? minnans = mid, lf = mid + 1 : rt = mid - 1;
            }
            if(minnans == maxxans)    continue;
            
            if(s < minnans)
                ans += minnans - s - tr.LRN_query(s + 1, minnans, a[s] + k);
            
            //Print("ANS", s, minnans, a[s] + k + 1, tr.LRN_query(s, minnans, a[s] + k + 1), minnans - s + 1 - tr.LRN_query(s, minnans, a[s] + k + 1));
        }   
        printf("%lld\n", ans);
    }
    
    return 0;
}

而后我们考虑使用单调队列维护区间最值，双指针维护当前的区间。

  • 当最大值减去最小值满足题意时，当前区间对答案的贡献就是$n - r + 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
56
57
58
/ *  vegetable1024 | liushan.site | Maybe Lovely?  * /

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

//DEBUG TEMPLATE
template<typename T>
void Print(T value){
    std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
    std::cout << head << ", ";
    Print(rail...);
}

int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x  *  10 + ch - '0', ch = getchar();
    return x;
}
int n, m, k, a[maxn];
signed main(void)
{
    n = read(); m = read();
    for(int i = 1; i <= n; i++)    a[i] = read();
    for(int i = 1; i <= m; i++)
    {
        k = read();
        int ans = 0, l = 1, r = 0;
        deque<int> maxx, minn;
        while(l <= n && r <= n)
        {
            while(!maxx.empty() && maxx.front() < l)    maxx.pop_front();
            while(!minn.empty() && minn.front() < l)    minn.pop_front();
            if(!maxx.empty() && !minn.empty() && a[maxx.front()] - a[minn.front()] > k)
            {
                ans += n - r + 1;
                l++;
                continue;
            }
            else
            {
                r++;
                while(!maxx.empty() && a[maxx.back()] <= a[r])    maxx.pop_back();
                maxx.push_back(r);
                while(!minn.empty() && a[minn.back()] >= a[r])    minn.pop_back();
                minn.push_back(r);
                continue;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}