SDUT - 2017年寒假集训 阶段测试赛3(组队)解题报告


比赛 ID: 2015

注:本题解参考代码均为 C++ 代码,如果你是 C 使用者,出现不认识的头文件时,若是 c 开头的,一般可以通过去掉开头的 c 然后在末尾添加 .h 来转换成 C 的头文件,如 cstdio 在 C 中为 stdio.h ,其他的请自行搜索。另外,如果出现不认识的写法,如 sort(排序)stack(栈) 等,请自行实现。


SDUT - 2017年寒假集训 阶段测试赛3(个人)解题报告


比赛 ID: 2016

注:本题解参考代码均为 C++ 代码,如果你是 C 使用者,出现不认识的头文件时,若是 c 开头的,一般可以通过去掉开头的 c 然后在末尾添加 .h 来转换成 C 的头文件,如 cstdio 在 C 中为 stdio.h ,其他的请自行搜索。另外,如果出现不认识的写法,如 sort(排序)stack(栈) 等,请自行实现。


ZOJ 3777 Problem Arrangement(状压 DP)解题报告


解题思路

不难想到用 $dp[i][j]$ 表示放第 $i$ 个题时趣味值为 $j$ 的方案数,然而有一个问题是不好表示前面 $i-1$ 个都选了哪些。因此这里需要用状态压缩 DP(一看题目数量那么小就应该试图往状压那边想了),把我们的 dp 数组中的第一维表示为一种题目选择方案(按二进制压缩成一个数存储),然后就很容易写出转移方程(其中 $i$ 表示当前遍历到的状态,$j$ 和 $k$ 分别为 $[1, n]$ 及 $[0, m]$ 的循环,$cnt$ 为当前状态下的已选题目数量):

$$dp[i+2^{j-1}][min(k+a[cnt+1][j], m)] += dp[i][k]$$


POJ 2135 Farm Tour(最小费用最大流)解题报告


解题思路

使用费用流求解。首先把题中所有的边都按流量为 1,费用为路径长度加边,这样就保证了每条路只能走一次,且求出来的最小费用就是最短路径长度。之后再把源点到 1 以及 n 到汇点都加一条流量为 2,费用为 0 的边,这是为了支持题目中的往返操作。这样跑一边最小费用最大流即可求出答案。