YeXiaoRain Blog(hexo的搜索高亮会破坏latex)

發表於 更新於 分類於 ， Disqus： 文章字數： 2k 所需閱讀時間 ≈ 7 分鐘
G(计算几何,排序,自定义排序)H(FWHT,FWT,meet-in-middle,bitmask)

G - Isosceles Trapezium

二维平面, N个点,坐标Xi,Yi, 权重Ci

选4个点, 形成 等腰梯形, 问选的4个点最大权重和

限制

N 1000

Xi,Yi [-1e9,1e9]

Ci [1,1e9]

无重点

3s

1024

我的思路

有点计算几何

N的样子,像是N^2的做法

如果是暴力找三个点, 确定平行边,那么剩下一个点就自然确定了, 这样的话是 N^3 log(N)

换个想法, 按对称轴来找

如果是垂于对称轴的一点,则找对称轴最远的两个点

这样 N^2 的对称轴, 其中相等的里面 按照垂点相同的最大的,找不同的两组就行了??

代码

https://atcoder.jp/contests/abc220/submissions/33799130

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

typedef long long ll;
#define MOD 1000000007
#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

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

ll gcd(ll a,ll b){
  a = abs(a);
  b = abs(b);
  while(b!= 0) tie(a,b) = make_pair(b,a%b);
  return a;
}
const ll INF = 0x3f3f3f3f3f3f3f3f;
array<ll,3> xyv[1010];
map<tuple<ll,ll,ll>, vector<pair<int,int> > > cx;

void addp(int i,int j){
  auto [x0,y0,v0] = xyv[i];
  auto [x1,y1,v1] = xyv[j];
  // 对称轴, 标准化
  ll ky = 2*(y1-y0);
  ll kx = -2*(x1-x0);
  ll k  = (x1-x0)*(x1+x0) + (y1-y0)*(y1+y0);
  ll g = gcd(k,gcd(ky,kx));
  ky /= g;
  kx /= g;
  k  /= g;
  if(ky < 0){
    ky = -ky;
    kx = -kx;
    k  = -k;
  }else if(ky == 0 && kx < 0){
    kx = -kx;
    k  = -k;
  }
  cx[{ky,kx,k}].push_back({i,j});
}

int main(){
  int n = read();
  rep(i,0,n){
    int x = read();
    int y = read();
    int v = read();
    xyv[i] = {x,y,v};
  }
  rep(i,0,n) rep(j,i+1,n) addp(i,j);
  ll ans = -1;
  for(auto [_,vec]:cx){
    auto center = [=](const pair<int,int>&ij){
        auto [i0,j0] = ij;
        auto [x0,y0,v0] = xyv[i0];
        auto [x1,y1,v1] = xyv[j0];
        return make_pair(x0+x1,y0+y1);
    };
    sort(vec.begin(),vec.end(), [=](const auto &ij0,const auto &ij1){
        return center(ij0) < center(ij1);
    });
    ll lastmax = -INF;
    ll cur = -INF;
    rep(i,0,vec.size()){
      if(i == 0 || center(vec[i]) != center(vec[i-1])){
        lastmax = max(lastmax,cur);
        cur = 0;
      }
      auto [i0,j0] = vec[i];
      cur = max(cur, xyv[i0][2] + xyv[j0][2]);
      if(lastmax != -INF){
        ans = max(ans, lastmax + cur);
      }
    }
  }
  printf("%lld\n",ans);
  return 0;
}
// y = -(x1-x0)/(y1-y0) (x - (x0+x1)/2) + (y0+y1)/2
// 2(y1-y0) y = -2(x1-x0) x + (x1-x0)(x1+x0) + (y0+y1)(y1-y0)

H - Security Camera

N 点, M 边

选定一些点, 让边(至少一个点上有被选定的)的数量是偶数个

求合法方案数

限制

N 40

无重边,自环

2s

1024mb

我的思路

感觉题面就是个朴素的图论

40 呢, 对应边就是780

估计是个边平方~ 3次方 左右的算法, 或者点的5次方?

思路正向就是考虑局部可行方案加上插头状态

逆向就是 所有减去存在未选择的 做容斥

点数量40, 2^40 = 1099511627776

如果, 是一个一个安装的, 那么考虑对于个数的影响

增量是 相邻未安装的和

而对于这个连接出的点,相邻未安装的奇偶性发生颠倒

题解

2^20 = 1048576

折半

把拆成两个点集合S,T

L1[S,s] = 点集S的子集s 被选了, 覆盖的边数的奇偶性

