「CF1242X」Codeforces Round #599 (Div. 1)

2019年11月8日4,0410

A. Tile Painting

对 n 做因式分解,如果 n 有超过一个质因数 t,则答案是 1,否则答案是 t。

因为两个质因数求 gcd 以后是 1,则 ax + by 可以把所有格子染上。

B. 0-1 MST

求补图的联通块个数,BZOJ 1098 原题。

维护一个 1 – n 的链表,表示有哪些点还没确定所在连通块。

从 1 – n 枚举点 x,用 bfs 把与 x 同一连通块的点找出来,每次 bfs 只需要考虑还在链表里的点,这样每一条边要不然在原图中,要不然不在原图中使得某个点的连通块确定,则复杂度不超过 n + m。

C. Sum Balance

所有数字互不相同这一性质,保证每个数字都确定了一个所在的箱子。

如果我们从第一个箱子里拿出一个数,为了达到目标总和,需要补一个差值,把它从某个箱子里拿过来,接着就要考虑被拿出数的箱子,这样会形成一个置换的环。

即拿出某个数字,会推导出一个一些箱子的环。现在的问题是,能不能选若干个环,使得某个箱子恰好在一个环上。

考虑 n <= 15,第二步就用状压 dp 来解决,预处理是 O(n * k^2) 的,枚举子集 O(3^k)

avatar
  Subscribe  
提醒