解题思路

• 问题抽象

  • 允许配对的仅限“同大小写且互补”的字母对：小写 (a,z)/(z,a), (b,y)/(y,b), ..., (m,n)/(n,m)；大写 (A,Z)/(Z,A), ..., (N,M)/(M,N)。
  • 互补条件等价于二者位置和为 27：若 pos(c) 为字母在字母表中的位置（不分大小写），则可配当且仅当二者同为小写或同为大写，且 pos(x) + pos(y) = 27。
  • 配对在环上不能相交，等价于“区间不交叉匹配”。

• 环转线的处理

题目内容

魔法项链是一个环形链条，上面串联着 $n$ 个宝石，每个宝石上刻着一个英文字母。

你可以选择若干对宝石，使得:

• 每对宝石刻的字母恰好是一个字母括号对，具体为小写对 $(a,z),(z,a),(b,y),(y,b),...,(m,n),(n,m)$;

• 或大写对 $(Z,A),(A,Z),(Y,B),(B,Y),·.·,(N,M),(M,N)$ ;