Atcoder abc232

發表於 更新於 分類於 ， Disqus： 文章字數： 1.9k 所需閱讀時間 ≈ 6 分鐘
G(数学,dij,图论)H(构造)

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

G - Modulo Shortest Path

N 点 有向图

任意两点$i,j$, 有边$weight_{i\to j} = A_i+B_i \bmod M$

输出$i$到$N$的最短路

范围

n 2e5

m 1e9

3s

1024 mb

我的思路

说是有向, 实际上是两两联通,区别只是权重 $i \to j$ 是$A_i+B_j$, 而 $j\to i$是$A_j+ B_i$

n很大 不能可能枚举边,

但似乎, 1->a->b->c

如果忽略到mod, 边代价为= A1+Ba+Aa+Bb+Ab+Bc

也就是 A1+Bc+ (A+B)(a+b)

也就是(1->N) = 首项 + 末项 + 中间的AB

ans - (A1+Bn + (A+B)(…)) = 0 (mod M)

而注意到直接走, 就是$(A1+Bn)%M$, 所以已经存在一个[0,M)的答案, 所以最优的一定也是[0,M)内

如果 Bi 和前面的不超过M, Ai和后面的和不超过M

那么显然i只会让总代价增加(Ai+Bi), 因为可以去掉它,把前后拼起来

这里可以看出需要

(A0 + Bi)mod m + (Ai + B1) mod m < (A0 + B1) mod m < m

所以前面一定也是 [0,m)

(A0 + B1 + Ai + Bi) % m < (A0 + B1) % m < m

因此 (A0+B1+Ai+Bi) >=m, 而且这个减m 要在 上面求和的两个mod 中实现

((A0 + B1)%m + Ai + Bi) % m < (A0 + B1) % m < m

对于A0+B1 < m,

如果 Ai > A0 则Ai+B1 >= m, 如果Ai < A0, 则Bi > B1

如果 Bi > B1 则A0+Bi >= m, 如果Bi > B1, 则Ai > A0

对于2m > A0+B1 >= m

则 m - B1 <= Ai < A0, m - A0 <= Bi < B0

可以看成, 每次路径上插入一个点, 都是让总代价单调下降 (m - (ai+bi)%m)

初始$1 \to N$, 然后每次找一个去插入

但是点插入的顺序, 如何做?

按下降排序? , 前i个最大下降结果, 可是还会收到可插入的影响? 如何维护状态

另外就是这性质 有没有办法优化dij

题解

建立等价图G’ + dij

点 $m_{0},\cdots,m_{M-1}$

$m_{i} \to m_{i+1}$, 权重1, 连成环

对于点$i = 1 \to N$, 建立 点$i \to m_{-A_i}$ 权重0

对于点$i = 1 \to N$, 建立 点$m_{B_i} \to i$ 权重0

这样就是$n+m$个点, $m+2n$条边

神奇啊, 这样原来的s->t 的代价和新图上的s->t代价一致

因为 每次i 到j相当于 代价 (Ai+Bi )% m = (Bi-(-Ai))% M,在环上就是$-A_i$沿增顺序走到$B_i$

剩下就简单了, 离散化一下m 毕竟至多2n个点, 中间的表示原来的点的也可以去掉, 只留下离散的m 即可

但是处理的时候 要注意! i的出点 和 j的入点同一个值, 则需要i在j之前!, 所以注意不能sort, 要么stable sort, 要么按照$\lbrace ai,i\rbrace$ 来sort

代码

https://atcoder.jp/contests/abc232/submissions/34625822

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
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;} // read
template <typename T> using minPQ = std::priority_queue<T,std::vector<T>, std::greater<T>>;
const int N = 2e5;
const int INF = 1e9+10;
std::vector<std::pair<int,int> > e[2*N+10]; // e[u] = {weight, v}
int a[2*N+10];
int l[2*N+10];// 下标
int main() {
  int n = read();
  int m = read();
  int *b = a+n;
  rep(i,0,n) a[i] = (m - read()) % m; // -Ai
  rep(i,0,n) b[i] = read(); // Bi

  rep(i,0,n) e[n+i].push_back({0,i}); // 点 Bi -> -Ai
  n *= 2;
  std::iota(l,l+n,0);
  std::sort(l,l+n, [=](int i, int j) { return a[i] == a[j] ? i < j : a[i] < a[j]; }); // 按mod的值排序 下标, 允许重复点, 或者 stable_sort
  rep(i,0,n) e[l[i]].push_back({(a[l[(i+1)%n]] + m - a[l[i]]) % m, l[(i+1)%n]}); // 环上离散的点 建立环
  // dij 0 -> n-1
  std::vector<int> d(n,INF); // 距离
  minPQ<std::pair<int,int> > h; // {dis, u}
  for (h.push({0,0}); !h.empty();) {
    auto [x,u] = h.top();
    h.pop();
    if (x >= d[u]) continue;
    d[u] = x;
    for(auto [w,v]:e[u]) if(x+w<m) h.push({x+w, v});
  }
  printf("%d\n",d[n-1]);
  return 0;
}

