Atcoder abc228

發表於 更新於 分類於 ， Disqus： 文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘
F(博弈论,矩阵,二维前缀和,st表)G(DP,bitmask)H(DP,斜率优化)

https://atcoder.jp/contests/abc228/tasks

F - Stamp Game

w乘h的矩阵初始全白色,每个有数字aij

T 可以染黑 h1 w1

A 可以染白 h2 w2

T 操作一次, S操作一次

分数= 黑色块之和

T 让尽可能大, A让T尽可能小, 求答案

范围

h,w 1000

aij [1,1e9]

2s 1024mb

我的思路

感觉就是二维常见运算

因为长度如果超了长度, 可以贪心把对应位置全覆盖,可以取min, h2=min(h2,h1), w2=min(w2,w1)

ans = max(f(i,j))

f(i,j) = sum(i,j) - max(g((range))

应该就过了吧

代码

果然就过了

https://atcoder.jp/contests/abc228/submissions/34466225

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

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 a[1010][1010];

int H;
int W;
int h[2];
int w[2];

ll mems[2][1010][1010]; // [0]
ll memcol[2][1010][1010]; // [0]
ll st[1010][1010];

ll col(int o,int i,int j){
  ll & r = memcol[o][i][j];
  if(r) return r;
  if(i == 0){
    rep(y,0,h[o]) r += a[i+y][j];
  }else{
    r = col(o,i-1,j) - a[i-1][j] + a[i+h[o]-1][j];
  }
  return r;
}

ll s(int o,int i,int j){
  ll & r = mems[o][i][j];
  if(r) return r;
  if(j == 0){
    rep(x,0,w[o]) r+= col(o,i,j+x);
  }else{
    r = s(o,i,j-1) - col(o,i,j-1) + col(o,i,j + w[o]-1);
  }
  return r;
}

int main(){
  H = read();
  W = read();
  h[0] = read();
  w[0] = read();
  h[1] = read();
  w[1] = read();
  h[1] = std::min(h[1],h[0]); // h[0] >= h[1]
  w[1] = std::min(w[1],w[0]); // w[0] >= w[1]
  rep(i,0,H) rep(j,0,W) a[i][j] = read();
  ll ans = 0;
  rep(i,0,H-h[1]+1) rep(j,0,W-w[1]+1) st[i][j] = s(1,i,j);
  int hp = 0; // h pwr
  int wp = 0; // w pwr
  for(;(1<< (hp+1))<=h[0]-h[1]+1;hp++)rep(i,0,H-h[1]+1)rep(j,0,W-w[1]+1)st[i][j]=std::max(st[i][j],st[i+(1<< hp)][j]);
  for(;(1<< (wp+1))<=w[0]-w[1]+1;wp++)rep(i,0,H-h[1]+1)rep(j,0,W-w[1]+1)st[i][j]=std::max(st[i][j],st[i][j+(1<< wp)]);
  rep(i,0,H-h[0]+1) rep(j,0,W-w[0]+1) ans = std::max(ans, s(0,i,j) - std::max(
      std::max(st[i                    ][j],st[i                    ][j+w[0]-w[1]-(1<<wp)+1]),
      std::max(st[i+h[0]-h[1]-(1<<hp)+1][j],st[i+h[0]-h[1]-(1<<hp)+1][j+w[0]-w[1]-(1<<wp)+1])
  ));
  printf("%lld\n",ans);
  return 0;
}

G - Digits on Grid

高h宽w的矩阵

每个包含数字1~9

首先T放一个棋子, 然后两个交替N次

  1. T把棋子移动到同一行的任意一个格子上,移动后记录所在的值
  2. S把棋子移动到同一列的任意一个格子上,移动后记录所在的值

把这些数按顺序连起来, 形成一个长2n的数

问能形成多少种

注: 这里根据样例知道 可以停在原格子上

mod 998244353

范围

h,w [2,10]

n 300

3 s

1024 mb

我的思路

想法是记录开始第i步到[i][j] 有多少种, 但直接这样搞的话, 没法处理重复的问题

第二个想法是有没有办法聚类,

f[{下标集合}] = 方案数

问题是 不知道这种下标集合 的上限是多少

S0横 + ch和其中一个同行 -> S1纵

S0纵 + ch和其中一个同列 -> S1横

题解

哇,就是类似的

但是注意到 比如 S0横 + ch和其中一个同行 -> S1纵

真正有关系的只有 s0中占了多少行

这样的话 状态数 就不是2^100 而是2^10了

剩下就暴力就完了

代码

https://atcoder.jp/contests/abc228/submissions/34466640

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;} // read

