Atcoder abc320

發表於 更新於 分類於 ， Disqus： 文章字數： 1k 所需閱讀時間 ≈ 3 分鐘
G(hall_theorem,二分)

https://atcoder.jp/contests/abc320

G - Slot Strategy 2 (Hard)

n个只包含’0’-‘9’的长度m的字符串在旋转

对于一个时刻 最多停止一个字符串旋转，字符串展示字符s[i][t%m]

问 最少多少时刻 让所有字符串停止，且展示的字符一样， 或无方案

n 100

m 1e5

2s

1024mb

我的思路

注意到 只包含数字，而数字只有10个，所以可以指定数字比较方案优劣

那么对于给定数字以后，每个字符串将变成一个0/1 bool串，其中 true表示 对应位置是要指定的结果数字

有一点想搞可反悔的dp

首先如果每个字符串都有指定数字才有可能，这样就是依次来都是一个方案，只是可能不是最短时间

但实际上可以变成二分图

首先 左侧是 字符串id, 右侧是可以逐步增加点的的时刻, 只要有对应位置就建立一条边

这样如果有 ans = |n| 就是答案， 这样最坏的情况是 n*m个右侧点，也就是所有字符串都集中在一个循环时刻上了

这里可以优化一下 右侧增点的过程，把与左侧无连接的点直接预处理掉，变成 [offset,vector<int>left]

那么每次增加 至少增加一次连边，

想用hall定理，也就是什么时刻 左侧的任意点的右向连接数一定大于左侧点数， 这个量级的上限

因为每循环一轮，所有左侧点连的点个数 至少增1,所以 总边数不会超过n^2

似乎就没了， 然而TLE了2个点

题解

一样的思路，但是二分答案

因为上面我的代码的问题是 直接做flow的时间复杂度太大了，虽然每次只找一个流量<=1的，但是其中的无效点和边还是会被循环到

然后还有一个很关键的优化是 一个左侧点最多匹配右侧n个点！！！！，因为可能左侧1全匹配右侧，左侧其它全匹配右侧1！这样会爆炸

更进阶的问题: ARC106E

代码

https://atcoder.jp/contests/abc320/submissions/49672663

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

int n,m;
const int INF=100*100000;
char s[100][100010];
int ans = INF;
vector<pair<int,vector<int> > > right_[10]; // {tick, vector<int> left}
int solve(const vector<pair<int,vector<int> > >&right){
  int l = 0;
  int r = INF+1;
  auto check=[&](int t){
    int S = 0;
    int T = 1;
    int loff = 2;
    int roff = 2+n;
    auto g = atcoder::mf_graph<int>(2+n+right.size());
    rep(i,0,n) g.add_edge(S,loff+i,1); // S -> string
    rep(j,0,size(right)) {
      auto &[tick,lefts] = right[j];
      g.add_edge(roff+j,T,t/m+int((t%m) >= tick));
      for(auto left:lefts) g.add_edge(loff+left, roff+j, n);
    }
    return g.flow(S,T,n) == n;
  };
  while(r-l > 1){
    int mid = (l+r)/2;
    if(check(mid)){
      r = mid;
    }else{
      l = mid;
    }
  }
  return check(l)?l:r;
}

int main(){
  n=read(); // <= 100
  m=read();
  rep(i,0,n) scanf("%s",s[i]);

  vector count(10,vector<int>(n,0)); // count[char][row]
  rep(i,0,n) rep(j,0,m) {
    auto res = ++count[s[i][j]-'0'][i];
    if(res > n+1) s[i][j] = '9'+1; // 无效化, 让左侧最多配前n个 ！！！！！！！！！！！！！！！！！！！！！！！！
  }

  rep(j,0,m) {
    vector pos(11,vector<int>()); // 多一维无效化 !!!
    rep(i,0,n) pos[s[i][j]-'0'].push_back(i);
    rep(c,0,10) if(pos[c].size()) right_[c].push_back({j,pos[c]});
  }

  rep(v,0,9+1) {
    int sum = 0;
    rep(i,0,n) sum += bool(count[v][i]);
    if(sum == n) ans = min(ans, solve(right_[v]));
  }
  printf("%d\n",ans==INF?-1:ans);
  return 0;
}

总结

F: 我觉得的dp转移的for， 很有意思，虽然没看官方题解的，但是我自己想的这个真是第一次想到

G: 几个问题

  1. 虽然每次找流至多1,但是每次的复杂度还是 点和边有关，这样还是二分会更少的运算次数
  2. 没有把一个显然的左侧只有连向右侧前n个点有效的 截断

能自己想到二分图 和 量级 是ok的