2014-2015 ACM-ICPC Southwestern Europe Regional Contest (SWERC 14)

https://odzkskevi.qnssl.com/727b6827e404fd453ff4858e2619c49c?v=1504751451

A - GREAT+SWERC=PORTO

全排列枚举。先将字母按照出现的顺序,重新编码为以$0$为开始值的数字,方便后续使用。然后构造一个排列数组$p$,长度为$10$,初始值$p[i] = i$。然后枚举$p$的全排列,$p[i]$的意义就是将数字(实质上是被重新编码后的字母)$i$以值$p[i]$来代替。假设有$cnt$个不同的字母,全排列我们枚举的却是$10$个数,每次只取前$cnt$个进行代替,那么最终的答案会重复计算$(10-cnt)!$次。进行暴力枚举并统计答案后,除以$(10-cnt)!$即可。

B - Flowery Trails

从起点和终点进行两次最短路。开一个$dis[2][i]$数组,分别表示从$0$点到$i$点的最短路、从$n-1$点到$i$点的最短路。要判断一条边是否在最短路上,可以枚举每一条$单向边$,假设这条边的两个端点分别为$u$和$v$,如果满足$dis[0][u] + len + dis[1][v] = dis[0][n-1]$,那么从$u->v$方向的这条边就在最短路上,应该纳入统计。这个题可能会卡SPFA,所以使用了堆优化的DIJ

C - Golf Bot

使用FFT进行计数。使用$cnt$数组记录每个值是否出现。将$cnt$数组和自己进行卷积后(假设为$A$数组),$A[i]$的意义就是任意选两个存在的数进行求和后,和值为$i$的方案数。再将$A$数组加回到$cnt$数组。$cnt[i]$是否为$0$,就代表是否有方案至多选两个数,至少选一个数的和为i。

D - Book Club

最大流求是否有合法方案

给出一些给书的关系,问是否有方案,使得每个人可以交出一本书,并且获得一本书,不能自己和自己玩。

将一个人$i$看作两个点,编号$A_i$和$B_i$。从源点引边到每一个$A_i$点,容量为1,表示$i$这个人要交出一本书。从每一个$B_i$引一条边到汇点,容量为1,表示$i$这个人要获得一本书。如果有一个关系,$i$的书可以给$j$,那么连一条边从$A_i$到$B_j$。最后跑最大流,如果流量为n,就满足要求。

G - Playing With Geometry

离散化,坐标旋转。

给定两个图,以转角坐标的方式逆时针给出,问两个图的轮廓是否相似。允许进行压缩或者旋转。

直接将两个图的横纵坐标进行离散化(压缩)。枚举将第一图进行旋转,和第二个图进行匹配,匹配的时候,需要找到两张图最左下角的点,让后从这个点开始,逆时针匹配。如果每个坐标都是相同的,那么就是OK的。

I - The Safe Secret

循环枚举,区间DP

给一个由数字和运算符号组成的序列,长度为$2*n$运算符号只包含+-*和?,?可以任意替换为+-*。枚举将序列向左进行循环位移,每次位移$2$个单位,可以得到$n$个表达式序列,问这$n$个表达式的值的最小值和最大值的绝对值。

先将原始序列的数字和符号进行分离。再分别复制一份后接到后面。这样就可以进行区间dp了。注意,第i个数字就是$num[i]$了,它后面的符号就是$symbol[i]$。用$mx[i][j]$来表示从第$i$个数字到第$j$个数字组成的子区间的表达式的最大值,$mi[i][j]$表示最小值。初始化$mx[i][i] = mi[i][i] = num[i]$。枚举区间长度,枚举区间起点,再枚举区间内的断点,进行转移即可。要注意断点处为乘号的时候,并不是最小值*最小值就是最小值(考虑两个都是负数的情况),为了偷懒,直接暴力枚举了4种情况进行转移。

最后mx[i][n+i-1]和mi[i][n+i-1]就是第i个序列的表达式的最大值和最小值