构造题自闭

摘要

鸽鸽给我们讲课啦

竞赛中有一类要求构造特定解的题,被称为构造题

构造题没有固定的套路,它要求选手对该领域知识有深层次的理解

URAL1979

对于一个 阶的魔方,要求把 的数填到每个格子里,每个数用一次。要求沿某一行或列走一圈的和恒定不变。输出方案数。

.

直接构造,每个格子的对面填上它的补数(加在一起是 的数)就行啦

CF226D

对于一个 的矩阵,每次可以选择某一行或者一列,将数字取相反数。输出一种方案使得每一行列的权值和非负。

.

注意到这道题不需要最优化,只需要输出方案,那么我们每次遇到和为负的行或列就直接取反就行了。

考虑这样做的正确性。每次取反,整个矩阵的元素的总和是增加的。而元素的绝对值是小于 100 的

因此一定有上界,那么多迭代几次就行啦

ASC44H

题目要求构造一组 huffman 编码。给出每一个编码的 01 个数,用二元组 表示,求是否能构造满足要求的 huffman 编码.

.

附上 CF 的 ASC 比赛集 https://codeforces.com/blog/entry/7770

首先要了解 huffman 树的某些性质。

根据它的构造过程,每一个结点(除了根结点)一定有兄弟结点.

因此,我们从最长的编码开始考虑,那么在这些编码中一定有兄弟编码,即 这样形式

那么我们就把这两个合并就行啦,相当于把末尾的 0/1 删掉,变成 就行啦

(具体的合并显然优先选择从最左的编码开始合并)

CF209C

把一个无向图加最少的边使得其包含欧拉回路。求方案数

.

欧拉回路的充要条件:图连通,每个点的度数都是偶数。

如果本来图就连通,就直接配对奇点连接;

如果不连通,就优先用奇点连通,即优先配对不同连通块的奇点


ZOJ3823

在一个 的方格走,要求只能四连通,起点终点在边界上,每个格子必须且只能走 1 次,而且总共至少拐 次弯。求方案

.

不要相信样例给的方案

p1.png

枚举几个例子,然后发现可以用 n-2 递推到 n。

奇偶方案略有区别

Latvia Contest14:G

a+b+c 是三角形数时有解

222,111 无解

贪心,每次倒着放最剩余多的

如果最后出现 111,222,那么找到某可选择和不可选择列,这两者的颜色一定不同,打个补丁即可

NEERC2013:K.

黑 xb= 白 xc

枚举黑点个数 n,白点 nb/c

黑点白点连边即可

考虑同色的点相连,要求每个点的度是一样的

图的度序列跑一遍即可


  转载请注明: Sshwy's Blog 构造题自闭

 上一篇
网络流建模 网络流建模
摘要 网络流算法本身不难,但是很多情况下难以被想到。其原因就在于网络流模型过于抽象,与表面的题目关联性不强。本文就从常见的建模角度,浅谈网络流建模 最大流建模魔术球问题 有 n 根柱子,现要按下述规则在这 n 根柱子中依次放入编号为 1,
2019.03.02
下一篇 
金华 DAY2 自闭 金华 DAY2 自闭
摘要 菜板:ZROI 改名 XYOI 完美理论Sutask1 暴力即可 Subtask2树形 DP 即可 STD枚举起始点 抽象出最大权闭合子图模型 模型: 将点分两种,正权和负权 正负之间的边容量为正无穷 考虑最小割的意义:正
2019.02.16
  目录