Codeforces Global Round 21

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
G(线性规划,对偶,DP,矩阵乘法,segtree)H(TODO)

G

给一个长n数列

q个操作或询问

  1. 操作修改 a[i] = v
  2. 询问[l,r] 区间上, 最小处理代价(不真实的修改区间)

f(l,r) = 每次可以对 相邻元素,分别 (-xt,-yt) 或(-yt,-xt) 代价为t

问最小代价和让 a[l..r] 全部小于等于0

范围

n 2e5

q 2e5

x,y [1,1e6]

ai, v [1,1e6]

6s

1024MB

题解

我的思路

因为对称,不妨设 ( x < y)

开始没看到相邻以为任意,那么不就是维护区间和与区间最大值 = max(和/(x+y),最大值/y)

但是要相邻这样肯定不对了, 比如样例1, 不相邻可以3,相邻最少要3.5

单次询问怎么做?

题解

线性规划对偶

https://pic1.zhimg.com/80/v2-b780de4a3bd814944026ad22f51518f8_720w.jpg

$max \sum c_j x_j$

限制

$a_{ij} x_{j} \le b_i$

$x_j \ge 0$

$i=1\cdots m,j=1\cdots n$

它的对偶问题

$min \sum b_i y_i$

限制

$a_{ij} y_{i} \ge c_i$

$y_i \ge 0$

$i=1\cdots m,j=1\cdots n$

我看了很多直觉的举例,反而没有理解,通过公式倒是理解了大流程, 下面youtube链接 感觉很清晰

小写字母表示列向量,大写字母表示矩阵

$max (c^Tx)$

$Ax \le b$

$x \ge 0$

对于任意$y \ge 0$满足

$c^Tx \le y^TAx$

有 $c^Tx \le y^TAx \le y^Tb$, 所以所有都满足,那么它的最大 = 右边的最小

所以对于所有$c^T \le y^TA$, $max(c^Tx) = min(y^Tb)$

$c^T \le y^TA$ 即是$Ay \ge c$

更一般的转化

  1. min max 对换

  2. 列个数x 变成行个数y

  3. 右侧约束 和 表达式系数 兑换

  4. 偏序关系

同偏序: max 变量(xi) 与 0关系 和 min 约束(不等式组xi) 左与右 关系

反偏序: min 变量(xi) 与 0关系 和 max 约束(不等式组xi) 左与右 关系

约束等于 对应 变量无约束

回到题目

线性规划 问题

原数组A

最小化 $\sum_{1\le i < n} a_i+b_i $

限制

$Xa_1+Yb_1\ge A_1$

$Xa_i+Yb_i+Ya_{i-1}+Xb_{i-1}\ge A_i (2\le i < n) $

$Ya_{n-1}+Xb_{n-1}\ge A_n $

$a_i,b_i\ge 0$

那么对偶

最大化 $\sum_{1\le i \le n} A_iz_i $

限制

$xz_i + yz_{i+1} \le 1 (1 \le z < n)$

$yz_i + xz_{i+1} \le 1 (1 \le z < n)$

$z_i \ge 0$

很好的把上面要求的所有系数1变成了右侧的限制

所以$z_i$ 可能取值$0,\frac{1}{y},\frac{1}{x+y}$

如果只有两个, 线性规划很明显 https://www.wolframalpha.com/input?i=2x%2B3y+%3C%3D+1%2C+2y%2B3x+%3C%3D+1

去画3个的3d情况,你会发现,和2d一样虽然有些棱,但如果这个棱上最优,那么棱上的顶点也最优,但这些凸点的坐标都是这三个可能值中

然后就可以dp了

dp[i][0/1/2], 即是算 $max \sum_{j \le i} A_jz_j$

代码

jiangly 的, 他整个G只花了15min??????

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

#define SEG_ROOT 1,0,n
#define mid (l+r)/2
#define SEG_L 2*p
#define SEG_R 2*p+1
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid,r

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;

int a[200010];

