Atcoder abc239

發表於 更新於 分類於 ， Disqus： 文章字數： 1.9k 所需閱讀時間 ≈ 6 分鐘
F(并查集,树)G(网络流)Ex(概率论,数学)

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

F - Construct Highway

n 点, m边

问是否有方案 点i的连边数 = Di

所有点连成树

范围

n 2e5

2s

1024mb

我的思路

  1. 不成环
  2. 每个联通块->得到需要额外的度
  3. 贪心大的到小的连?

显然并查集先搞一搞

但不会实现如何后续的合并

题解

每次把节点大于1的和=1的连 !!!!!!!

直到剩余两个需求为1的块

证明 显然度需求1的肯定是和>1的连

那么假设 一个合法方案中1连的A, 任选一个度大于1的B

因为B度大于1,除了A…B路径外,肯定还连了一个块, 1-A-…-B-?, 那么 ?-A-…-B-1, 肯定也是一个合法方案

因此有合法方案, 任选的一个 >1的块, 依然有合法方案

代码

https://atcoder.jp/contests/abc239/submissions/34897350

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;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

int fa[200010];
int d[200010];
int getfa(int v) { return v == fa[v]?v:(fa[v] = getfa(fa[v]));}
vector<int> arr[200010];

int main(){
  int n = read();
  int m = read();
  rep(i,1,n+1) d[i] = read();
  iota(fa+1,fa+n+1,1);
  rep(i,0,m){
    int u = read();
    int v = read();
    d[u]--;
    d[v]--;
    int fu = getfa(u);
    int fv = getfa(v);
    if(fu == fv){
      printf("-1\n");
      return 0;
    }
    fa[fu] = fv;
  }
  rep(i,1,n+1){
    if(d[i] < 0){
      printf("-1\n");
      return 0;
    }
    int fi = getfa(i);
    rep(t,0,d[i]) arr[fi].push_back(i);
  }
  vector<int> e1; // equal 1
  vector<int> g1; // greater than 1
  rep(i,1,n+1) if(i == getfa(i)) {
    if(!arr[i].size()){
      printf("-1\n");
      return 0;
    }
    (arr[i].size() == 1?e1:g1).push_back(i);
  }

  vector<pair<int,int>>ans;
  while(e1.size() && g1.size()){
    int pj = g1.back();
    ans.push_back({arr[e1.back()].back(),arr[pj].back()});
    e1.pop_back();
    arr[pj].pop_back();
    if(arr[pj].size() == 1){ // 大于1变成等于1
      g1.pop_back();
      e1.push_back(pj);
    }
  }
  if(g1.size() || 2 != (int)e1.size()){
    printf("-1\n");
    return 0;
  }
  ans.push_back({arr[e1[0]].back(),arr[e1[1]].back()});
  for(auto[u,v]:ans) printf("%d %d\n",u,v);
  return 0;
}

G - Builder Takahashi

连通 无向 n点,m边

没有直接的1-n的边

点可能 空/有障碍, 初始都是空

A要从1走到n

而T要选择一些点建立障碍(A不可经过障碍),让A无法走到n

不能选1和n建立障碍, 每个点建立的代价ci

求最小建立代价,和具体方案

范围

n 100

无重边自环

ci [1,1e9]

c1=cn=0

2s

1024mb

我的思路

有点网络流求最小割的味道

感觉 每个点拆成in/out, 然后 点内就是代价, 点间就是无限大代价?

这样就可以了?

问题是这样,是能算出代价, 但如何求一组割边?

题解

和我想的一样 也是 拆点做

显然割边流量跑满

但是是通过残量网络里, 从源可达的点选出来作为割断边

1->2->3, 这种 1->2,2->3都可以是割边时, 那么只有1可达

而对于 1->2->3->4, 1->3 这种,跑满1,2,3,4的来说, 2->3是不能成为割边的, 所以需要满足的是 a可达而b不可达,则a->b是割边

代码

https://atcoder.jp/contests/abc239/submissions/34897775

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

ll INF = 0x3f3f3f3f3f3f3f3f;
int main(){
  int n = read();
  int m = read();
  auto g = atcoder::mf_graph<ll>(n*2);
  rep(i,0,m){ // edge id = [0..2*m-1]
    int u = read()-1;
    int v = read()-1;
    g.add_edge(u*2+1,v*2,INF);
    g.add_edge(v*2+1,u*2,INF);
  }
  rep(i,0,n) g.add_edge(i*2,i*2+1,read());// edge id = 2*m + i = [2*m..2*m+n-1]
  int S = 0*2+1;
  int T = (n-1)*2;
  ll c = g.flow(S,T);
  printf("%lld\n",c);
  auto cut = g.min_cut(S);
  vector<int> ans;
  rep(i,1,n-1) if(cut[i*2] && !cut[i*2+1]) ans.push_back(i+1);
  printf("%d\n",(int)ans.size());
  for(auto u:ans) printf("%d ",u);
  return 0;
}

Ex - Dice Product 2

