只写我会的、B以后的。
为什么要写到019呢，因为Contest的第三版的最后一个AGC就是019。
## AGC016
### B
### C
### D
### E
### F
## AGC017
### B
### C
### D
### E
### F
题意：给定一个$n$行三角形，$m$条线，每条线每一次向下可以选择向左或者向右走，共$n-1$次。
第$i$条一定在$i+1$的左边（可重合），此外还有$k$个限制，表示第$i$条直线在第$j$次向下只能向$k$方向走($k=0$←,$k=1$→)，求总的方案数。$n,m\le 20,k\le m(n-1)$
这题虽然的确很神，但是$doe$~~狗~~对我的误导极大地增加了我理解的难度。
首先我们考虑一个比较显然的DP，设$dp[i][S]$表示前$i$条直线，第$i$条直线的移动是$S$的方案数。枚举$\le ^* S $的$(i-1,T)$状态进行转移。
$^* T\le S$指的是对于一个二进制数$T$的从小到大每一位的$1$的前缀和都不大于$S$。
你可以画一下图，发现这样转移是正确的。复杂度是$O(n4^n)$。
发现无论怎么样确认这样形式的转移都很难，只能换个思路。
设$dp[i][j][S]$表示表示前$i$条直线，第$i$条直线的前$j$次移动是$S$的前$j$位，第$i-1$条直线的后$n-j$次移动是$S$的后$n-j$位的方案数。这个定义的意义是，第$i$条直线后面至少能走哪里，也就是一个限制。
假设第$i$条直线第$j+1$次方向为$x$。
考虑如果$S[j+1]=1$，$x=0$不合法。
若$x=S[j+1]$，那么直接复制当前的状态过去就可以了。
若$x=1,S[j+1]=0$，那么意味着这条直线在之后的路上实际上可以有的选择变多了，也就是说，$S$给予的某个限制可以解除了。
那么怎样才能使限制删得正确呢？实际上就是删除离$j+1$最近的下一个$1$，显然这样删除限制的话，转移才是合法的，才能保证构成尽量多的方案。找下一个$1$可以直接$\rm lowbit$，也可以$O(n2^n)$预处理。
于是我们就可以转移到把这个限制删掉的新状态$S'$。
最后还有一个其实已经不太重要的问题，那就是题目给出的限制。
这个处理实际上比较简单，你只要判一下当前选择的方向$x$满不满足要求就可以了，直接弄个数组存当前的限制即可，注意这个数组初始化成$-1$或是什么其它的不是$01$的值。
于是这题就在$O(n^22^n)$的时间内做完了。实现上的差异貌似非常大，导致常数可以千变万化，尽管理论复杂度是$4s$，但$\rm whzzt$的代码最慢只有$121ms$，简直神仙。
## AGC018
### B
### C
### D
### E
### F
题意：给定两棵树，相同编号的点要填相同的权值。构造一组权值方案，使得每个点的子树权值和的绝对值为1。
比较神，~~更神的是$doe$把这题出到了$NOIp$模拟题里~~。
首先考虑如何判断是否能够构造。注意到由于每个点都要满足这个限制，那么对于任意一个点，如果它在两棵树下儿子的数量的奇偶性不同，那显然是构造不出合法解的。除此之外，~~应该~~可以证明一定有一种$val_i\in\{-1,0,1\}$的填法。
如果一个点有奇数个儿子，那么这个点可以填$0$。显然（?）可以利用它的儿子们构造出合法解。
**引理1：每棵子树都有奇数个权值为奇数的点。**
证明比较显然，因为这棵子树的权值和是奇数。
利用这个，我们对这$2k+1$个点配对，这样配出$k$对，每对里面的两个数分别填上$1,-1$，最后剩下那个点填$1,-1$都可。
**引理2：用上述方法每一对的两个点之间连边，对两棵树进行操作之后，得到的图一定是个二分图。**
证明也很简单，我们考虑如果出现奇环那么一定是在一棵树内出现了一个点向两个点都有连边的情况，这显然与我们的连边方式不符，那么结论成立。
那么我们直接进行黑白染色就可以了，对二分图的两边分别填$1,-1$，于是就能在$O(n+m)$的复杂度内得出一组合法解。
## AGC019
B
C
D
E
F