2019-2020 ACM-ICPC Brazil Subregional Programming Contest(gym 102346)

来自PC Wiki
跳到导航 跳到搜索

Records

[Contest]

Solutions

A

判断从左下角到右上角能不能走到,我们只需要给点连线,判断左上角到右下角是否连通即可.

B

签到题

C

D

每次选择贡献最大的人,这个贪心是对的.

我们考虑贡献的修改,应该是若干个子树$$-1$$,注意到我们每次只需要对新抓到的人子树$$-1$$.

均摊一下复杂度是$$O(n \log n)$$

E

考虑有的箱子是把公的移走,母的不动同时做收集; 有的箱子是把母的移走,然后公的依次变性移走.

显然两种操作都需要做, 同时我们还需要考虑空箱子的影响.

于是$$\text{dp}[i][j][x][y]$$表示考虑前$$i$$个箱子, 遇到的空箱子数为$$j$$, 两种操作是否做了($$0/1$$).

然后动态规划转移即可.

F

二分答案之后套矩形面积并板子就行了

G

权值取对数把乘积变成和

按行-列建图,跑最大权匹配

H

签到题

I

按顺序加点Floyd

J

毫无技术含量的签到...

为啥过的人那么少= =,因为题目不短吗?

K

要求$$2 \times N$$的八连通哈密顿路计数

矩阵加速的线性递推.

我们考虑已知$$2 \times (N - 1)$$的某些情况,要求出$$2 \times N$$的某些情况

考虑了四种,即不妨假设新加入的两个点是$$A, B$$

  • $$A, B$$一个是起点,一个是终点
  • $$A, B$$既不是起点也不是终点
  • $$A, B$$一个是哈密顿路端点,另一个不是
    • $$A, B$$相邻
    • $$A, B$$中间隔了一个数

然后推系数转移即可.

L

这东西是个二项分布,考虑每一项$$\binom{n}{i}$$

为奇数就会剩一个,为偶数就不剩

那么我们统计有多少个$$i$$满足$$\binom{n}{i}$$为奇数

由lucas定理的推论,即(n&i)==i

那么我们计数n的子集就行了

这个东西就是统计一下$$n$$中的$$1$$的个数$$\text{cnt}$$,然后答案就是$$2^\text{cnt}$$

M

二分答案+check