November 2022 Algorithm Solution

Replace Sort

题目链接：https://codeforces.com/gym/103438/problem/E

题目大意：给定两个数组 A 和 B，两个数组里面的每一个元素都不相同，可以做多次操作，每次操作可以选择 B 中的任意一个元素替换 A 中的任意一个元素，但是 B 中每个元素只能用一次，问让 A 变成有序的最小操作次数是多少或者报告这是不可能的

解题思路：

由于 B 的顺序不重要，因此可以先排序，按照官方题解，是定义两个数组 dpA[i]dpA[i] 表示 A 数组前 i 个数有序的最小成本，dpb[i][j]dpb[i][j] 表示 A 中前 i 个数有序且第 i 个数被 B[j]B[j] 替换的最小成本，可以把 dpA[i]dpA[i] 简化为 dpB[i][0]dpB[i][0]

以下是暴力代码

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
int n, m;
int a[N], b[N], f[N][N];  // a[i]被b[j]替换后且前i个有序的最小成本
void solve() {
    cin >> n >> m;
    lep(i, 1, n) cin >> a[i];
    lep(i, 1, m) cin >> b[i];
    sort(b + 1, b + 1 + m);
    memset(f, INF, sizeof(f));
    f[0][0] = 0;
    lep(i, 1, n) {
        if (a[i] > a[i - 1]) {  //不用换
            f[i][0] = min(f[i][0], f[i - 1][0]);
        }
        lep(j, 1, m) {  //找到所有可以替换 a[i-1] 的
            if (b[j] < a[i]) f[i][0] = min(f[i][0], f[i - 1][j]);
        }
        lep(j, 1, m) {
            if (j >
                1)  //假如a[i-1]已经被b[j-1]替换，那么用b[j]替换a[i]一定不会更劣
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
            if (b[j] > a[i - 1]) {  //找到所有可以替换 a[i] 的
                f[i][j] = min(f[i][j], f[i - 1][0] + 1);
            }
        }
    }
    int ans = f[n][0];
    lep(i, 0, m) ans = min(ans, f[n][i]);
    cout << (ans == INF ? -1 : ans) << endl;
}

