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

G - Game on Tree 3

n点,1为根的树

除了根,点i上面还有值Ai

棋子初始在1

1. 乙 选一个非根点,修改值Ai = 0
2. 甲 把棋子移动到当前所在的一个子节点上, 随时可以结束游戏

移动到叶子后结束

分数=结束游戏时棋子所在位置的值

甲要让分尽量大, 乙要让分尽量小

求分

范围

n 2e5

ai 1e9

6s

1024mb

我的思路

一眼感觉树上dp, 因为乙要让分尽量小, 所以每次乙一定操作的是当前所在的剩余树上的点

但感觉不一定操作最近的

比如

1
2
3

         0
   1         1 
100 100     100

那么,最大答案是1, 乙第一次移动的是左边某个叶子的100, 因为如果不是这样, 那么甲向左走,可以得到>=100 > 1

没啥想法对于局部性, dp[i][j] = 点i为根的树已经删了j个点后剩余能得到的最大值, 但转移和范围 感觉都没想法

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)

有办法容斥出来吗?