snuke 有个骰子,上面1-n等概率

初始v=1

当v <= M时, 1~n等概率被选 v 乘上被选的值

求停止的期望次数

mod 1e9+7

范围

n,1e9

m,1e9

2s

1024mb

我的思路

惊了 atcoder竟然也有1e9+7

f(v) 表示从v开始,需要的期望次数

f(>m) = 0

f(v) = 1 + 1/n (f(v) + f(2v) + f(3v) + … + f(nv))

f(v) = n/(n-1) + 1/(n-1) (f(2v)+f(3v)+f(4v) +…+f(nv))

答案是f(1)

暴力似乎需要 O(m log(n)) 以上

但是注意到 (m/2,…,m] 都 = n/(n-1)

(m/3…m/2] 都 = n/(n-1) + 1/(n-1) * (n/(n-1))

(m/4…m/3] 都 = n/(n-1) + 1/(n-1) * (2n/(n-1))

似乎可以按照 (m/(i+1),m/i] 来分段

题解

emmm, 感觉概率论还是不会, 上面我这样也是对的吗?

g(x) = 当前值乘上 x 后 小于等于m 的期望次数

g(0) = 0

g(x) = 1+ 1/n(f(x/1)+f(x/2)+…+f(x/n))

g(x) = (n/(n-1)) (1+1/n(f(x/2)+f(x/3)+…+f(x/n)))

答案是 g(M)

啊 我看着好别扭啊

这里表达的应该是 g(x) = (v * x <=m )且(v * (x+1) > m) 的 v的期望次数

相当于我的f(1) = g(M), f(>M) = g(0)

v * x <= m, v * (x+1) > m

v * i * x <= m * i, v * i * (x+1) > m * i

v * i * (x/i) <= m , v * i * (x/i+1) > m (因为 a + 1 > b 则 a/b + 1 > 1

观察1

m/i 只有 O(sqrt(M)) 种, 易证(i=1..sqrt(M) 时 假设每个不一样, i=sqrt(M)..M 时 结果在[1..sqrt(M)]中, 因此 是sqrt M的量级

g(x) = (n/(n-1)) (1+ sum ( t(x,v) * g(v) )

其中v是 所有 m/i 的结果, t(x,v) 是它出现的次数

这样如果 子的计算完成了, 那么 g(x) 就可以再花sqrt(M)的完成计算了

观察2

m/i/j = m/(i * j)

这个也容易证明

可以想 i * j 的对整数分块, 后面的m/(ij) 就是问是在哪一块

而前面就是 i * j 的对整数分块,每块内再每i个一块, 后面的m/i 得到的就是 块号 * j + 块内的小块号, 再除j就只剩 块号了

这个还可以2推3 , m/i/j/k = m/(ijk)

因此 递归话只会有O(sqrt M) 个需要计算

观察3

f(M) 只需要 O(M^{3/4}) 即可算出

首先每个 一共需要算O(sqrt(M)) 个

f(x) 需要 O(sqrt(x))

sum (sqrt(M/[1..sqrt{M}]) ) (> sqrt M 部分) + sqrt{sqrt{M}} * sqrt{M} , (< sqrt M 部分)

int sqrt{M} 1/sqrt{x} dx , x= 1..sqrt{M}

= sqrt{M} 2(sqrt{sqrt{M}} - 1)

= M ^ {3/4}

代码

https://atcoder.jp/contests/abc239/submissions/34960041

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint1000000007;
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;}

mint low[40000]; // low[x] = f(x), // sqrt(1e9)
mint high[40000]; // high[x] = f(M/x)

int main() {
  int N = read();
  int M = read();
  ll L = llround(sqrt(M));
  ll K = M / (L + 1);
  rep(i,1,L+K+1){ // [1..L]:1..L,  [L+1...L+K] : M/K .. M/1
    int x = i <= L ? i : M / (L + K + 1 - i);
    mint sum = N;
    int l = 2;
    while(l <= min(N,x)){ // 暴力 f(x) = (n + f(x/2)+..+f(x/n))/(n-1)
      int q = x / l;
      int r = min(N, x / q) + 1; // x/[l..r) = q
      mint cur = q <= L ? low[q] : high[M / q];
      sum += cur * (r - l);
      l = r;
    }
    (i <= L ? low[i] : high[L + K + 1 - i]) = sum / (N - 1);
  }
  printf("%d\n",(M <= L ? low[M] : high[1]).val());
}

总结

F

又卡蓝题,不会数学,没有智慧

G

这个好像很久很久很久以前做USACO做过, 但好久都没求过割边集了, 现在拆点这些是会了, 这算又复习一下如何求割边集

Ex

概率论 每日自闭

学了收这样把乘和除法的转化(通过倒数? x => v/x), 没有悟到, 这样转化后, 似乎依赖的值不再像我的那样需要手工去判断 相同的是哪一段了, 鹅妹子嘤

数学完全不会

https://cplusplus.com/reference/cmath/llround/

参考

官方题解