只需要对上面的代码进行优化即可，注意到有求区间最小值和区间取min，至于 f[i][j]=min(f[i][j],f[i−1][j−1]+1)f[i][j]=min(f[i][j],f[i-1][j-1]+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
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
int n, m;
int st;
int a[500059], b[500050], f[500050];

struct data {
    int mx, mx2, mn, mn2, cmx, cmn, tmx, tmn, tad;
    int sum;
};
data t[4000050];

void pushup(int u) {
    const int lu = u << 1, ru = u << 1 | 1;
    t[u].sum = t[lu].sum + t[ru].sum;
    if (t[lu].mx == t[ru].mx) {
        t[u].mx = t[lu].mx, t[u].cmx = t[lu].cmx + t[ru].cmx;
        t[u].mx2 = max(t[lu].mx2, t[ru].mx2);
    } else if (t[lu].mx > t[ru].mx) {
        t[u].mx = t[lu].mx, t[u].cmx = t[lu].cmx;
        t[u].mx2 = max(t[lu].mx2, t[ru].mx);
    } else {
        t[u].mx = t[ru].mx, t[u].cmx = t[ru].cmx;
        t[u].mx2 = max(t[lu].mx, t[ru].mx2);
    }
    if (t[lu].mn == t[ru].mn) {
        t[u].mn = t[lu].mn, t[u].cmn = t[lu].cmn + t[ru].cmn;
        t[u].mn2 = min(t[lu].mn2, t[ru].mn2);
    } else if (t[lu].mn < t[ru].mn) {
        t[u].mn = t[lu].mn, t[u].cmn = t[lu].cmn;
        t[u].mn2 = min(t[lu].mn2, t[ru].mn);
    } else {
        t[u].mn = t[ru].mn, t[u].cmn = t[ru].cmn;
        t[u].mn2 = min(t[lu].mn, t[ru].mn2);
    }
}
void push_add(int u, int l, int r, int v) {
    t[u].sum += (r - l + 1ll) * v;
    t[u].mx += v, t[u].mn += v;
    if (t[u].mx2 != -INF) t[u].mx2 += v;
    if (t[u].mn2 != INF) t[u].mn2 += v;
    if (t[u].tmx != -INF) t[u].tmx += v;
    if (t[u].tmn != INF) t[u].tmn += v;
    t[u].tad += v;
}
void push_min(int u, int tg) {
    if (t[u].mx <= tg) return;
    t[u].sum += (tg * 1ll - t[u].mx) * t[u].cmx;
    if (t[u].mn2 == t[u].mx) t[u].mn2 = tg;
    if (t[u].mn == t[u].mx) t[u].mn = tg;
    if (t[u].tmx > tg) t[u].tmx = tg;
    t[u].mx = tg, t[u].tmn = tg;
}
void push_max(int u, int tg) {
    if (t[u].mn > tg) return;
    t[u].sum += (tg * 1ll - t[u].mn) * t[u].cmn;
    if (t[u].mx2 == t[u].mn) t[u].mx2 = tg;
    if (t[u].mx == t[u].mn) t[u].mx = tg;
    if (t[u].tmn < tg) t[u].tmn = tg;
    t[u].mn = tg, t[u].tmx = tg;
}
void pushdown(int u, int l, int r) {
    const int lu = u << 1, ru = u << 1 | 1, mid = (l + r) >> 1;
    if (t[u].tad)
        push_add(lu, l, mid, t[u].tad), push_add(ru, mid + 1, r, t[u].tad);
    if (t[u].tmx != -INF) push_max(lu, t[u].tmx), push_max(ru, t[u].tmx);
    if (t[u].tmn != INF) push_min(lu, t[u].tmn), push_min(ru, t[u].tmn);
    t[u].tad = 0, t[u].tmx = -INF, t[u].tmn = INF;
}
void build(int u, int l, int r) {
    t[u].tmn = INF, t[u].tmx = -INF;
    if (l == r) {
        t[u].sum = t[u].mx = t[u].mn = INF;
        t[u].mx2 = -INF, t[u].mn2 = INF;
        t[u].cmx = t[u].cmn = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void add(int L, int R, int v, int u, int l, int r) {
    if (R < l || r < L) return;
    if (L <= l && r <= R) return push_add(u, l, r, v); 
    int mid = (l + r) >> 1;
    pushdown(u, l, r);
    add(L, R, v, u << 1, l, mid), add(L, R, v, u << 1 | 1, mid + 1, r);
    pushup(u);
}
void tomin(int L, int R, int v, int u, int l, int r) {
    if (R < l || r < L || t[u].mx <= v) return;
    if (L <= l && r <= R && t[u].mx2 < v) return push_min(u, v);
    int mid = (l + r) >> 1;
    pushdown(u, l, r);
    tomin(L, R, v, u << 1, l, mid), tomin(L, R, v, u << 1 | 1, mid + 1, r);
    pushup(u);
}
void tomax(int L, int R, int v, int u, int l, int r) {
    if (R < l || r < L || t[u].mn >= v) return;
    if (L <= l && r <= R && t[u].mn2 > v) return push_max(u, v);
    int mid = (l + r) >> 1;
    pushdown(u, l, r);
    tomax(L, R, v, u << 1, l, mid), tomax(L, R, v, u << 1 | 1, mid + 1, r);
    pushup(u);
}
int qsum(int L, int R, int u, int l, int r) {
    if (R < l || r < L) return 0;
    if (L <= l && r <= R) return t[u].sum;
    int mid = (l + r) >> 1;
    pushdown(u, l, r);
    return qsum(L, R, u << 1, l, mid) + qsum(L, R, u << 1 | 1, mid + 1, r);
}
int qmax(int L, int R, int u, int l, int r) {
    if (R < l || r < L) return -INF;
    if (L <= l && r <= R) return t[u].mx;
    int mid = (l + r) >> 1;
    pushdown(u, l, r);
    return max(qmax(L, R, u << 1, l, mid), qmax(L, R, u << 1 | 1, mid + 1, r));
}
int qmin(int L, int R, int u, int l, int r) {
    if (R < l || r < L) return INF;
    if (L <= l && r <= R) return t[u].mn;
    int mid = (l + r) >> 1;
    pushdown(u, l, r);
    return min(qmin(L, R, u << 1, l, mid), qmin(L, R, u << 1 | 1, mid + 1, r));
}
void solve() {
    cin >> n >> m;
    lep(i, 1, n) cin >> a[i];
    lep(i, 1, m) cin >> b[i];
    sort(b + 1, b + 1 + m);
    a[++n] = INF;
    st = n + 1;
    build(1, 1, n + m + 1);
    tomin(st + 1, n + m + 1, 1, 1, 1, n + m + 1);
    lep(i, 1, n) {
        if (a[i] > a[i - 1])
            f[i] = f[i-1];
        else
            f[i] = INF;
        int id = lower_bound(b + 1, b + 1 + m, a[i]) - b - 1;
        f[i] = min(f[i], qmin(st + 1, st + id, 1, 1, n + m + 1));
        st--;
        add(st + 1, st + m, 1, 1, 1, n + m + 1);
        id = lower_bound(b + 1, b + 1 + m, a[i - 1]) - b - 1;
        tomin(st + id + 1, st + m, f[i - 1] + 1, 1, 1, n + m + 1);
    }
    cout << (f[n] < 1e9 ? f[n] : -1) << endl;
}

Job Allocator

题目链接：https://codeforces.com/gym/103185/problem/J

题目大意：维护一个容器，n 次操作，操作一，往容器中插入一台机器，告诉每台机器每种资源有多少个，操作二，给出一个任务，告诉完成该任务每种资源至少需要多少个，求容器中有多少台机器可以完成该任务，操作三，删除容器中第 x 台机器

资源种类 K 不超过 8 ，需要的资源总数也不超过 8

解题思路：先考虑 K=2 的情况，维护一个矩阵 f[x][y]f[x][y] ，表示第一种资源数大于等于 x 且第二种资源数大于等于 y 的机器有多少个，这样在回答查询操作时可以 O(1)O(1) 得到答案，增加一台机器 (a,b)(a,b)时，只需要把 0≤x≤a&& 0≤y≤b0 \le x\le a \&\&\ 0\le y\le b 的 f[x][y]f[x][y] 加一即可，删除同理，每次操作次数为 (x+1)∗(y+1)(x+1)*(y+1) ，由于 x+y≤8x+y\le 8 ，因此当 x=4 以及 y=4 时，最大值为(x+1)∗(y+1)=25(x+1)*(y+1)=25

K=8 时只需要开一个 8 维数组即可，操作次数最大为 282^8 ，因此时间复杂度为 O(n∗2k)O(n*2^{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
int n, k;
int f[9][9][9][9][9][9][9][9];
array<int, 9> a;
ordered_set t;
void add(array<int, 9> a, int v) {
    lep(i1, 0, a[1]) {
        lep(i2, 0, a[2]) {
            lep(i3, 0, a[3]) {
                lep(i4, 0, a[4]) {
                    lep(i5, 0, a[5]) {
                        lep(i6, 0, a[6]) {
                            lep(i7, 0, a[7]) {
                                lep(i8, 0, a[8]) {
                                    f[i1][i2][i3][i4][i5][i6][i7][i8] += v;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}
void solve() {
    cin >> n >> k;
    lep(i, 1, n) {
        int id, num, x;
        string s;
        cin >> s;
        if (s == "C") {
            cin >> num;
            lep(j, 1, num) {
                cin >> x;
                a[x]++;
            }
            t.insert({i, a});
            add(a, 1);
        } else if (s == "J") {
            cin >> num;
            lep(j, 1, num) {
                cin >> x;
                a[x]++;
            }
            cout<<f[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]]<<endl;
        } else {
            cin >> id;
            a = (*t.find_by_order(id - 1)).se;
            add(a, -1);
        }
        lep(j, 1, k) a[j] = 0;
    }
}

The Bakery

题目链接：https://codeforces.com/problemset/problem/833/B

题目大意：给定一个序列，你需要把序列分成 k(k≤min(50,n))k(k\le min(50,n)) 段，每一段的贡献为区间内不同数的个数，最大化总贡献

解题思路：DP+线段树优化。考虑 DP 方程：dp[k][i]=max1≤j≤i(dp[k−1][j]+c[j+1][i])dp[k][i]=max_{1\le j\le i}(dp[k-1][j]+c[j+1][i]) ，dp[k][i]dp[k][i] 表示前 i 个分成 k 段的最大贡献，c[i][j]c[i][j] 表示区间 [i,j][i,j] 的贡献，假设已经求到了 dp[k−1]dp[k-1] ，那么问题的关键就是求后缀 c[i][j]c[i][j] 的贡献，考虑一个数 a[i]a[i] ，设它上一次出现的位置是 last[a[i]]last[a[i]] ，那么序列 [last[a[i]]+1,i][last[a[i]]+1,i] 贡献加一，因此可以用线段树维护 dp[k−1][j]+c[j+1][i]dp[k-1][j]+c[j+1][i] 的最大值，然后区间加即可 ，算法流程如下：

1
2
3
4
5
6
for i in k:#遍历k段
    build()#用上一段dp重新建树
    for j in n:
        add(pos[a[j]]+1,j,1)#每个数的贡献
        dp[i][j]=get_max(1，j)#求出1-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
77
78
int n, k;
int a[N], last[N], dp[55][N], pos[N];
struct segment {
    int l;
    int r;
    int sum;
    int lazy_inc;
    int Max;
} tr[N << 2];
void increase(int rt, int v) {
    int l = tr[rt].l, r = tr[rt].r;
    tr[rt].sum += (r - l + 1) * v;
    tr[rt].Max += v;
    tr[rt].lazy_inc += v;
}
void pushdown(int rt) {
    if (tr[rt].lazy_inc) {
        increase(rt << 1, tr[rt].lazy_inc);
        increase(rt << 1 | 1, tr[rt].lazy_inc);
        tr[rt].lazy_inc = 0;
    }
}
void pushup(int n) {
    tr[n].Max = max(tr[n << 1].Max, tr[n << 1 | 1].Max);
    tr[n].sum = tr[n << 1].sum + tr[n << 1 | 1].sum;
}
void build(int rt, int l, int r, int id) {  //建树
    tr[rt].l = l;
    tr[rt].r = r;
    tr[rt].lazy_inc = 0;
    if (l == r) {
        tr[rt].Max = tr[rt].sum = dp[id][l - 1];
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid, id);
    build(rt << 1 | 1, mid + 1, r, id);
    pushup(rt);
}
void add(int rt, int l, int r, int v) {  //区间加
    if (l > tr[rt].r || tr[rt].l > r) return;
    if (l <= tr[rt].l && tr[rt].r <= r) {
        increase(rt, v);
        return;
    }
    pushdown(rt);
    add(rt << 1, l, r, v);
    add(rt << 1 | 1, l, r, v);
    pushup(rt);
}
int get_Max(int rt, int l, int r) {  //区间最大值
    if (l > tr[rt].r || tr[rt].l > r) return -INF;
    if (l <= tr[rt].l && tr[rt].r <= r) {
        return tr[rt].Max;
    }
    int max1 = -INF;
    pushdown(rt);
    max1 = max(max1, get_Max(rt << 1, l, r));
    max1 = max(max1, get_Max(rt << 1 | 1, l, r));
    pushup(rt);
    return max1;
}
void solve() {
    cin >> n >> k;
    lep(i, 1, n) {
        cin >> a[i];
        pos[i] = last[a[i]];
        last[a[i]] = i;
    }
    lep(i, 1, k) {
        build(1, 1, n, i - 1);
        lep(j, 1, n) {
            add(1, pos[j] + 1, j, 1);
            dp[i][j] = get_Max(1, 1, j);
        }
    }
    cout << dp[k][n] << endl;
}

Because, Art

题目链接：https://codeforces.com/gym/103640/problem/B

题目大意：给定两个数组 a 和 b ，从 a 和 b 两个数组各任意选 k 个数一一配对，和为 ∑i=0ka[i]∗b[i]\sum^{k}_{i=0} a[i]*b[i] ，求当 k=1,2,...,nk=1,2,...,n 时和的最大值和最小值

解题思路：先考虑求最大值，首先将两个数组排序，然后把同正同负的数按顺序配对，然后按大小排序，然后输出前 k 个之和即可，若 k 大于这样的数对数量，那么接下来就只能选择一正一负相乘了，此时剩余的两个数组，一个全为正数，一个全为负数，分别按照绝对值升序排，那么答案就是 ∑i=0ka[i]∗b[k−i]\sum^{k}_{i=0} a[i]*b[k-i] ，可以用 FFT 计算答案，求最小值只需要将一个数组全部取反，然后重复上述步骤

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
const double PI = acos(-1.0);
struct Complex {
    double x, y;  //复数，x代表实部，y代表虚部。
    Complex(double _x = 0, double _y = 0) { x = _x, y = _y; }
} a[N], b[N];  //多项式a和b，相乘。
int l, r[N],
    limit =
        1;  // n为a的次数,m为b的次数。limit即为最大限制。2^n次方，而l为二进制的位数
//运算符重载。
Complex operator+(Complex a, Complex b) {
    return Complex(a.x + b.x, a.y + b.y);
}
Complex operator-(Complex a, Complex b) {
    return Complex(a.x - b.x, a.y - b.y);
}
//复数相乘，则模长相乘，幅度相加。
Complex operator*(Complex a, Complex b) {
    return Complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
void fft(Complex* A, int type) {
    for (int i = 0; i < limit; ++i) {
        if (i < r[i]) swap(A[i], A[r[i]]);
        //求出要迭代的区间。小于r[i]时才交换，防止同一个元素交换两次，回到原来的位置。
    }
    //从底层往上合并。
    for (int mid = 1; mid < limit; mid <<= 1) {
        //待合并区间长度的一半，最开始是两个长度为1的序列合并,mid = 1;
        Complex Wn(cos(PI / mid), type * sin(PI / mid));  //单位根。
        for (int len = mid << 1, j = 0; j < limit; j += len) {
            // len是区间的长度，j是当前的位置，也就是合并到了哪一位。
            Complex w(1, 0);  //幂，一直乘，得到平方，三次方。
            for (int k = 0; k < mid; ++k, w = w * Wn) {
                //枚举左半部分。蝴蝶变换得到右半部分的答案。w为wn * k
                Complex x = A[j + k],
                        y = w * A[j + mid + k];  //左半部分和右半部分。
                A[j + k] = x + y;                //左边加。
                A[j + mid + k] = x - y;          //右边减。
            }
        }
    }
    if (type == 1) return;
    for (int i = 0; i <= limit; ++i) {
        a[i].x /= limit;
        //最后需要除以limit也就是补成了2的整数幂。将点值转换为系数。
    }
}
ll n;
ll x[N], y[N], ans1[N], ans2[N];
void work(ll* ans) {
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    sort(x + 1, x + 1 + n);
    sort(y + 1, y + 1 + n);
    vector<ll> c, d, e;
    lep(i, 1, n) {
        if (x[i] * y[i] >= 0)
            c.emplace_back(x[i] * y[i]);
        else {
            d.emplace_back(x[i]);
            e.emplace_back(y[i]);
        }
    }
    sort(c.begin(), c.end(), greater<ll>());
    int id = 1;
    for (auto i : c) {
        ans[id] = i + ans[id - 1];
        id++;
    }
    if (d.empty()) return;
    if (d[0] < 0) {
        sort(d.begin(), d.end(), greater<ll>());
        sort(e.begin(), e.end());
    } else {
        sort(d.begin(), d.end());
        sort(e.begin(), e.end(), greater<ll>());
    }
    int len = d.size() - 1;
    for (int i = 0; i <= len; ++i) {
        a[i].x = d[i] * 1.0;
    }
    for (int i = 0; i <= len; ++i) {
        b[i].x = e[i] * 1.0;
    }
    while (limit <= 2 * len) limit <<= 1, l++;
    //初始化r数组。
    for (int i = 0; i < limit; ++i)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    fft(a, 1);  //将a的系数转化为点值表示，
    fft(b, 1);  //将b的系数转化为点值表示。
    for (int i = 0; i <= limit; ++i) {
        //对应项相乘，得到点值表示的解。
        a[i] = a[i] * b[i];
    }
    fft(a, -1);
    int k = id - 1;
    for (int i = 0; i <= 2 * len; ++i) {
        //取出来除2，加上0.5四舍五入。
        ans[id] = ans[k] + (int)(a[i].x - 0.5);
        id++;
        if (id > n) return;
    }
}
void solve() {
    cin >> n;
    lep(i, 1, n) cin >> x[i];
    lep(i, 1, n) cin >> y[i];
    work(ans1);
    lep(i, 1, n) y[i] = -y[i];
    work(ans2);
    lep(i, 1, n) debug(-ans2[i], ans1[i]);
}