template<class Info,
  class Merge = plus<Info> // 合并方法
  >
  struct SegmentTree {
    const int n;
    const Merge merge;
    vector<Info> info;
    SegmentTree(int n) : n(n), merge(Merge()), info(4*n) {}
    SegmentTree(vector<Info> init) : SegmentTree(init.size()) {
      function<void(int, int, int)> build = [&](int p, int l, int r) { // [l,r) 左闭右开
        if (r - l == 1) { // 线段树叶子节点
          info[p] = init[l];
          return;
        }
        build(SEG_L_CHILD);
        build(SEG_R_CHILD);
        pull(p);
      };
      build(SEG_ROOT);
    }
    void pull(int p) {
      info[p] = merge(info[SEG_L], info[SEG_R]);
    }
    void modify(int p, int l, int r, int x, const Info &v) {
      if (r - l == 1) {
        info[p] = v;
        return;
      }
      if (x < mid) {
        modify(SEG_L_CHILD, x, v);
      } else {
        modify(SEG_R_CHILD, x, v);
      }
      pull(p);
    }
    void modify(int p, const Info &v) {
      modify(SEG_ROOT, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
      if (l >= y || r <= x) return Info(); // 直接省去范围判断, 超过范围提前 返回可参与计算的空状态
      if (l >= x && r <= y) return info[p];
      return merge(rangeQuery(SEG_L_CHILD, x, y), rangeQuery(SEG_R_CHILD, x, y));
    }
    Info rangeQuery(int l, int r) {
      return rangeQuery(SEG_ROOT, l, r);
    }
  };

int x, y;

// 0: 0
// 1: 1/(x+y)
// 2: 1/y
// 线段树每个节点
struct Info {
  double f[3][3];
  Info(ll v = 0) {
    rep(i,0,3){
      rep(j,0,3){
        if (i + j > 2) {
          f[i][j] = -1E18; // 不合法
        } else { // 这里直接 值 * z_i(0,1/(x+y),1/y), 因为转移方程里始终要乘 值
          f[i][j] = (j == 0 ? 0.0 : 1.0 * v / (j == 1 ? x + y : y));
        }
      }
    }
  }
};

// 实现合并方法
Info operator+(const Info &a, const Info &b) {
  Info c;
  rep(i,0,3){
    rep(j,0,3){
      c.f[i][j] = -1E18; // 不合法
      rep(k,0,3){
        // max 矩阵乘法
        c.f[i][j] = max(c.f[i][j], a.f[i][k] + b.f[k][j]);
      }
    }
  }
  return c;
}

int main() {
  int n = read();
  int q = read();

  x = read();
  y = read();
  if (x > y) swap(x, y); // 保证 x<=y

  vector<int> b(n);
  rep(i,0,n) b[i] = read();

  SegmentTree seg(vector<Info>(b.begin(), b.end())); // v => Info(v) => segtree(vector<info()>)

  while(q--) {
    int t = read();
    if (t == 1) {
      int k = read() - 1;
      int v = read();
      seg.modify(k, v);
    } else {
      int l = read() - 1;
      int r = read();
      auto info = seg.rangeQuery(l, r) + Info(); // + Info() 整合最大值,否则需要手动for 去取max
      printf("%.15lf\n",info.f[0][0]);
    }
  }

  return 0;
}

H

https://codeforces.com/contest/1696/problem/H

给一个正整数k

大小为n,元素可重复的集合A

f(集合S) = S中恰好选出k个元素能得到的最大乘积

求 A所有元素个数不小于k的子集B,的f(B)的和

mod 1e9+7

范围

n 600

ai [-1e9,1e9

1.5s

512 MB

题解

我的思路

如果全非负, 则最大k个的乘积

如果全负

k为偶数, 则最小k个的乘积

k为奇数, 则最大k个的乘积

如果有负有非负

k为偶数, 则负 和 非负 分两组, 每组按照绝对值 从大到小,两两成对 构成新的乘积, 一对一对选

如果k 为奇数, 取一个最大非负, 剩下的 和偶数方案一样处理

所以肯定要对原来的集合拍个序

但贡献怎么统计没有思路

题解

选k个指定它们最大? 计算会出现在多少个集合中??

总结

G

低分题做多了, 太久没遇到线性规划了,很久以前学过, 但好像也是系数多限制多变量少的,

然后这个对偶学了一下, 希望下次能有用到的地方???

最后转化可以描述为矩阵max乘法,可以用segtree维护

参考

官方

https://sites.math.washington.edu/~burke/crs/407/notes/section3.pdf

https://www.youtube.com/watch?v=yU8updOR87c

https://blog.csdn.net/qq_43539633/article/details/109150749