开题之后发现做过div2的QwQ
A Fox And Names
B Fox And Jumping
题目描述
你希望遍历一个长度为无穷的环
有(n)种卡片，你可以花费(c_i)的代价购买第(i)种卡片并可以无限次使用，每一次可以让你顺/逆时针跳(a_i)步，问是否存在一种方案，使得你可以遍历所有点，如果有，输出最小代价
(1leq n leq 300,1leq a_ileq 10^9,1leq c_ileq 10^5)
分析
我幼小呀
首先可以把问题简化为是否存在一种方案，使得(sum a_i*x_i=1)，其中，(a_i)是选了的那些卡片，(x_i)为任意整数
因为如果可以向某一个方向走1步，那么就可以遍历整个环，并且如果要遍历整个环，就必然要有一种方案可以向某个方向走一步
好了然后根据裴蜀定理的扩展，所有(a_i)的(gcd)要为(1)，那么直接(dp)就可以了
发现gcd的个数不会太多，可以用个map
C Fox And Dinner
题目描述
给出(n)个([2,100])的数，问能否把他们分成若干个大于等于3的环，使得任意相邻的两个数之和为质数
(1leq n leq 100)
分析
由于数值大于2，所以和为质数的两个数必然是一奇一偶。把所有的数分成奇偶两列，每一个数左右都有两个奇偶性和自己不同的数，那么从(S)到每个奇数点连(2)的边，从每个偶数点到 (T)连(2)的边，跑网络流就OK啦