XIII Open Cup named after E.V. Pankratiev. GP of SPb

时间:2021-07-23 14:34:47

A. Graph Coloring

答案为$1$很好判,为$2$只需要二分图染色,对于$3$,首先爆搜哪些边要染成第$3$种颜色,然后二分图染色判定即可。

B. Decimal Fraction

枚举前缀,那么只需要求出后面部分的最小循环节即可,将串翻转之后进行KMP,循环节长度$=i-next[i]$。

时间复杂度$O(n)$。

C. Teams of Equal Power

首先将球员按能力值从大到小排序,假设一队的队长能力值比二队队长高,那么显然一队队长只能是第一个人,枚举二队队长,然后看看后面是否存在合法方案即可。

判断合法,可以设$f[i][j]$表示用$[i,n]$这些人能否组成能力值之和为$j$的队伍,可以用bitset加速。

时间复杂度$O(\frac{n^3}{64})$。

D. Hexagon

轮廓线DP,设$f[i][j][S]$表示考虑到$(i,j)$这个三角形,轮廓线上的匹配情况为$S$的方案数,然后打表即可,注意去掉冗余的状态。

E. Maximal Matching

建图:$S$向左边每个点连边,费用为点权,流量为$1$;右边每个点向$T$连边,费用为点权,流量为$1$;左边的点向能匹配的右边的点连边,费用为$0$,流量为$1$,那么答案就是这个图的最大费用流。

注意到与$S$和$T$相连的边费用非负,且中间的边费用都是$0$,第一次增广后,左右那两条边费用取负,中间的$0$权边反向,因为左右两条边与源汇连接,所以以后最长增广路必然不会经过它,可以删除。而对于中间的$0$权边来说,将它们按强连通分量合并后增广路不变,所以可以如此缩成DAG,就可以每次在$O(n+m+e)$的时间内找到增广路。

时间复杂度$O(e(n+m+e))$。

然后不想写,写个裸费用流居然A了。

F. Right Turn Only

按题目要求分类讨论即可。

G. Similar Strings

$O(2^k)$枚举串中哪些位置必须匹配,算出Hash值,相同的Hash值的串之间可以互相更新答案。

时间复杂度$O(2^kn\log n)$。

H. Traffic Lights

留坑。

I. Triple Connections

区间DP,细节很多,留坑。