我不是大富翁时间限制2秒 空间限制128M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述提到大富翁游戏就想到环就想到经典的约瑟夫问题作为经典问题其出彩的展示了数学思维在实际问题中的应用启发了一代又一代的算竞人。好了不要再约瑟夫了都是经典问题害的你没法正常的玩大富翁游戏。现在让我们来愉快的玩大富翁吧R a b b i t RabbitRabbit拿到了一张环形的大富翁地图地图被平均划分为了n nn个地块地块的编号以1 11为起点顺时针进行排布。即1 11号地块的顺时针方向依次为2 , 3 , … … 2, 3, ……2,3,……号地块1 11号地块的逆时针方向依次为n , n − 1 , … … n , n−1, ……n,n−1,……号地块由于是环形的所以1 11号地块与n nn号地块相邻如下图所示。游戏过程如下系统会给定一个长度为m mm的行动力序列a 1 , a 2 , … , a m a_1,a_2,…,a_ma1,a2,…,am在第i ( 1 ≦ i ≦ m ) i (1≦i≦m)i(1≦i≦m)回合R a b b i t R RabbitRRabbitR都需要移动a i a_iai个地块但是他可以自由选择移动的方向换句话说可以自由选择是向逆时针还是顺时针方向移动a i a_iai个地块。在游戏的开始时R a b b i t RabbitRabbit位于1 11号地块他想知道是否存在这样一种移动方式使得m mm个回合后他依旧在1 11号地块。输入描述每个测试文件仅有一组测试数据。第一行输入两个整数n nn和m ( 1 ≦ n , m ≦ 5000 ) m (1≦n, m≦5000)m(1≦n,m≦5000)表示地块数量和行动回合数。第二行输入m mm个整数a 1 , a 2 , … , a m ( 0 ≦ a i ≦ 2 ⋅ 10 5 ) a_1,a_2,…,a_m (0≦a_i≦2⋅10^5)a1,a2,…,am(0≦ai≦2⋅105)表示行动力序列。输出描述如果m mm个回合后R a b b i t RabbitRabbit依旧在1 11号地块则输出Y E S YESYES否则请输出N O NONO。您可以以任何大小写形式输出答案例如y E s 、 y e s yEs 、yesyEs、yes和Y e S YeSYeS都将被视为肯定的回答。示例1输入360 3 120 120 120输出YES示例2输入50 5 30 0 10 10 10输出yES示例3输入114 5 14 1 9 1 9输出no备注如果您需要使用P y t h o n PythonPython解题我们建议您在提交时选择p y p y 2 pypy2pypy2或p y p y 3 pypy3pypy3。解题思路本题是环形可达性动态规划的经典模型核心是逐回合维护可能停留的位置集合利用模运算处理环形移动最终检查起点是否仍在集合中。1. 问题等价转化环形地块n nn个地块编号1 ∼ n 1 \sim n1∼n顺时针移动加、逆时针移动减。将地块编号改为0 ∼ n − 1 0 \sim n-10∼n−1起点变为0 00移动后的位置用模n nn运算表达。方向选择每回合给定步数a i a_iai可以选择 a i a_iai或− a i -a_i−ai即下一位置为( c u r r e n t a i ) m o d n (current a_i) \bmod n(currentai)modn或( c u r r e n t − a i ) m o d n (current - a_i) \bmod n(current−ai)modn确保非负。可达性状态记第i ii回合后可能位于哪些地块。初始仅在0 00号地块。若最终0 00号地块可达则答案为YES。2. 算法实现逐回合 DP状态表示用一个布尔数组x表示当前回合可能的位置长度n nnx[pos]1表示可以到达该位置。初始x[0]1。状态转移每回合新建布尔数组t全零遍历j ∈ [ 0 , n − 1 ] j \in [0, n-1]j∈[0,n−1]若x[j]1则将t[(j a[i]) % n]和t[(j - a[i] % n n) % n]置为 1。用t替换x进入下一回合。结果判定m mm回合后若x[0]为真则输出YES否则输出NO。3. 复杂度分析时间复杂度O ( n × m ) O(n \times m)O(n×m)。n , m ≤ 5000 n, m \le 5000n,m≤5000最大操作次数约2.5 × 10 7 2.5 \times 10^72.5×107在 2 秒时限内可行。空间复杂度O ( n ) O(n)O(n)两个长度为n nn的布尔数组滚动使用。总结将环形移动转化为模n nn的加减操作用逐回合 DP 维护所有可能到达的位置集合。由于n , m n, mn,m不大直接模拟所有可能路径即可无需贪心或数学构造。代码简要说明输入处理读入n , m n, mn,m和行动力数组a aa。DP 数组初始化vectorll x(n)作为当前回合可达状态x[0]1表示起点。逐回合转移创建临时数组t(n)。遍历j jj若x[j]1计算(j a[i]) % n和((j - a[i]) % n n) % n在t中标记。swap(x, t)更新状态。结果输出检查x[0]的值输出YES或NO。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidS(){ll n,m;cinnm;vectorlla(m);for(ll i0;im;i)cina[i];vectorllx(n);x[0]1;for(ll i0;im;i){vectorllt(n);for(ll j0;jn;j){if(x[j]1){t[(ja[i])%n]1;t[((j-a[i])%nn)%n]1;}}swap(x,t);}if(x[0])coutYES\n;elsecoutNO\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T1;while(T--)S();return0;}
我不是大富翁时间限制2秒 空间限制128M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述提到大富翁游戏就想到环就想到经典的约瑟夫问题作为经典问题其出彩的展示了数学思维在实际问题中的应用启发了一代又一代的算竞人。好了不要再约瑟夫了都是经典问题害的你没法正常的玩大富翁游戏。现在让我们来愉快的玩大富翁吧R a b b i t RabbitRabbit拿到了一张环形的大富翁地图地图被平均划分为了n nn个地块地块的编号以1 11为起点顺时针进行排布。即1 11号地块的顺时针方向依次为2 , 3 , … … 2, 3, ……2,3,……号地块1 11号地块的逆时针方向依次为n , n − 1 , … … n , n−1, ……n,n−1,……号地块由于是环形的所以1 11号地块与n nn号地块相邻如下图所示。游戏过程如下系统会给定一个长度为m mm的行动力序列a 1 , a 2 , … , a m a_1,a_2,…,a_ma1,a2,…,am在第i ( 1 ≦ i ≦ m ) i (1≦i≦m)i(1≦i≦m)回合R a b b i t R RabbitRRabbitR都需要移动a i a_iai个地块但是他可以自由选择移动的方向换句话说可以自由选择是向逆时针还是顺时针方向移动a i a_iai个地块。在游戏的开始时R a b b i t RabbitRabbit位于1 11号地块他想知道是否存在这样一种移动方式使得m mm个回合后他依旧在1 11号地块。输入描述每个测试文件仅有一组测试数据。第一行输入两个整数n nn和m ( 1 ≦ n , m ≦ 5000 ) m (1≦n, m≦5000)m(1≦n,m≦5000)表示地块数量和行动回合数。第二行输入m mm个整数a 1 , a 2 , … , a m ( 0 ≦ a i ≦ 2 ⋅ 10 5 ) a_1,a_2,…,a_m (0≦a_i≦2⋅10^5)a1,a2,…,am(0≦ai≦2⋅105)表示行动力序列。输出描述如果m mm个回合后R a b b i t RabbitRabbit依旧在1 11号地块则输出Y E S YESYES否则请输出N O NONO。您可以以任何大小写形式输出答案例如y E s 、 y e s yEs 、yesyEs、yes和Y e S YeSYeS都将被视为肯定的回答。示例1输入360 3 120 120 120输出YES示例2输入50 5 30 0 10 10 10输出yES示例3输入114 5 14 1 9 1 9输出no备注如果您需要使用P y t h o n PythonPython解题我们建议您在提交时选择p y p y 2 pypy2pypy2或p y p y 3 pypy3pypy3。解题思路本题是环形可达性动态规划的经典模型核心是逐回合维护可能停留的位置集合利用模运算处理环形移动最终检查起点是否仍在集合中。1. 问题等价转化环形地块n nn个地块编号1 ∼ n 1 \sim n1∼n顺时针移动加、逆时针移动减。将地块编号改为0 ∼ n − 1 0 \sim n-10∼n−1起点变为0 00移动后的位置用模n nn运算表达。方向选择每回合给定步数a i a_iai可以选择 a i a_iai或− a i -a_i−ai即下一位置为( c u r r e n t a i ) m o d n (current a_i) \bmod n(currentai)modn或( c u r r e n t − a i ) m o d n (current - a_i) \bmod n(current−ai)modn确保非负。可达性状态记第i ii回合后可能位于哪些地块。初始仅在0 00号地块。若最终0 00号地块可达则答案为YES。2. 算法实现逐回合 DP状态表示用一个布尔数组x表示当前回合可能的位置长度n nnx[pos]1表示可以到达该位置。初始x[0]1。状态转移每回合新建布尔数组t全零遍历j ∈ [ 0 , n − 1 ] j \in [0, n-1]j∈[0,n−1]若x[j]1则将t[(j a[i]) % n]和t[(j - a[i] % n n) % n]置为 1。用t替换x进入下一回合。结果判定m mm回合后若x[0]为真则输出YES否则输出NO。3. 复杂度分析时间复杂度O ( n × m ) O(n \times m)O(n×m)。n , m ≤ 5000 n, m \le 5000n,m≤5000最大操作次数约2.5 × 10 7 2.5 \times 10^72.5×107在 2 秒时限内可行。空间复杂度O ( n ) O(n)O(n)两个长度为n nn的布尔数组滚动使用。总结将环形移动转化为模n nn的加减操作用逐回合 DP 维护所有可能到达的位置集合。由于n , m n, mn,m不大直接模拟所有可能路径即可无需贪心或数学构造。代码简要说明输入处理读入n , m n, mn,m和行动力数组a aa。DP 数组初始化vectorll x(n)作为当前回合可达状态x[0]1表示起点。逐回合转移创建临时数组t(n)。遍历j jj若x[j]1计算(j a[i]) % n和((j - a[i]) % n n) % n在t中标记。swap(x, t)更新状态。结果输出检查x[0]的值输出YES或NO。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidS(){ll n,m;cinnm;vectorlla(m);for(ll i0;im;i)cina[i];vectorllx(n);x[0]1;for(ll i0;im;i){vectorllt(n);for(ll j0;jn;j){if(x[j]1){t[(ja[i])%n]1;t[((j-a[i])%nn)%n]1;}}swap(x,t);}if(x[0])coutYES\n;elsecoutNO\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T1;while(T--)S();return0;}
