Atcoder abc221

發表於 更新於 分類於 ， Disqus： 文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘
F(树的直径)G(坐标转化,笛卡尔系)H(差分转化,前缀和,滑窗和,动态规划)

F - Diameter set

https://atcoder.jp/contests/abc221/tasks/abc221_f

N 点树, 找染色法, 染>=2个点为红色,让红色点两两之间距离为直径

方案数 mod 998244353

范围

N 2e5

2s

1024mb

我的思路

首先直径 是经典算法, 随机点u,找最远点v, 再以v找最远点 便是直径

如果选v

那么可以把v看作根, 相当于做树上dp

因为有深度和直径都知道, 那么对于到叶子距离2倍小于直径的分叉至多选一个,

而2倍大于直径的分叉(不可能都有直径,否则这样能得到更大的长度)

如果直径是偶数, 那么从v到1/2直径点u再到最远点, 这样的点u只有一个,并且这个u可以看成重心

因此可以从重心去找 直径/2 的距离做树上统计 即可

问题来到了奇数长度的直径, 如果直径是奇数, 选了v到最远点的方案 就是最远点的个数

任意两个直径 必有交点, 否则 两个直径上 p1..p2 有一个简单路径 取 p1 — 最远, p2 — 最远, p1-p2, 大于等于 直径/2向上取整 + 1

这样的话

任取一条来看,

v …. x - y…..t

假设,x和y是中间距离的两个点

那么不可能有不经过y的v..x…t1, 否则 t..x..t1 更长

换句话说

一定所有直径有x-y

类似的证明

已经证明了有公共点,

那么假设是y右侧的最近的某个p

同样v ….p…更长的一半, 将会比直径长

x对称同理

所以奇数情况,就是, x 去找距离的方案 乘上 y 去找距离的方案

似乎就推出来了?

代码

https://atcoder.jp/contests/abc221/submissions/33847992

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

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define pb push_back

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

vector<int> p2[200010];

// {distance, node}
pair<int,int> dfs(int u,int fa,int d = 0){
  pair<int,int> r = {d ,u};
  for(auto v:p2[u]) if(v != fa) r = max(r, dfs(v,u,d +1));
  return r;
}
int D = 0;

bool dfsxy(int u,int fa,int findv,int &x,int &y,int d = 0){
  bool ok = u == findv;
  for(auto v:p2[u]) if(v!=fa) ok = ok || dfsxy(v,u,findv,x,y,d+1);
  if(ok && d == D/2) x = u;
  if(ok && d == D/2 + 1) y = u;
  return ok;
}

int dfscnt(int u,int fa,int d){
  int r = d==0;
  for(auto v:p2[u])if(v!=fa) r += dfscnt(v,u,d-1);
  return r;
}

int main(){
  int n = read();
  rep(i,1,n){
    int u = read();
    int v = read();
    p2[u].pb(v);
    p2[v].pb(u);
  }
  auto [_,u] = dfs(1,0);
  auto [d,v] = dfs(u,0);
  D = d;
  int x,y; // x: d/2, y: d/2+1
  dfsxy(u,0,v,x,y);
  if(d % 2){ // 奇数长度
    ll cx = dfscnt(x,y,D/2);
    ll cy = dfscnt(y,x,D/2);
    printf("%lld\n",cx*cy % MOD);
  }else{ // 偶数长度
    ll s = 1;
    ll r = 1;
    for(auto p:p2[x]){
      ll c = dfscnt(p,x,D/2-1);
      (r*=(c+1))%=MOD;
      s += c;
    }
    printf("%lld\n",(r+MOD-s)%MOD);
  }
  return 0;
}

G - Jumping sequence

https://atcoder.jp/contests/abc221/tasks/abc221_g

能否从(0,0) 恰好N次,跳到(A,B)

第i次可以向, x正/x负/y正/y负(4选1),跳恰好Di

如果可以,给一个方案

范围

N 2000

A,B [-3.6e6,3.6e6]

Di 1800

5s

1024

我的思路

顺序其实没有关系,因为是向量加和

那一个角度转化就是

分成4组,

其中两组的差 = X

另外两组的差 = Y

另一个就是

先分两组 组A-组B = X+Y

然后找到组A中部分 = Y的 移出来

但这个只是 充分条件不是必要条件

题解

逆时针转45度坐标轴 长度再乘上 根号2

终点 原坐标系(a,b) -> 新坐标系 (a-b,a+b)

操作 全变成了(+-di,+-di)的形式

什么好处呢, 两个轴单独考虑了

对于一个轴, 要找

S = sum (1/-1) * di

的方案

可以同时加 所有di的和

S + sum di = sum (2/0) * di = 2 * (选一些di)

就是简单的01 背包,需要bitset搞一下 空间

代码

https://atcoder.jp/contests/abc221/submissions/33849395

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
#include <bits/stdc++.h>
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;)
#define pb push_back

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

