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

G - Foreign Friends

N个点, 第i个人颜色是Ki

其中一些点是好的点

初始没有边

有m个可选边, 第i个可以花费 Ci 让ui和vi连一条边(无重边自环)

对于每个点, 独立的求最小代价 让它和一个异色好点连通, 或报告不可能

范围

N 1e5

M 1e5

我的思路

既然是每个到异色好点最短距离, 那么路径上一定都是同色或非好点

目前思路是 按一个颜色的个数能不能根号分治

另一个是记录到每个点最小代价不同色的两个最近点

考虑用Floyd+提前退出? 问题是 时间复杂度怎么估计和保证

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

G - Construct Good Path

n点m边 简单无向连通图.

边长=点数

构造一条 长度小于4N的边, 让点i出现次数%2 == s[i]

范围

n 1e5

m 1e5

2s

1024mb

我的思路

说是图, 但是树也是图, 所以树应该也可以, 所以 先从图中随便提出个树再在树上做

显然树上有个不满足个数的方案

根到点再返回根, 这样走完所有再决定 根需要奇数次还是偶数次

但这样搞次数肯定超了

考虑树上两种,一个是成链,一个是分叉

链上 a-b-c-d-e-f-g-h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

abcdefgh
xxxxxxxx
      x
     x
      x
     x
    x  
   x
    x
   x
  x
 x
  x
 x
x

然后是分叉, 考虑分叉= 多个链合并起来, 主要关注一下合并处的奇偶

1
2
3
4
5

 a
 b
 c
d f 
e g

可以看成a b c d e 和 c f g 两条链

c的奇偶性 = 原来c的奇偶性 + 1(额外链数)

似乎就没了, 因为新增的链 对 链头的重复可以看成链尾上多一次,这样每个点次数不超过4, 最后判断根要奇还是偶即可

但是感觉好难写啊

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

Ex - Builder Takahashi (Enhanced version)

给定S,G,O,. 组成的高h,宽w的矩阵, 其中S和G分别出现且仅出现一次

S起点

G终点

.可以建墙

O不可建墙

四临移动

问

1. 最少建立多少墙可以让无法从S到G
2. 满足最少墙时的方案数 mod 998244353

范围

h [2,100]

w [2,100]

4s

1024mb

我的思路

首先想到的是 直接建一个竖着或这横着的, 这样隔开就行了

又想到, 直接把起点或者终点围起来

那么问题就是能不能围住

那么先不管多少, 就把所有能建的全建立完, 那能走的只有4临可达的不能建的

所以判断能否很好判断

那么就是 最小代价的围

感觉不会超过100

但想了下要是能建立的是个蛇形, 那还是会很长接近平方

反正问题变成平面上一堆4临连在一起的S, 和一堆4临连在一起的G

要画圈/线 把两堆隔开, 然后有些不能画线的地方

1
2
3
4
5
6
7

  sss
    s
xxx s
    s
  sss

注意到虽然 不能画的x与s不相连, 但是依然可能影响围住s的大小

没啥想法, 感觉直接围起来 保证不了最小

1
2
3
4
5
6
7
8
9

sss
s
s
sss
s
s
sss

如果围完以后, 找 两点最短更新,需要保证包裹住

需要A星 一类的启发式吗?

但如果上了启发 后面统计又不太行了

甚至可能包裹和 隔断等价

1
2
3
4
5
6

           g
           g
ss         g
ss         g
           g
           g

没有头绪

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

F - Black and White Rooks

n行,m列

放b 个黑色,w个白色, 求任意黑 不与 白同行/同列 的 放法 mod 998244353

范围

n,m 50

b,w 2500

2s 1024

我的思路

emmm 如果能算出 放b个黑色后, 还有x位置可以放白色, 那么就是 binom(x,w)

然后当然不能枚举

所以考虑说 放了b个后, 剩余有x个位置可以放白色 有多少种方案

一个想法是插头dp, 做一个横切折线, dp[折线][已放黑色个数][折线以上的可放白色位置数] = 方案数

每个状态 O(1) 转移

但问题是 2^n n n^2, 显然没法搞

考虑交换行列, 把 黑色的平移交换到一块

则考虑黑色铺的占了 i0行j0列, 白色占了i1行j1列 的方案, 并且注意到行列看似有关系,但行与行交换不影响列的个数

最后乘上 binom(n,i0,i1) * binom(m,j0,j1)

问题是 直接行列的个数描述也可能多种

1
2

x0
0x

和

1
2

0x
x0

行列 都是(1,1)

dp[i][mask][j] = 前i行用了j个, 列占用情况是mask 的方案数, 依然状态就 n^3 2^n,

f(i,j,c) = 一共铺了(<=i,<=j) 的方案数 = binom(i * j, c)

有办法容斥出来吗?

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

G - Round Robin

n 个人

两两之间打比赛

已知 已经结束了m场,每场wi赢,li输

问 如果所有比赛结束后 可能成为赢得比其它人都多的可能的id有哪些?

范围

n 50

2s

1024mb

我的思路

如果一个人目前全胜,那当然可能

那如果一个人输过,那么可能是比其他所有人多吗?

显然是 n(n-1)/2 场比赛, 那么有n(n-1)/2个胜场, n(n-1)/2个负场

如果最多的t场,其它最多t-1场, t + (t-1)(n-1) >= n(n-1)/2

t >= (n-1)(n+2)/2n = (n-1)(1/2+1/n)

看起来似乎不一定要全胜

试一试

1
2
3
4
5
6

 12345
1 yyyx
2x yxy
3xx yy
4xyx y
5yxxx

这样的话 1胜3也是胜最多的

看数据量n 50, n(n-1)/2 = 1225

看起来能接受n^4

既然只讨论可能性, 那么不妨直接贪心这个人赢得最多, 得到他赢的次数t

那么变成剩下的点组成的图,能否让最大胜利次数 < t

感觉dp点或者dp边, 都不知道怎么处理互相关联的问题, 怎么做局部性

以及另外一个问题是, 如果剩下的点没有边已经确定,那么最小的胜利局数是怎么 去分配边

毫无头绪