Atcoder abc261

發表於 更新於 分類於 ， Disqus： 文章字數： 1.8k 所需閱讀時間 ≈ 6 分鐘
G(DP, 字符串),H/Ex(图,DP,拓扑排序,dij,拆点)

G - Replace

字符串S,T包含小写英文

可以执行k种 操作, 任意次 任意顺序

第i种 操作: 1代价, 把一个字符Ci 换成 字符串Ai

问S变成T 的最小代价 或不可能

限制

|S|<=|T| <= 50

k <= 50

|Ai| <= 50

2s

1024mb

题解

我的思路

既然是字符(离散)换成字符串

那么岂不是 dp[i][j] 表示 S前i 个换成 T前j个

dp[i][j] = dp[i-1][j-k], s[i] -> T[j-k+1..j] 可行

那么问题是如何判断可行

换句话说, 如果我们能算出 T[j-k+1..j] 能否逆向变成s[i] 也是办法

但是感觉这个会分叉很多

题解

dp[i][j][c] = 最小代价T[i..j] => 字符 c

f[i][j][k][l] = 最小代价T[i..j] => 字符串 A[k][1..l] (这个很关键, 是把字符中前缀设置成状态)

1
2
3
for i = N -> 1:
  for j = i -> N:
    计算 f[i][j][k][l], f[i][j][c], f[i][j][k][1]

计算f[i][j][k][l] 时 (T[i..j] => A[k][1..l])

注意到替换时顺序不会变相当于

时 (T[i.m][m+1.j] => A[k][1..l-1] A[k][l])

$f[i][j][k][l] = min(f[i][m][k][l-1] + dp[m+1][j][A[k][l]])$

计算dp[i][j][c] / f[i][j][k][1]

  1. 本身就是c字符, i==j, Ti = c, 0
  2. 一步到位 T[i..j] = A[k], C[k] = c
  3. 先转换到某个A[k] 再转一步, min(f[i][j][k][|A[k]|]+1),C[k] = c

f[i][j][k][1] 从dp[i][j][A[k][1]] 中读即可

这大概是O(n^4)的状态

O(n^5) 的转移复杂度

这其中还有一个问题是, 对于A和C都是单个字符的, 你会出现T[i...j] -> c0 -> c1 -> c2

你需要求最短路dij/spfa松弛 即可

代码

https://atcoder.jp/contests/abc261/submissions/33608140

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

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

int read(){int r;scanf("%d",&r);return r;} // read

const int INF = 0x3f3f3f3f; // 无穷大
const int maxc = 'z' - 'a'; // 最大字符对应数字

vector<int> t;
int f[60][60][60][60]; // [l..r] => a[k][0...i] (prefix(a[k][i]))
int dp[60][60][30]; // [l..r] => char c

int c[60] = {maxc + 1}; // 不存在的字符
vector<int> a[60]; // c[i] -> a[i];
vector<pair<int,int> > c2c; // 单字符映射

char tmp[60];
int lcStr2VecInt(vector<int> & res){ // lower case string to vector<int>
  scanf("%s", tmp);
  int sz = strlen(tmp);
  res.resize(sz);
  rep(i,0,sz) res[i] = tmp[i] - 'a'; // s 放在 c[0],a[0]
  return sz;
}

void setMin(int &v0,int v1){v0 = min(v0,v1);}

int main(){
  int ns = lcStr2VecInt(a[0]); // s 放在 c[0],a[0]
  int nt = lcStr2VecInt(t); // t
  int K = read() + 1; // 包含s
  rep(i,1,K){
    scanf("%s", tmp);
    c[i] = tmp[0] - 'a';
    if(lcStr2VecInt(a[i]) == 1) c2c.push_back({c[i], a[i][0]});
  }
  rep(l,0,nt) {
    rep(r,l,nt) { // 全部设置为无穷大
      rep(k,0,K) rep(i,0,50) f[l][r][k][i] = INF;
      rep(c,0,maxc+1) dp[l][r][c] = INF;
    }
    dp[l][l][t[l]] = 0; // 本身就是字符
  }
  // --- init ---
  per(l,0,nt) rep(r,l,nt){ // T[l..r], 各种顺序都行 保证依赖关系先被运算
    rep(k,0,K){
      int sz = a[k].size();
      rep(i,1,sz){ // T[l..j][j+1..r] = > a[k][0..i-1],a[k][i]
        int &v = f[l][r][k][i];
        rep(j,l,r) setMin(v, f[l][j][k][i-1] + dp[j+1][r][a[k][i]]);
        if(i == sz - 1) setMin(dp[l][r][c[k]], v + 1); // T[i..j] => a[k] => c[k]
      }
    }
    // dp[l][r][c]=min(dp[l][r][k][|a[k]|]) + 1 = min(len > 1(上面算了), len = 1) + 1, len = |a[k]|
    rep(c,0,maxc+1) for(auto [c0, c1]: c2c) setMin(dp[l][r][c0], dp[l][r][c1] + 1); // 26 次 松弛
    rep(k,0,K) setMin(f[l][r][k][0], dp[l][r][a[k][0]]); // 更新 f 中首字母
  }
  int & ans = f[0][nt-1][0][ns-1];
  printf("%d\n", ans == INF? -1: ans);
  return 0;
}