bitset<3600001> dp[2001]; // bitset 压空间, dp[前i个][值] = 是否可达
int d[2000];
// 旋转矩阵: 逆时针 45度 * 根号2
// (x y) ( 1  1) => (x-y, x+y)
//       (-1  1)
//                                     x y   y   x
// L: (-1 0) => (-1 -1)  =>  +1)/2 => (0,0)  0 + 0 =  0
// D: (0 -1) => ( 1 -1)  =>  +1)/2 => (1,0)  0 + 1 =  1
// U: (0  1) => (-1  1)  =>  +1)/2 => (0,1) 10 + 0 = 10
// R: (1  0) => ( 1  1)  =>  +1)/2 => (1,1) 10 + 1 = 11
const char c[] = { 'L','D','U','R'};
char ans[2010];

bool w(){
  int n = read();
  int x = read();
  int y = read();
  int m[2] = {x-y,x+y};
  int s = 0;
  rep(i,0, n) {
    d[i] = read(); // [1,1800]
    s += d[i];
  }
  rep(i,0,2) if(abs(m[i]) > s) return false; // 过远
  rep(i,0,2) if((m[i] + s) % 2 != 0) return false; // (m[i] + s )/2 = 选部分di
  rep(i,0,2) m[i] = (m[i] + s) / 2;
  dp[0][0] = true;
  rep(i,0, 2000) dp[i + 1] = dp[i] | (dp[i] << d[i]); // 哇
  rep(j,0,2) if(!dp[n][m[j]]) return false; // 有值无法构成
  per(i,0,n){ // 倒着找哪些用了哪些没用
    int bit = 0;
    rep(j,0,2) if (!dp[i][m[j]]) { // 表示可达, 直接贪心选取, 两个中必有一个可行,一个不可行另一个一定可行
      m[j] -= d[i];
      bit += (1 << j);
    }
    ans[i] = c[bit];
  }
  return true;
}

int main() {
  if(!w()) printf("No\n");
  else {
    printf("Yes\n");
    printf("%s\n",ans);
  }
  return 0;
}

H - Count Multiset

https://atcoder.jp/contests/abc221/tasks/abc221_h

输入正整数 N, M

找可重集合,k=1…N个正整数, 和=N, 同一个重复数量不超过M, 这样可重集合的个数

mod 998244353

对于k=1..N 分别输出答案

范围

M <= N <= 5000

2 s

1024 mb

我的思路

5000 很想平方

但是直接之想到3维dp

dp[v][x][c] = 和 = v, 最大值不超过v, 一共用了c个数 的方案数

转移

dp[v][x][c] = sum dp[v-kx][x-1][c-k], k=0..m

这样$N^3$的状态, 转移还要枚举k(可以跳点双指针变成O1均摊), 虽然滚动可以吃掉一维解决空间,还是无法解决时间

但是从加和的角度可以看成二维卷积 一个稀疏的[k][1] * 0..m

题解

显然 等于 非严格递增序列的方案数(其实上面dp就是按照这个来的

令B为其差分数组,其中B1=A1, Bi = Ai-A[i-1]

sum Ai = N

sum Bi * (k-1+i) = N

考虑翻转顺序

sum i Bi = N

然后限制是最多M个Ai, 也就是连续0的个数 <= M-1 < M

这里的好处就是把M限制变成了连续0的限制,不影响总和,而非0的内容是任意的数量,没有限制

f[i][j] = B中前i个数和为j 且最后一个数不为0的方案数

$f_{i,j}=\sum\limits_{k=\max(0,i-m)}^{i-1}\sum\limits_{l = ik < j} f_{k,j-l}$

初始状态f[0][0] = 1, f[0][>0] = 0

滑窗和/前缀和优化一下就n^2了

注意到颠倒了i以后正好我们要的就是首个不为0,变成末尾不为零

因此f[i][n] 就是要求的k=i的答案

代码

https://atcoder.jp/contests/abc221/submissions/33848661

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

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

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

const int N = 5000;
ll f[N+10][N+10]; // f[i][j] = 前i个(第i个不为0), sum(i*Bi) = j 方案数
ll sum[N+10][N+10]; // sum[i][j] = sum f[i-m+1..i][j], 对i维度的滑窗和(也可以前缀和)

int main() {
  int n = read();
  int m = read();
  f[0][0] = sum[0][0] = 1;
  rep(i,1,n+1) rep(j,0,n+1) {
    // f[i][j] = sum f[i-m ~ i-1][j - i * bi] ,  k = bi * i, O(log)
    for(int k = i; k <= j; k+=i) (f[i][j] += sum[i-1][j-k]) %= MOD;
    sum[i][j] = (sum[i-1][j] + f[i][j] - (i-m>=0?f[i-m][j]:0)) % MOD; // 长度m的滑窗
  }
  rep(i,1,n+1) printf("%lld\n", (f[i][n] + MOD) % MOD);
  return 0;
}

总结

F

没啥难的

先知道基本的直径算法, 也是可以自己推的

G

分离相关性

坐标轴转化

据说有黑科技 能55ms Linear Time Algorithms for Knapsack Problems with Bounded Weights

https://www.sciencedirect.com/science/article/abs/pii/S0196677499910349

H

差分转化!!!

这里的好处就是把M限制变成了连续0的限制,不影响总和,而非0的内容是任意的数量,没有个数限制

只有对于首个非零和连续0的个数的限制了

然后是bitset的熟练应用了, 甚至位运算做01背包转移

参考

官方题解