2017-2018 ACM-ICPC Latin American Regional Programming Contest
ECNU Foreigners
Problem A
Solved by kblack. 03:24 (+2)
题意：一堆高度相同（有固定平行边）的凸多边形，要求找到最好的顺序把所有多边形卡在一起最短。
题解：枚举多边形对，从下到上判断边对之间卡在一起的距离，然后状压 DP 求最短的排列，搞一个 (0, 0) 到 (0, H) 的“多边形”后面写起来会方便点。
Problem B
Solved by kblack. 00:54 (+)
题意：一个 CodeBlocks，输入元音会导致已经输入的倒置，求输入指定串的方案数。
题解：发现多余一个元音的时候上一个输入的字符都是唯一的，只有最初的元音后面的辅音是可以有多解的，找到就好。
Problem C
Solved by zerol. 00:38 (+)
温暖的签到。
Problem D
Solved by zerol & ultmaster. 02:00 (+)
题意：数列染色，强制在线，支持区间染色和询问某种颜色的数量。
题解：由于颜色数众多，所以没法线段树。用 set 维护所有不相交区间的端点和颜色，同时数组维护每种颜色的出现次数，每次询问至多增加一个区间，对于与之相交的区间，进行删除或者切分。这题还可以分块做。
Problem E
Solved by ultmaster. 01:24 (+)
题意：一个数某些位置可以填，另一些位置不能动。求能被 $n$ 整除的最小值。
题解：数位 DP。反正很简单就是了。
Problem F
Solved by ultmaster. 00:29 (+1)
题意：二维最大权值上升子序列。
题解：随便怎么做。注意题目要读清楚。
Problem G
Solved by zerol. 02:15 (+)
题解：有树形的与非门组成的电路，有些门坏了，会一直输出 0 或 1，求有多少种不同的输入能使输出结果错误。
题解：树形 dp。状态 2×2，表示预测值和实际值分别为 0 或 1 的情况。
Problem H
Solved by kblack. 00:08 (+)
温暖的签到。
Problem I
Solved by zerol. 01:13 (+)
题意：询问强制选取某个边的最小生成树的值。
题解：经典题。建最小生成树，对于询问的边，答案就是 最小生成树的权 - 这条路径上权最大的边 + 这条边的权。用树上倍增维护会比较好写。
Problem J
Solved by ultmaster. 00:44 (+)
题意：求步长为 $k$ 的时候能否在剩余系中走通。
题解：只跟 gcd 有关。反正很简单就是了。
Problem K
Solved by kblack. 04:23 (+2)
题意：一个矩阵，四种图形，问能否用指定方式铺满。
题解：图形 $1$ 相当于他和四周有一个连接，图形 $2, 3, 4$ 相当于他和四周有两个连接，拆分成对应数量的点，和周围连边，跑二分图匹配就行了。
红色是实际匹配的边，蓝色是建了没匹配的边，绿色是对应的图形。
Problem L
Upsolved by zerol. (-1)
题意：给一个网格图，相邻的平行边之间的距离为 1 或 5，求两点间的最短路，要求每个路口必须拐弯。
题解：一通观察，乱搞。如果横向和纵向之间的格子数不一样就需要绕远路，最好是在 1 的地方绕，注意 1 的地方可能在起点和终点构成的矩形外侧。
zerol：赛后 4 分钟 AK 也是很酸爽的。
Problem M
Solved by ultmaster. 03:47 (+1)
题意：$k$ 个栈合并，使得合并后字典序最小。
题解：用一个堆维护就好了。比较两个栈应该要选哪个的时候要比较后缀的字典序大小。可以用个后缀数组之类的搞一下。实现的时候出了点奇怪的问题爆了 int（居然 WA 50？）
One,Two,Three,AK
Problem A
Unsolved.
Problem B
Solved by Xiejiadong. 01:13:59(+)
题意：求构成给定字符串的方案数，元音加在最后，然后倒置；辅音直接加。
题解：如果一个串全部都是元音或者辅音，那么方案数为$1$；如果有元音，而辅音在第一位，答案为$0$。
然后思考全部都是元音的时候，字符串是从里面向外面一层一层旋转出来的，推广到有元音和辅音混杂的情况，辅音只有在出现第二个元音之前可以通过和第一个元音的顺序调换来产生不同的方案，方案数量为$len_{辅音}+1$。
所以方案数就是最中间的一段$len_{辅音}+1$，如果是偶数段的话，是中间靠后段，可以模拟出来。
这样就产生了另一种特殊情况，元音在第一位，后面全部都是辅音的，方案数显然是$len_s$。
Problem C
Solved by dreamcloud. 01:03:15(+)
Problem D
Solved by dreamcloud. 4:34:54(+)
Problem E
Solved by dreamcloud. 3:12:52(+)
Problem F
Solved by dreamcloud. 00:44:53(+1)
Problem G
Solved by dreamcloud && Xiejiadong. 3:45:44(+)
题意：给出一个二叉树形状的只有与非门的数字电路图，某些元件只能输出确定的信号，求最后有多少信号是错误的。
题解：简单的树形dp，$f[i][x][y]$表示，到元件$x$为止，理应信号为$x$的，实际信号为$y$的方案数，dfs一下，暴力转移。
Problem H
Solved by Xiejiadong. 00:07:01(+)
温暖的签到，算个差就好了。
Problem I
Solved by Xiejiadong. 4:57:04(+3)
题意：每次询问一条边，求包含那条边的最小生成树代价。
题解：现在原图中把最小生成树建出来，如果询问的边属于最小生成树，那么显然，答案就是最小生成树的代价。
否则，我们把那条边在最小生成树上加上，会变成基环树，那找到那个环，在环上去掉除新加边以外的最大边即可。
可以发现，去掉的最大边，恰好是原来最小生成树中新加边的两点组成的链，由于是静态的，直接st表维护即可。
Problem J
Solved by dreamcloud. 1:52:59(+)
Problem K
Unsolved.
Problem L
Unsolved.
Problem M
Unsolved.