const int N = 10;
int a[N+10][N+10]; // 输入数字矩阵
int r2c[1 << N][N]; // [行bitmask][数字digit] = 列bitmask
int c2r[1 << N][N]; // [列bitmask][数字digit] = 行bitmask

int main() {
  int n = read();
  int m = read();
  int k = read();
  char tmp[N+10];
  rep(i,0,n){
    scanf("%s",tmp);
    rep(j,0,m) a[i][j] = tmp[j] - '1'; // 1-9 转换成 0~8
  }
  // s bit集合
  rep(s,1,1<<n)rep(i,0,n)if(s&(1<<i))rep(j,0,m) r2c[s][a[i][j]] |= 1<<j;
  rep(s,1,1<<m)rep(j,0,m)if(s&(1<<j))rep(i,0,n) c2r[s][a[i][j]] |= 1<<i;
  std::vector<mint> r(1<<n,0);
  r.back() = 1; // 一个都没选的时候, 满集
  while(k--){
    std::vector<mint> c(1<<m,0);
    rep(s,1,1<<n) rep(d,0,9) c[r2c[s][d]] += r[s]; // row -> col
    r = std::vector<mint>(1<<n,0);
    rep(s,1,1<<m) rep(d,0,9) r[c2r[s][d]] += c[s]; // col -> row
  }
  mint ans = 0;
  rep(s,1,1<<n) ans += r[s];
  printf("%d\n", ans.val());
  return 0;
}

H - Histogram

长n的整数序列, A,C, 可以操作任意次

每次任选一个 A[i] +1, 代价C[i]

所有操作结束后, 还需要花费代价 X 乘 A中不同数的个数

范围

n 2e5

x 1e6

ai,ci[1,1e6]

2s

1024mb

我的思路

考虑直接对A排序,

那么对于i来说,如果a[j…i] 都提升到i

那么代价是 a[j..i] 变成a[i] 每个和a[i]差乘上系数, 再减去 X 乘上 (原来种数-1)

dp[i] = max(dp[j-1] + cost[j..i])

但是显然这样直接搞是n^2的

cost[j..i] = sum t=j..i, (a[i] - a[t])c[t] - X * (cnt[i] - cnt[j-1])

有一点是 如果 a[j..k] 一段是相等, 根据那么要么全部变成i, 要么全部不变, 所以对答案可能有贡献的j一定满足a[j-1] != a[j]

上面的表达式cost(j,i)另一个角度对于给定的i

cost[j..i] = sum t=j..i, c[t]a[i] - a[t]*c[t] - X * (cnt[i] - cnt[j-1])

可以拆分成3部分

  1. 常数部分 -Xcnt[i]
  2. 与i 无关,随着j越小增加的部分, -a[t]c[t] + Xcnt[j-1], 虽然本身右侧cnt不是每个+1, 但是可以把这整个合并成一个只与t相关的部分, 还可以和dp[j-1] 合并
  3. 与i,t相关 的c[t]a[i]

f(i,j) = k(j) a[i] + g(j) + C

问题是这个 似乎并不知道如何找最小值

题解

排序和贪心显然

但是dp 不用反过来, 直接正向