H - King’s Tour

H行 W列 的格子, 一个王

8临移动

一个合法的路径就是每个格子恰好走一次

构造一个从$(1,1)$ 开始 $(a,b)$ 结束的合法路径

保证存在

范围

h 100

w 100

2s

1024mb

我的思路

既然构造先考虑特殊情况

nxm 走到右下角

那么nxm 至少一个是奇数就可4临的方式走到, 否则 对于最后两列/行, 走来剩下2x2,也可以 z 字走完

因此nxm走到右上角, 那么始终可行

那么是不是可以拆成

1
2
3
4
5
6
7
8
9
S

                1
-----------------
       T|       2
        |
        |
        |
       4|3

或者竖着切

1
2
3
4
5
6
7
8
9
S      |
       |
       |
       |T        4
       |----------
       |         3
       |
       |
      1|2

然后一些情况

T是角落,那直接一个块

T贴底边

1
2
3
4
5
6
S 1|2
   |
   |
   |
   |T
----------

这个问题是 如果左边只有宽1, 因为T不在角落,所以右边还有空隙, 所以先除开T的两列, 完成右侧, 再从3到T

1
2
3
4
5
6
S1|2
  | 
  | 
  | 
 T|3 
----------

这感觉有方案不难想,但难写,写吐了

代码

TL;DR;

https://atcoder.jp/contests/abc232/submissions/34627109

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

pair<int,int> col(const array<int,4> &M,const pair<int,int> &p){// 列对面点
  return {p.first^M[0]^M[2],p.second};
}

array<int,4> rmcol(const array<int,4> &M,int j){ // 删掉s所在列
  auto [i0,j0,i1,j1] = M;
  if(j == j0) return {i0,j0+1,i1,j1};
  else return {i0,j0,i1,j1-1};
}

void o(pair<int,int> p, int rev) { // 输出
  auto [i,j] = p;
  if(rev) o({j,i},0);
  else printf("%d %d\n",i,j);
}

void line(pair<int,int> s,pair<int,int>t,int rev){ // 画线段
  auto [si,sj] = s;
  auto [ti,tj] = t;
  int dj = tj > sj?1:-1;
  if(si == ti) for(int j = sj;j!=tj+dj;j+=dj) o({si,j},rev);
  else line({sj,si},{tj,ti},rev^1);
}

void f(array<int,4> M,pair<int,int> s,pair<int,int> t,int rev/*ij翻转*/){
  auto [i0,j0,i1,j1] = M; // (i0,j0) <= (i1,j1)
  auto [si,sj] = s;
  auto [ti,tj] = t;
  int di = ti > si?1:-1;
  int dj = tj > sj?1:-1;
  if(i0 == i1 || j0 == j1) { // 1xn, nx1
    line(s,t,rev);
  } else if(sj == tj) { // 保持不同列
    f({j0,i0,j1,i1},{sj,si},{tj,ti},rev^1);
  } else if(abs(j0-j1) == 1){ // nx2, sj != tj
    if(si == ti){ // U形
      line(s,col(M,s),rev);
      line(col(M,t),t,rev);
    }else{
      for(int i = si;i!=ti;i+=di) line({i,sj},{i,tj},rev); // Z形
      o({ti,sj},rev);
      if(ti != (si^i0^i1)){ // U形
        line({ti+di,sj}    ,col(M,s)  ,rev);
        line(col(M,{si,tj}),{ti+di,tj},rev);
      }
      o(t,rev);
    }
  } else if(abs(sj-tj) == 1 && si != ti && (ti == i0 || ti == i1)){ // 特殊 col > 2, t 在第2列对称方向, sj != tj
    line(s,col(M,s),rev);
    line({ti-di,tj},{si,tj},rev);
    f(rmcol(rmcol(M,sj),tj), {si,tj+dj},{ti,tj+dj},rev);
    o(t,rev);
  } else { // 一般 消耗掉s所在列, sj != tj
    line(s,col(M,s),rev);
    f(rmcol(M,sj),col(M,{si,sj+dj}),t,rev);
  }
}

int main(){
  int h = read();
  int w = read();
  int a = read();
  int b = read();
  f({1,1,h,w},{1,1},{a,b},false);
  return 0;
}

总结

G

感觉dij倒是没啥, 主要还是数学智慧没有

感觉算是模运算在图论上的意义?

然后dij虽然不能负边,零边还是可以的!, 因此代码可以不需要对重复意义的mod点做合并, 但是要注意之间的转移顺序有偏序关系类才能做还要保持关系, 这里是 入入入入入 -> 出出出

H

构造,感觉以我的智力,学了也白学

虽然这个自己想出来了, 但写起来感觉好恶心

模拟完全不会,递归编码完全不会

感觉我的问题在于给了太多参数,又是上下左右,又是起始结束, 其实完全可以就是长宽+目标点

然后把子问题答案转义, 反正才100,随便乱搞,又不是3000 * 3000

参考

官方题解