H/Ex - Game on Graph

N点, M边

有向边 [ui,vi,weight i], 无重边 无自环

初始,点v上有个棋子

T和A交替游戏

  • 如果棋子所在点 没有向外路径 则结束游戏
  • 如果有路径,任选一个走路径

T 让weight和尽量小, A让和尽量大

T(结束游戏优先级 > 和尽量小)

A(让游戏无限循环优先级 > 和尽量大)

限制

N 2e5

M 2e5

Wi [0,1e9]

2s

1024mb

题解

我的思路

并不是有环就一定无限, 例如 a->b->c->d->a

a连了个有限的, c也连了个更短的有限的

那么虽然你可以走到b,让对手走到c,这样在走到有限的 会比a直接去到有限的更短

考虑从叶子反过来, 判断是否有限,感觉bfs或者spfa/dij的感觉

题解

图上环状dp

dp[x][0] 从x出发 尽量小

dp[x][1] 从x出发 尽量大

dp[x][0] = min (f[y][1] + weight[x][y]), 相当于 反向图的最短路

dp[x][1] = max (f[y][0] + weight[x][y]), 需要所有f[y][0] 被计算后才有意义

然后就反图+拓扑+dij 就没了???

我感觉这个条件必要, 但总觉得没有证明到充分

代码

https://atcoder.jp/contests/abc261/submissions/33603896

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
#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 dp[2][200010];
ll mx[200010]; // 只记录1的, 因为0的直接记录在pq和dp中, 而1的在子节点未完全计算时pq和dp都不会记录
int deg[200010]; // 正向图出度, 反向图入度
vector<pair<int,int> > g[200010]; // 反向图 v = {u, weight}
 
template <typename T> using minPQ = priority_queue<T,vector<T>, greater<T>>; // 小根堆
 
int main(){
  int n = read();
  int m = read();
  int v = read();// 起点
  rep(i,0,2) fill(dp[i],dp[i]+n+1,-1); // 未访问
  rep(i,0,m) {
    int u = read();
    int v = read();
    int w = read();
    g[v].push_back({u, w});
    deg[u] ++;
  }
  minPQ<array<ll,3>> q; // 小根堆, dij 每次找最小的未达点变为可达 {距离, 0/1, 点}
  rep(i,1,n+1) if(deg[i] == 0) rep(j,0,2) q.push({0, j, i}); // dp[0/1][i] 反向入度为0 的节点
  while(q.size()) {
    auto [d, i, u] = q.top(); q.pop();
    if(dp[i][u] != -1) continue; // 计算过
    dp[i][u] = d; // 更新值
    if(!i) { // dp[0][u] -> dp[1][v]
      for(auto [v, w] : g[u]) { // 更新反向边 并更新 deg[v] --
        mx[v] = max(mx[v], d + w); // 更新值但是 不一定进入pq dp[x][1] = max (f[y][0] + weight[x][y])
        if(--deg[v] == 0) q.push({mx[v], 1, v}); // dp[1][v] 只能所有计算都计算后才有意义
      }
    } else for(auto [v, w] : g[u]) q.push({d + w, 0, v}); // dp[1][u] -> dp[0][v] dij
  }
  if(dp[0][v] == -1) printf("INFINITY\n");
  else printf("%lld\n", dp[0][v]);
  return 0;
}

总结

G

大小只有50的情况, 对字符串中的前缀设计状态, 从而有dp的状态

第二就是 小的情况 多次松弛简单也效率满足, 不需要上dij

H/Ex

我感觉这个条件必要, 但总觉得没有证明到充分???

可能关键在于,虽然点上有 0/1两个状态,但实际上这两个状态不相关, 所以其实每个点可以拆点

这样就变成了路径的逆向dp了, 有环一定不行, 所以关键在这个拆点 -> 变成dij

参考

官方题解