dp[i] = min(dp[j]+X + sum t=j+1..i, (a[i] - a[t])c[t] )

dp[i] = X + min(dp[j] + a[i](prec[i]-prec[j]) - (preac[i] - preac[j]))

dp[i] - a[i]prec[i] + preac[i] = X + min(dp[j] - a[i]prec[j] + preac[j])

令 y[i] = y[i]+preac[i]

要求的ans = y[i] - preac[i]

y[i] - a[i]prec[i] - X = min(y[j] -a[i]prec[j])

看成一次函数b[i] = y[j] - k[i]x[j]

其实就是很多过点(x[j],y[j]) 斜率为k[i]的直线 的最小截距

注意到k[i] = a[i], 所以斜率随着i增大而增大

而x[j] = prec[j] 也是随j增大而增大

因此需要维护一个凹(下凸)点集

查询的时候二分即可

然后边界如果是把i以前全部变成a[i]

y[i] - a[i]prec[i] - X = min(y[0] -a[i]prec[0])

均为0即可

代码

https://atcoder.jp/contests/abc228/submissions/34483299

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
#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 = 200000;
pair<ll,ll> in[N+10];
vector<int> que = {0}; // 凸的下标
ll pc[N+10]; // pre sum c
ll y[N+10]; // y[0] = [0]

bool le(pair<ll,ll>k0, pair<ll,ll>k1){ // k0 < k1
  auto [y0,x0] = k0;
  auto [y1,x1] = k1;
  ll b0 = y0/x0;
  ll b1 = y1/x1;
  if(b0 != b1) return b0 < b1;
  ll r0 = y0 % x0;
  ll r1 = y1 % x1;
  if(!r0 || !r1) return r0 < r1; // 其中一个是0
  // r0/x0 < r1/x1  <->  x1/r1 < x0/r0
  return le({x1,r1},{x0,r0});
}

int k2j(int k) { // 斜率 k => 最小截距 对应切点idx
  int idx = 0;
  for(int i=(1<<17);i;i>>=1) if(idx+i < (int)que.size()) { // 2^17 = 131072, 2^20 > 200000
    int i0=que[idx+i-1];
    int i1=que[idx+i];
    if(le({y[i1]-y[i0],pc[i1]-pc[i0]},{k,1})) idx += i; // k of (i0->i1) < k
  }
  return que[idx];
}

int main() {
  int n = read();
  ll X = read();
  rep(i,1,n+1) { // in[0] = {0,0}
    ll a = read();
    ll c = read();
    in[i] = {a,c};
  }
  sort(in+1,in+n+1); // 按a排序
  rep(i,1,n+1) pc[i] = pc[i-1] + in[i].second; // c前缀和
  rep(i,1,n+1){
    int j = k2j(in[i].first);
    y[i] = y[j] + (pc[i]-pc[j])*in[i].first+X; // y[i] - a[i]prec[i] - X = min(y[j] -a[i]prec[j])
    while(que.size() > 1) { // 至少两个点 保证 (yi-y1)/(xi-x1) > (y1-y0)/(x1-x0)
      int i0=que[que.size()-2];
      int i1=que.back();
      // 注意overflow
      if(le({y[i1]-y[i0],pc[i1]-pc[i0]},{y[i]-y[i1],pc[i]-pc[i1]})) break;
      que.pop_back();
    }
    que.push_back(i);
  }
  ll ans = y[n];
  rep(i,1,n+1) ans -= in[i].first*in[i].second;
  printf("%lld\n",ans);
  return 0;
}

总结

F

没啥难的

G

大的方向对了, 但是在提取必要信息时有问题, 没提取出只和行/列相关

H

算是又看了一个斜率优化的实际例子吧

大概是 f(i) = g(j) + n(i)(单调递增) * m(j)(单调递增?), (j < i) 的形式可以考虑 把k_i = n(i), 剩下的, 且单调递增

参考

官方题解