Atcoder abc217

發表於 更新於 分類於 ， 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

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

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

参考

官方题解