Atcoder abc259

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
G(网络流)H/Ex(分块,讨论)

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

G - Grid Card Game

题目

HxW的数阵

选择任意的一些行和一些列, 让被选到的所有格子的和最大(同时被行和列选只统计一次)

且 限制条件,如果格子上的值为负那么 不能同时选它的行和列

范围

H,W [1,100]

Aij [-1e9,+1e9]

2s

1024mb

题解

我的思路

显然 纯非负的行和列一定被选,

所以可以预处理让剩下的所有行列至少包含一个负数

然后考虑说纯选行或选列

但是显然有反例

1
2
3
  1     -1    100
 -1      1 -10000
100 -10000      1

这种情况 最优的是选1行和1列

然后另一个性质是, 显然 和为非正的行和列不会被选, 因为 如果即选了行又选了列,重叠部分非负 两个都选的和是 小于 两个分别的和的

然后没思路了

题解

首先我们令 结果 = 全部正值 都被选了, 考虑变化对结果的影响

  1. 如果一个正的没有被选, 那么它的行列没有直接被选, -Aij
  2. 如果一个负值被选了, 那么它的行和列有一个被选, Aij

如果 Aij < 0 被选了,

  • 如果是行被选, 那么 影响的是 加上 i行的所有负数

  • 如果是列被选, 那么 影响的是 加上 j列的所有负数

于是改变题目

初始分 = 正数和

那么如果 选了i行, 则 损失 i行的所有负值的和

那么如果 选了j列, 则 损失 j列的所有负值的和

对于正的单元没被选的 损失上面值的代价

对于负的单元, 不恩那个同时选行和列

答案 = 正数和 减去 下面网络流的最小割

点:

R[1..H]

C[1..W]

源S,汇T

边:

S->R[i], 容量 行i的所有负值和的绝对值

C[j]->T, 容量 行j的所有负值和的绝对值

R[i] -> C[j] 如果是 Aij > 0, 则 权重 Aij

C[j] -> R[i] 如果是 Aij < 0, 则 权重 无限大

这样考虑

对于 Aij > 0

S->R[i]->C[j]->T 在最小割中, 至少有一条边被割(说至少是因为, 可能 R和T一个集合,S和C一个集合)

对 Aij < 0

也就是最小割一定不会同时割S->R[i],和C[j]->T, 因为如果这样割了

意味着, S,C[j] 是一个集合,R[i],T是一个集合, 就有 C[j] -> R[i] 的无限大, 就不会是最小割了

对于Aij < 0 一定是 S->R[i] 或 C[j]->T, 表示

也就是对于Aij < 0, 至多一个成为割边

然后最小割 = 最大流 Dinic, 或者直接调用官方的maxflow

代码

https://atcoder.jp/contests/abc259/submissions/33171094

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
#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++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;
int m;
const int N = 100;

const ll inf = 0x3f3f3f3f3f3f3f3f;
int h, w; // 输入
ll a[N+10][N+10]; // 输入
ll rsum[N+10], csum[N+10]; // 行列负数绝对值和

int main() {
  h = read();
  w = read();
  rep(i,1,h+1){
    rep(j,1,w+1) a[i][j] = read();
  }
  atcoder::mf_graph<ll> g(h+w+2); // 传入点数
  int S = 0; // 源
  int T = h+w+1; // 汇
  ll ans = 0;
  rep(i,1,h+1){
    rep(j,1,w+1){
      if(a[i][j] >= 0){
        ans += a[i][j];
        g.add_edge(i, h+j, a[i][j]); // R[i] -> C[j], a[i][j]
      } else {
        g.add_edge(h+j, i, inf); // C[j] -> R[i], inf
        rsum[i] += -a[i][j];
        csum[j] += -a[i][j];
      }
    }
  }
  rep(i,1,h+1) g.add_edge(S, i, rsum[i]); // S -> R[i], 行负数和的绝对值
  rep(j,1,w+1) g.add_edge(h+j, T, csum[j]); // C[j] -> T, 列负数和的绝对值
  printf("%lld\n", ans - g.flow(S, T));
  return 0;
}

H/Ex - Yet Another Path Counting

NxN的矩阵

每次向右或向下走

问有多少种路径,头和尾所在位置的数字相同

范围

n 400

aij [1,N^2]

2s

1024 MB

题解

我的思路

最朴素就是 对不同值分开处理,直接变成 每个值=> 所有位置

然后 (i0,j0) => (i1,j1) 就是组合数

问题是, 如果一个一算,是(N^4)的样子会TLE

考虑是否有办法把结果变成统计合并

题解

分块

更朴素的纯色+dp是, O(n^2)的

所以对于每个颜色根据个数来做不同处理

如果当前颜色点个数 <= n

显然用我的思路里两两去算, 复杂度不超过O(个数^2),这一类的总复杂度小于O(sum{个数^2}) <= O(sum{n * 个数})<= O(n * sum{个数}) <= O(n^3)

如果当前颜色个数 > n , 那就直接dp,也不超过O(n^2), 而这种最多n种颜色最多O(n^3)

综上

都在n^3内

代码

https://atcoder.jp/contests/abc259/submissions/35946797

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint=atcoder::modint998244353;
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 a[410][410];
vector<pair<int,int>>b[160010];//value->{i,j}
mint c[410][410];
int main() {
  int n=read();
  rep(i,0,n)rep(j,0,n)b[a[i][j]=read()].push_back({i,j});
  rep(i,0,n)c[0][i]=c[i][0]=1;
  rep(i,1,n)rep(j,1,n)c[i][j]=c[i-1][j]+c[i][j-1];
  mint s=0;
  rep(k,1,n*n+1){//kolour
    if((int)size(b[k])<=n){//点少枚举点对
      for(auto[x0,y0]:b[k])for(auto[x1,y1]:b[k])if(x0<=x1&&y0<=y1)s+=c[x1-x0][y1-y0];
    } else{//点多二维dp
      auto t=vector(n,vector<mint>(n,0));
      rep(i,0,n)rep(j,0,n){
        t[i][j]=(i?t[i-1][j]:0)+(j?t[i][j-1]:0)+(a[i][j]==k);
        if(a[i][j]==k)s+=t[i][j];
      }
    }
  }
  printf("%d\n",s.val());
  return 0;
}

总结

G

感觉 完全对网络流类型不熟,即使看了答案也仅是证明, 感觉没有系统的练习相关的建图, 还是不知道从何而起

这里相当于网络流求的是尽可能删除得小的, 利用了 最小割 = 最大流 , 这也是一个点,要求最小值的时候可以考虑让图能含义到最小割

然后就是atcoder内置的maxflow真香啊

Ex

有一说一感觉比G简单

这个分类的第一个复杂度上限推导还是很有意思,有点像之前树上左右部分平方的dp总复杂度是n3不是n4的感觉

参考

官方题解

https://www.bilibili.com/video/BV1KW4y1S7NA