L2[S,T,s] = 点集T中, 连向S\s的数量是奇数的点集? (因为偶数的话,首先不被s选,其次不论在T中是否被选不影响奇偶性

R[T,t] = 点集T的子集t被选了,覆盖的两端属于T的边的奇偶性

因为对于每个选中状态, 可以枚举剩下所有点, 所以 可以$O(|S|2^{|S|})$ 暴力算完

那么对于答案有贡献的

$L_1[s] \oplus ((\text{popcount} (L_2[s] & t) ) &1) \oplus R[t] = 0$

意义 s得到的奇数偶,t内部奇偶,和t向S\s的奇偶 = 最终奇偶

中间这玩意怪怪的,虽然很长意义也就是L2[s] & t 的1的个数的奇偶性

像个办法把右侧合并一下

$F[S,T,s] = \sum_{t \subset T} ((\text{popcount} (L_2[s] \& t) ) \& 1) \oplus R[t] $

注意到 求和部分,奇数贡献1, 偶数贡献0, 所以这里是对于给定s,在T的子集中, 让上述表达式贡献1的个数

那么贡献0的个数就是 $2^{|T|} - F[S,T,s]$

如果能求出来, 那么对于每个$s$, 有$L1[s]$ 的奇偶性, 直接加上对应贡献即可

问题变成是如何求出F[S,T,s]

这里记$t’ = L2[s]$, 这样一个s唯一对应一个t', 但t'可能有多个s 映射过来

记作$G[T,t’] = \sum_{t \subset T} ((\text{popcount} (t’ \& t) ) \&1) \oplus R[t] $

这样有个好处是,不再关心S和s, 只用管T中的即可

注意到 $FWHT$的变换公式是

$fwht[a]_ i = \sum_{(\text{popcount}(i \& j) \bmod 2 = 0}a_j - \sum_{(\text{popcount}(i\& j) \bmod 2 = 1}a_j$

对于给定 i

一个具体的j

左侧为0时, 原式子贡献是 R[j], 而fwht贡献是 a[j]

左侧为1时, 原式子贡献是 R[j]^1, 而fwht贡献是 -a[j]

如果让a[j] = R[j], 那么

左侧为0时, 原式子贡献是 0 , 而fwht贡献是 0

左侧为0时, 原式子贡献是 1 , 而fwht贡献是 1

左侧为1时, 原式子贡献是 0^1, 而fwht贡献是 -0

左侧为1时, 原式子贡献是 1^1, 而fwht贡献是 -1

左侧为0和为1各占一半, 总贡献会少掉$2^{|T|-1}$

加上即可?

另一个做法

所有边变成”有向”, 小点连出到大点

f[i][j][k] = 前i个点, 未覆盖的边的两端都在前i的边数为j(奇1/偶0), 一些未来不选的会影响未覆盖边的奇偶性的点的方案数

i+1选 f[i][j][k] 贡献 f[i+1][j][k高(i+2)位]

i+1不选 f[i][j][k] 贡献 f[i+1][j^(i+1是否在k中)][(k高(i+2)位) ^ (i+1 连出的边) ]

很神奇的是, 这样每个点对于每个上个状态最多分支出两个状态

那么前一半最多2^20个状态

而状态低i位都是0, 所以后面的一半也是最多2^20个状态

所以复杂度也是

n 2^{n/2}

从一定程度上也有meet-in-middle 的感觉,而没有了fwt的需要

代码

https://atcoder.jp/contests/abc220/submissions/33847519

1.7s 快超时了, 为什么有人6ms 啊

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

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

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

ll g[50]; // g[小点] = 大点的bit mask
// f[前i个点][两端均在前i个中的未覆盖的边的奇偶][mask中的点每不选一个奇偶性变化1]=方案数
unordered_map<ll,ll>f[50][2];
int main() {
  int n = read(); // 点
  int m = read(); // 边
  rep(i,0,m){
    int x = read() - 1;
    int y = read() - 1;
    if(x > y) swap(x,y);
    g[x] |= 1ll<<y; // 全是小 -> 大
  }
  f[0][0][0]=1; // 选 点0，所有点因为不选 未覆盖 的边都为0，为偶数。
  f[0][0][g[0]]++; // 不选 点0，0指向的点因为不选 未覆盖 的边+1.
  rep(i,0,n-1) rep(j,0,2) { // 枚举当前的未覆盖的边数的奇偶。
    for(auto [mask,cnt]:f[i][j]) { // 枚举上一层的所有状态，进行推磨式转移。
      ll bit = (mask >> (i+1)) & 1;// 确定 不选点i+1 未覆盖的边的 奇偶变化。
      //选 点i+1，所有点(i+1之后的点) 因为不选而未覆盖的边数的就不变。且j的状态不变。
      f[i+1][j][mask^(bit<<(i+1))]+=cnt;
      //不选 点i+1，j的状态 根据当前j 和 因为i不选要未覆盖的边数的就确定
      //并且改变之后的点因为不选而未覆盖的边的奇偶
      f[i+1][j^bit][mask^(bit<<(i+1))^g[i+1]] += cnt;
    }
  }
  ll ans=0;
  for(auto [_,cnt]:f[n-1][m&1]) ans += cnt; // m&1 未覆盖的奇偶和总边一样,则覆盖了的为偶数
  printf("%lld",ans);
  return 0;
}

总结

G

没啥难的

简单的计算几何,排序,自定义排序

H

一个是40的一半是20, 2^20 是可以范围内的

另一个是拆的时候,可以按点拆分,一半是有点就包含,另一半是需要两端都属于集合

参考

官方题解

csdn 逆天峰 H

發表於 更新於 分類於 ， Disqus： 文章字數： 2.4k 所需閱讀時間 ≈ 8 分鐘
F(排序,分组)G(根号分类,分类)H(区间DP,问题转化)

F - Cleaning Robot

https://atcoder.jp/contests/abc219/tasks/abc219_f

给序列 从点(0,0) 出发,上下左右走n个点,

重复序列k次, 问经过次数>=1的点有几个

限制

n 2e5

k 1e12

2s

1024mb

我的思路

可以看成 一个图形, 每次平移固定向量, k次,问覆盖的图形面积

似乎脑补可得: 每次计算增量, 如果增量不变, 则往后都是这个增量

但不知道如何判断 达到了最小增量

如果是这个形状, s -> e

1
2
3
4
5
xxx
x
x
e
sxx

那么下一次增量是5, 下下次增量也是5, 但是 这不是最小增量, 最小是3

所以可能要变成去计算每个点首次不产生贡献的时刻, 而不产生贡献,也就是沿着 e -> s 的向量方向如果存在点

所以考虑对点归类, 能够通过向量 e -> s 到达的 归类

然后比较时刻和所有点的首次不产生贡献的时间即可

不产生时刻 = 同类别最近的方向向量 / 向量

好像就过了

代码

https://atcoder.jp/contests/abc219/submissions/33772772

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
#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

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

char s[200010];
int ch[256];

int di[] = {-1,1,0,0};
int dj[] = {0,0,-1,1};

vector<pair<pair<ll,ll>,ll> > pos;

int main(){
  ch[(int)'L'] = 0;
  ch[(int)'R'] = 1;
  ch[(int)'U'] = 2;
  ch[(int)'D'] = 3;
  scanf("%s",s);
  int n = strlen(s);
  ll k = read();

  ll dx = 0;
  ll dy = 0;
  vector<pair<ll,ll> > vis = {{dx,dy}};
  rep(i,0,n){
    dx += di[ch[(int)s[i]]];
    dy += dj[ch[(int)s[i]]];
    vis.push_back({dx, dy});
  }
  if(dx < 0){ // 保证在 (-pi/2,pi/2]
    dx = -dx;
    dy = -dy;
  }else if(dx == 0 && dy < 0){ // <- bug dx == 0
    dy = -dy;
  }

  sort(vis.begin(),vis.end());
  rep(i,0,vis.size()) if(i == 0 || vis[i] != vis[i-1]){
    auto [x,y] = vis[i];
    ll t = 0;
    if(dx != 0){ // dx >= 0
      t = x/dx;
      x -= t * dx;
      y -= t * dy;
      if(x < 0){
        t --;
        x += dx;
        y += dy;
      }
    }else if(dy != 0){ // dx == 0, dy >= 0
      t = y/dy;
      y -= t * dy;
      if(y < 0){
        t --;
        y += dy;
      }
    }
    pos.push_back({ { x , y } , t}); // 没空格 hexo 炸了
  }
  sort(pos.begin(),pos.end());
  ll ans = 0;
  if(dx == 0 && dy == 0){
    ans = pos.size();
  }else{
    rep(i,0,pos.size()){
      if(i == 0 || pos[i].first != pos[i-1].first){
        ans += k;
      }else{
        ans += min(k, pos[i].second - pos[i-1].second);
      }
    }
  }
  printf("%lld\n",ans);
  return 0;
}

G - Propagation

https://atcoder.jp/contests/abc219/tasks/abc219_g

n个点,m跳边的图, 点i上写的i

q次操作

每次让点xi 上的值扩散给它的所有相邻节点

输出最终每个点上的值

范围

n 2e5

m 2e5

q 2e5

无重边 自环

2s

1024mb

我的思路

直接模拟? 如果出现2层菊花形状 每次一个外层染进来,中心扩散, 那么可能就是QN的量级

那么思路方向一个如何批量 或者 lazy的表示

另一个就是有没有可能倒着做

如果把做为修改中心的, 作为点, 按时间顺序和依赖关系 可以建立树(森林), 但不太知道怎么去建

题解

分度处理

对于度小于 $\sqrt{m}$, 直接修改周围的点, 而对于 $\ge \sqrt{m}$的度的点, 在点上标识

对于查询, 可以查询所有, 相当于边访问2次

而每次 处理前, 需要遍历一次周围度大于等于$\sqrt{m}$ 的

复杂度分析

修改就不用说了显然

而就每次获取最新状态时, 因为要遍历相邻的所有度$\sqrt{m}$

那么假设有$w$个, 那么即使边来自它们之间 $\frac{w \sqrt{m}}{2} leq m$, 即$w \leq {2\sqrt{m}}$, 说明也是$O(\sqrt{m})$ 级别的访问

中间复杂度$O(q\sqrt{m})$, 最后查询复杂度$O(n\sqrt{m})$

代码

https://atcoder.jp/contests/abc219/submissions/33773300

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
#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

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

vector<int>p2[200010];
vector<int>pl[200010]; // linked large
bool large[200010]; // is large
pair<int,int> distr[200010]; // [u] = {value, time}

int a[200010]; // value
int t[200010]; // time

int getV(int u){
  int val = a[u];
  int ti = t[u];
  for(auto v:pl[u]) if(distr[v].second > ti) tie(val,ti) = distr[v];
  return val;
}

int main(){
  int n = read();
  ll m = read();
  int q = read();
  rep(i,0,m){
    int u = read();
    int v = read();
    p2[u].pb(v);
    p2[v].pb(u);
  }
  iota(a+1,a+n+1,1);
  rep(i,1,n+1) large[i] = (ll)p2[i].size() * (ll)p2[i].size() > m;
  rep(u,1,n+1){
    for(auto v:p2[u]){
      if(large[v]) pl[u].push_back(v);
    }
  }
  rep(ti,1,q+1){
    int u = read();
    int val = getV(u);
    a[u] = val;
    t[u] = ti;
    if(large[u]){
      distr[u] = {val, ti};
    }else{
      for(auto v:p2[u]){
        a[v] = val;
        t[v] = ti;
      }
    }
  }
  rep(i,1,n+1) printf("%d ",getV(i));
  return 0;
}

H - Candles

https://atcoder.jp/contests/abc219/tasks/abc219_h

N 个蜡烛, 第i个在Xi, 长度Ai

每分钟, 点燃的蜡烛长度-1, 直到 = 0, 而没点燃的不变化

初始在0,每分钟可以移动+1/-1, 如果当前位置有任何蜡烛,可以扑灭(不耗时)

求所有蜡烛长度剩余和的最大值

范围

N 300

xi [-1e9,1e9]

Ai [1,1e9]

我的思路

第一感觉是, 向左走 然后一直向右, 或者向右然后一直向左, 找这个折反点

问题是,会不会出现 左右左的情况?

例如-1上有10个, 2上有10个, -4 上1个, 都足够的长

那么 0 -> -1 -> 2 -> -4 的损失是21 * 1 + 11 * 3 + 1 * 6, 是最小的

这样证否了贪心折返

注意到N很小

甚至能接受 n^3, 考虑dp

dp[i..j][0] = [i,j] 区间内全部熄灭(烧完), 停在i 的 {最大长度, 时间}

问题是, 这种状态设计下, 最大长度和时间是有一致性吗?

题解

也是说, 仅从访问来看

如果已经访问过的区间是[X_i,X_j] 那么下一次 一定是[X_{i-1},X_j] 或[X_i,X_{j+1}]

修改一下问题

  1. 蜡烛可以负数长度
  2. 你可以在起始时移除一些蜡烛

显然新答案不会比原答案更大,而如果有一个答案的方案你照着走,然后把是会是负数的在一开始就移除,那么也可以达到这个原答案的最大值

那么

  1. 初始 分 = 0
  2. 计数 C 去 [0,N] 之间的一个值, 相当于剩余的蜡烛个数,但是不知道具体是哪C个蜡烛
  3. Hi等于对应蜡烛的高度
  4. 每次移动坐标变化1, 分数 -= C
  5. 对于走到一个未访问过的点, 且C > 0, 可以选择 C-=1, 分 += Hi

求最大分

显然最优解和答案是一样的

// 咦 我怎么看到上凸函数的影子

然后就可以dp了

dp[i][j][flag][k] = 已获的最大分数, $[X_i,X_j]$ 已经访问,$flag = 0$ 在$X_i$,$flag = 1$ 在$X_j$, $k$ 是剩余的要去熄灭的蜡烛个数

那么转移方程, 走到$X_i$

dp[i][j][0][k] = max(dp[i+1][j][0/1][k] - 距离 * k, dp[i+1][j][0/1][k+1] - 距离 * (k+1) + H[i])

转移方程, 走到$X_j$

dp[i][j][1][k] = max(dp[i][j-1][0/1][k] - 距离 * k, dp[i][j-1][0/1][k+1] - 距离 * (k+1) + H[i])

最后答案就是dp[0][n-1][0/1][0]

代码

https://atcoder.jp/contests/abc219/submissions/33780170

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
#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

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

const int N = 300;

ll dp[N+10][N+10][2][N+10];
pair<int,int> ph[N+10]; // pos height 起点 {0,0}
const ll INF = 0x3f3f3f3f3f3f3f3f;

void setMax(ll &v0,ll v1){ if(v1 > v0) v0 = v1; }

int main(){
  int n = read();
  rep(i,1,n+1){
    auto p = read();
    auto h = read();
    ph[i] = {p,h};
  }
  sort(ph,ph+n+1);
  int ci = -1; // center i 起始点
  rep(i,0,n+1){
    if(ph[i] == make_pair(0,0)){
      ci = i;
      break;
    }
  }
  rep(i,0,n+1) rep(j,0,n+1) rep(f,0,2) rep(c,0,n+1) dp[i][j][f][c] = -INF;
  rep(f,0,2) rep(c,0,n+1) dp[ci][ci][f][c] = 0;
  per(i,0,ci+1) rep(j,ci,n+1) {
    //dp[i][j][0][k]=max(dp[i+1][j][0/1][k]-距离*k,dp[i+1][j][0/1][k+1]-距离*(k+1)+H[i])`
    //dp[i][j][1][k]=max(dp[i][j-1][0/1][k]-距离*k,dp[i][j-1][0/1][k+1]-距离*(k+1)+H[i])`
    if(i == j) continue;
    rep(c,0,n+1) rep(f,0,2) {
      if(i < ci) {
        auto [x,h] = ph[i];
        const ll pos[] = {i+1, j};
        ll &res = dp[i][j][0][c];
        setMax(res, dp[pos[0]][pos[1]][f][c] - (ph[pos[f]].first - x) * c);
        if(c < n) setMax(res, dp[pos[0]][pos[1]][f][c+1] - (ph[pos[f]].first - x) * (c+1) + h);
      }
      if(j > ci){
        auto [x,h] = ph[j];
        const ll pos[] = {i, j-1};
        ll &res = dp[i][j][1][c];
        setMax(res, dp[pos[0]][pos[1]][f][c] - (x - ph[pos[f]].first) * c);
        if(c < n) setMax(res, dp[pos[0]][pos[1]][f][c+1] - (x - ph[pos[f]].first) * (c+1) + h);
      }
    }
  }
  printf("%lld\n", max(dp[0][n][0][0], dp[0][n][1][0]));
  return 0;
}

总结

F

一眼题

G

分类处理, 根号分治

做了不少分类的,又忘了分类

H

一个是题目转化去掉限制的技巧不会啊, 如果直接是转化后的题面, 那我还是会区间DP的, 但这个转化感觉遇到多了学一学转化

其实就是这里每分钟下降 燃烧着的个数, 会因为=0而难以维护, 通过支持负数 和可预先移除来让每分钟下降易于维护, 同时保持新的最大答案 = 原答案

n^3和dp的感知还是没有问题, 虽然在没有前面转化的情况下用处不大

参考

官方题解

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘
G(DP,树,multiset)H(王钦石二分,Alien Trick)

G - Game on Tree 2

https://atcoder.jp/contests/abc218/tasks/abc218_g

n点, 树, 点i上有数字Ai

初始 棋子在点1, 交替玩, 每次移动到未访问过的相邻点, 直到无法移动为止

先手 希望最大化访问过的中位数, 后手希望最小化中位数

如果他们都最优方案, 求这个中位数

限制

N 1e5

Ai [2,1e9]

我的思路

既然是树, 相当于1作为根, 走到叶节点结束, 路径上的中位数就是结果

换句话说, 每个叶节点 可以存储结果

如果能够算出每个从根到叶的结果, 那么简单的根据深度树上dp就完了(根 同的2倍深度 选最大, 根%2不同深度选最小)

想到的是相当于从中间剖开,那么dfs维护一个大根堆,一个小根堆,让它们元素个数差最多是1即可

代码

https://atcoder.jp/contests/abc218/submissions/33755229

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
#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 pb push_back

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

int A[100010];
vector<int> e[100010];

template<typename T> using maxSet = multiset<T, greater<T>>;
template<typename T> using minSet = multiset<T>;

int mid[100010];

template<typename T>
void balance(maxSet<T> &small,minSet<T> &large){
  while(large.size() > small.size()){
    small.insert(*large.begin());
    large.erase(large.begin());
  }
  while(small.size() >= large.size() + 2){
    large.insert(*small.begin());
    small.erase(small.begin());
  }
}

template<typename T>
int dfs(int u,int f,maxSet<T> &small,minSet<T> &large, int dep){
  // 插入
  if(small.size() == 0 || *small.begin() >= A[u]){
    small.insert(A[u]);
  }else{
    large.insert(A[u]);
  }
  balance(small,large);

  int res = 0;
  if(u != 1 && e[u].size() == 1){ // leaf
    res = (small.size() == large.size()) ? (*small.begin() + *large.begin())/2 : *small.begin();
  }else{
    vector<int> vals;
    for(auto v:e[u]) if(v != f) vals.push_back(dfs(v,u,small,large,dep^1));
    res = (dep==0)? *max_element(vals.begin(),vals.end()) : *min_element(vals.begin(),vals.end());
  }
  // 删除
  auto sptr = small.find(A[u]);
  if(sptr != small.end()){
    small.erase(sptr);
  }else{
    auto lptr = large.find(A[u]);
    assert(lptr != large.end());
    large.erase(lptr);
  }
  balance(small,large);
  return res;
}

int main(){
  int n = read();
  rep(i,1,n+1) A[i] = read();
  rep(i,1,n){
    int u = read();
    int v = read();
    e[u].pb(v);
    e[v].pb(u);
  }
  maxSet<int> small ; // 前一半
  minSet<int> large ;
  printf("%d\n",dfs(1,1,small,large,0));
  return 0;
}

H - Red and Blue Lamps

https://atcoder.jp/contests/abc218/tasks/abc218_h

N个灯, 你需要让R个红色,N-R个蓝色

如果 i 和 i+1 不同色 则有Ai的贡献

求最大的贡献

范围

N 2e5

R [1,N-1]

Ai [1,1e9]

2s

1024mb

我的思路

显然有个n^2的dp

dp[i][j][c] = 前i个有j个红色,第i个颜色为c,的最大贡献

dp[i][j][red] = max(dp[i-1][j-1][red] , dp[i-1][j-1][blue] + A[i])

dp[i][j][blue] = max(dp[i-1][j][red] +A[i], dp[i-1][j][blue])

但肯定超时

题解

如果红色比蓝色多, 则交换颜色数量

那么尽量多的两两不同,显然红色不相邻

那么把 A[i]+A[i+1] 看作整体

构造B[i] = A[i]+A[i+1] 数组

变成在B中选r个不相邻的元素使得总价值最大, 类似的dp[i][j][0/1] = 前i个,选了j个,第i个是否选的最大值

dp[i][j][1] = dp[i-1][j-1][0] + B[i]

dp[i][j][0] = max(dp[i-1][j][1],dp[i-1][j][0])

复杂度依然不能接受

但是有简单的性质: 可以王钦石二分

王钦石二分

  1. 当可选的越多(虽然题目要你求具体的), 那么总收益越大(单增)
  2. 当选的越多, 增量非严格递减凹函数(上凸)
  3. 不限制个数,容器得到最优方案

反过来, 如果我们指定一个最大收益, 那么可以快速算出需要可选的最少数量

如果变成二维图,是凹(上凸)函数,

方法是二分斜率, 对斜率找和凹函数的切点(切线)

而显然切线在y轴截距最大, f(x) = g(x) - k x, 原函数g(x), 截距函数f(x)

问题变成 给k, 找最大f(x), 而 g(x) - k x 从另一个角度看, 就是每个值-k 以后选x, 对于x没有限制时, 容易求的话,那就容易得到f(x) 和 x

求的话因为干掉了一个记录当前有多少个的限制, 从而可以简单dp

然后…. 我被卡double /long double 了

现实是,本身斜率就是 每次增量, 答案不会有小数,而切点对切线斜率也是单调影响, 所以,全整数就行了

代码

https://atcoder.jp/contests/abc218/submissions/33768310

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

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

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

int n;
ll a[200010];

pair<ll,int> f(ll v){ // f(斜率) => {最大截距, 横坐标(选的个数)}
  auto dp = vector(n,vector(2,pair<ll,int>{0,0})); // dp[i][第i个 选/不选] = {最大截距,个数}
  rep(i,1,n){
    auto [y0, c0] = dp[i-1][0];
    dp[i][1] = {y0 + (a[i-1] - v), c0 + 1}; // 当前选, 则上一个不选
    dp[i][0] = max(dp[i-1][0],dp[i-1][1]); // 当前不选, 则上一个可选可不选
  }
  return max(dp[n-1][0],dp[n-1][1]);
}

int main(){
  n = read();
  int x = read();
  x = min(x, n-x);
  rep(i,0,n-1) a[i] = read(); // [0..n-2]
  rep(i,0,n-1) a[i] += a[i+1]; // [0..n-2], 看成多了末尾多了一个0, 对最大值无影响
  ll L = 0, R = 3000'000'000; // 斜率
  // 二分, 这里可能 有多个点 让同一个斜率最大, 保证 斜率R < x <= 斜率L 即可, 注意到这这里可能 f(R).pos < f(L).pos < x, 但f(L).pos 只是斜率L上的任意一点 但只要x 斜率不大于 L即可
  while(L + 1 < R) (f((L+R)/2).second < x ? R : L) = mid;
  printf("%lld\n", f(L).first + x * L);
}

总结

G

没啥难的

H

感觉有的时候还是有点 PE的味道,偏数学一点

这里涉及 王钦石二分, 也是凸(凹)函数和二分相关的知识

然后这里double还不行,得long double

参考

官方题解

王钦石二分

發表於 更新於 分類於 ， Disqus： 文章字數： 1.4k 所需閱讀時間 ≈ 5 分鐘
G(DP)H(凸函数)

G - Groups

https://atcoder.jp/contests/abc217/tasks/abc217_g

有数字1..N

把它们分成k组(每组至少一个数)

要求, 每组中没有两个数 mod M 是相等的

问对于k=1…n 分别有多少方案

答案 模 998244353

方案: 如果两方案不同,至少有一个(x,y) 在一个中同组,另一个是不同组

范围

n 5000

2 <= m <= n

我的思路

显然 (n - 1) / m + 1 个 mod m = 1 的

我们也容易计算mod m = r 的有多少个

然后 计算这个方案数无非是两个方向, 正向算和逆向算

正向算, 则需要对每个方案唯一标识, 那么考虑用每组中( (value - 1 )mod m, value) 最小的作为组标识

似乎相互依赖很多, 不知道怎么算

反向算, 则就是同 mod的放在同一个位置了

题解

我感觉自己已经傻掉了, 看到n 5000 竟然没有想一下n方的算法

dp[i][j] 表示前i个数,分成了j组方案

如果没有同余限制

dp[i][j] = dp[i-1][j-1](单独放在j) + j * dp[i-1][j] (前面i-1已经放了j) 个

注意到同余的限制

那么j的放法就是 和它不同余的位置

已经有 ((i-1) / m)个和它同余了

dp[i][j] = dp[i-1][j-1](单独放在j) + (j-(i-1)/m)保证非负 * dp[i-1][j] (前面i-1已经放了j) 个

就没了

代码

https://atcoder.jp/contests/abc217/submissions/33750183

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;} // read

int main() {
  int n = read();
  int m = read();
  vector<vector<mint>> dp(n + 1, vector<mint> (n + 1));
  dp[0][0] = 1;
  rep(i,1,n+1){
    rep(j,1,i+1) { // j-(i-1)/m >= 0
      dp[i][j] = dp[i-1][j-1];
      if(j-(i-1)/m >= 0) dp[i][j] += dp[i-1][j] * (j-(i-1)/m);
    }
  }
  rep(i,1,n+1) printf("%d\n",dp[n][i].val());
  return 0;
}

H - Snuketoon

https://atcoder.jp/contests/abc217/tasks/abc217_h

初始在点0, 每秒可以-1,0,+1

N次事件: 在ti时刻, 若在Xi左侧且Di = 0,受到和Xi距离的伤害, 若在Xi右侧, 且Di = 1,受到和Xi距离的伤害

想要受到伤害最小化, 求最小值

范围

N 2e5

ti [1,1e9]

di 0/1

Xi [-1e9,1e9]

我的思路

看起来像dp

题解

$dp_{i,x} = $ 在Ti分钟 恰好在x 所需要受到的最小伤害, 为了方便认为T0 = 0

那么

dp[0][0] = 0

dp[0][!=0] = INF

若Di = 0, dp[i][x] = min(dp[i-1][y]) + max(0,Xi - x), 且|y-x| <= T[i] - T[i-1]

若Di = 1, dp[i][x] = min(dp[i-1][y]) + max(0,x - Xi), 且|y-x| <= T[i] - T[i-1]

很明显直接算会TLE

对于一个具体的i, 在二维平面上画点$(x,dp_{i,x})$, 其中横坐标范围是$[-T_i,T_i]$, 然后用线段连起来, 发现是个凸函数(下凸)

证明: 若对于i-1是下凸函数, 注意到min(dp[i-1][y]) 依然是凸函数, 而max部分也是凸函数,所以对于i 也是凸函数

因此问题变成维护那些拐点

每次min的操作,相当于把最小值的区间 向两侧 平移T[i]-T[i-1]

注意到 最初是[0,0], 其实就是把区间最左和最有移动到-Ti和正Ti

然后每次+max, 相当于一段不变, 一段 斜率+1, 还可能产生新的节点

如何维护呢?

注意到每次 min的过程核心等于向两侧平移, 如果以 和-Ti,Ti的距离来看, 甚至是没有变化

每次 +max, 是区间内斜率增加1, 那不妨直接记录 斜率1的起始点,斜率2的起始点, 斜率3的起始点( 可能会有重合, 这些点和左侧的距离, 和右侧的距离

-3 -2 -1 0 1 2 3 这样的斜率区间

如果加上 0 1 的

最终会变成 -3 -2 -1 0 1 2 3 4 这样的, 虽然可能有起点重合(斜率区间长度为0

代码

https://atcoder.jp/contests/abc217/submissions/33754555

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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
priority_queue<ll> ql; //大根堆,左侧, 记录斜率-1的起点,-2的起点,-3的起点,...到 -Ti的距离
priority_queue<ll> qr; //大根堆,右侧, 记录斜率 1的起点, 2的起点, 3的起点,...到  Ti的距离
 
int main() {
  int n = read();
  ll ans = 0;
  rep(i, 1, n+1) {
    ll t = read();
    ll d = read();
    ll x = read();
    // 让下凸的最小值一直是0
    if (d == 0) {
      if (x > t) { // 超出范围直接全部都加上
        ans += x - t;
        x = t;
      }
      if (qr.empty() || qr.top() <= t-x) { // 不影响右侧的
        ql.push(x + t);// 原来-1变-2, -2变-3,... , 新的-1的起点
      } else { // ... -3 -2 -1  0 ... 0 1 2 3 ... 影响右侧的,
        int pos = t - qr.top(); // 最小值的位置 右侧1斜率的起点
        qr.pop();
        ans += x - pos; // 让下凸的最小值 = 0
        ql.push(pos-(-t)); // 成为左侧新的 -1 斜率的起点
        qr.push(t - x); // 插入新的 斜率变化分割(距离右侧Ti
      }
    } else { // d = 1
      if (x < -t) { // 超出范围直接全部都加上
        ans += -t - x;
        x = -t;
      }
      if (ql.empty() || x - (-t) >= ql.top()) { // 不影响左侧
        qr.push(t - x); // 右侧最大点
      } else {
        int pos = ql.top() - t; // 最小值的位置, 左侧-1斜率的起点
        ql.pop();
        ans += pos-x;
        qr.push(t-pos);
        ql.push(x-(-t));
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}

总结

G

干啊, n方dp都想不到了,我

据说有数学的 N log N 的方法

H

知识点就是凸函数, 但是变化点较少时, 只需要维护这些点即可

然后维护的时候, 想办法保持尽可能多的不变量, 让变化记录是常数级别

参考

官方题解

發表於 更新於 分類於 Disqus： 文章字數： 975 所需閱讀時間 ≈ 3 分鐘
cow game, 差分约束

Layout

http://poj.org/problem?id=3169

数轴上放N个点(按照i的顺序坐标非严格单调递增

10000 个大于限制, 点i和点j距离不超过 di (1e6)

10000 个小于限制, 点i和点j距离不小于 di (1e6)

1s

64MB

求点1 和 点N的最大距离

题解

传说中日本众所周知的的cow game

也就是 全部小于号, (大于号同乘-1)

注意到上面要保证i的顺序( 所以 大-小 <= Di 或者 大减小 >= Di

然后说 差分约束本质上还是 最短路 只是需要建图

b-a <= d

转化成 a + d >= b, 所以 a -> b如果有边长d的话, 那么b的距离最小就是 a+d 还可能更小

b-a >= d的话

转化成 b-d >= a, 也就是 b -> a 如果有边长 (-d), 那么a的距离最小是 b-d, 还可能更小

总而言之转化成

点0 + ? >= 点1 的形式, 然后从点0 发一条长? 的边

代码

过不了编译版本

这poj g++版本太老了

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

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read
const int INF = 0x3f3f3f3f; // 1e9

vector<array<int,3> > e; // 有向边 [u,v,weight/length]

int main(){
  int N = read();
  int ML = read();
  int MD = read();

  // 建图
  rep(i,1,N) e.push_back({i+1, i, 0}); // 从i+1->i权值为0的边 保证顺序i的距离不大于i+1
  rep(i,0,ML){ //'喜欢'关系约束 <= DL
    int a = read();
    int b = read(); // 保证 b>a
    int d = read(); // |距离| <= DL[i]
    /* b-a<=d, 即 a+d>=b 从a到b权值为d的边 */
    e.push_back({a,b,d});
  }
  rep(i,0,MD){ //'不喜欢'关系约束 >= DD
    int a = read();
    int b = read(); // 保证 b>a
    int d = read(); // |距离| >= DD[i]
    /* BD - AD >= DD 即 BD - DD >= AD,  从BD到AD权值-DD的边*/
    e.push_back({b,a,-d});
  }

  // Bellman_Ford
  vector<int>dist(N+1,INF);// 最短距离
  dist[1] = 0;
  //循环N-1次 对所有边进行松弛操作
  rep(i,0,N-1) for(auto [u,v,w]: e) if(dist[u] != INF) dist[v] = min(dist[v], dist[u] + w);

  //再遍历一次所有边（第N次循环）如果本次有更新，则存在负环
  bool ngloop = false;
  for(auto [u,v,w]: e) if(dist[u] != INF && dist[u] + w < dist[v] ) ngloop = true;
  int ans = dist[N];
  if (ngloop) ans = -1;
  else if(ans == INF) ans = -2;
  printf("%d\n", ans);
  return 0;
}

AC 版本

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 <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define mt make_tuple

ll read(){ll r;scanf("%lld",&r);return r;} // read
const int INF = 0x3f3f3f3f; // 1e9

// 没有tuple
struct edge{
  int u;
  int v;
  int w;
  // 结构体直接赋值也没有
  edge(int _u,int _v,int _w){
    u = _u;
    v = _v;
    w = _w;
  }
};

vector<edge> e; // 有向边 [u,v,weight/length]

int main(){
  int N = read();
  int ML = read();
  int MD = read();

  // 建图
  rep(i,1,N) e.push_back(edge(i+1, i, 0)); // 从i+1->i权值为0的边 保证顺序i的距离不大于i+1
  rep(i,0,ML){ //'喜欢'关系约束 <= DL
    int a = read();
    int b = read(); // 保证 b>a
    int d = read(); // |距离| <= DL[i]
    /* b-a<=d, 即 a+d>=b 从a到b权值为d的边 */
    e.push_back(edge(a,b,d));
  }
  rep(i,0,MD){ //'不喜欢'关系约束 >= DD
    int a = read();
    int b = read(); // 保证 b>a
    int d = read(); // |距离| >= DD[i]
    /* BD - AD >= DD 即 BD - DD >= AD,  从BD到AD权值-DD的边*/
    e.push_back(edge(b,a,-d));
  }

  // Bellman_Ford
  vector<int>dist(N+1,INF);// 最短距离
  dist[1] = 0;
  //循环N-1次 对所有边进行松弛操作
  rep(t,0,N-1) rep(i,0,e.size()){
    edge &uvw = e[i]; // 不支持auto
    int u = uvw.u;
    int v = uvw.v;
    int w = uvw.w;
    if(dist[u] != INF) dist[v] = min(dist[v], dist[u] + w);
  }

  //再遍历一次所有边（第N次循环）如果本次有更新，则存在负环
  bool ngloop = false;
  rep(i,0,e.size()){
    edge &uvw = e[i]; // 不支持auto
    int u = uvw.u;
    int v = uvw.v;
    int w = uvw.w;
    if(dist[u] != INF && dist[u] + w < dist[v] ) ngloop = true;
  }
  int ans = dist[N];
  if (ngloop) ans = -1;
  else if(ans == INF) ans = -2;
  printf("%d\n", ans);
  return 0;
}

总结

就是如何对差分变成图

0%