小红的循环移位时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红拿到了一个数字串她每次操作可以使得其向左循环移动一位。将串s s 0 s 1 … s n − 1 s s_0 s_1 \dots s_{n-1}ss0​s1​…sn−1​向左循环移动一位将得到串s 1 … s n − 1 s 0 s_1 \dots s_{n-1} s_0s1​…sn−1​s0​。小红想知道使得该数字串变成4 44的倍数需要最少操作多少次可以包含前导零输入描述一个数字串长度不超过10 5 10^5105。输出描述如果无法达成目的则输出-1。否则输出一个整数代表最少的操作次数。示例 1输入201输出1说明操作一次数字串变成012是4 44的倍数。示例 2输入135输出-1说明无论操作多少次该字符串都是奇数不可能是4 44的倍数。数据范围与提示串长不超过10 5 10^5105核心结论一个数是否为4 44的倍数只取决于它的末两位前导零不影响因为100 100100能被4 44整除。做法向左循环移动k kk位后新串的末两位分别是原串下标( n − 2 k ) m o d n (n-2k) \bmod n(n−2k)modn与( n − 1 k ) m o d n (n-1k) \bmod n(n−1k)modn的字符即原串中循环相邻的两位。于是只需枚举k ∈ [ 0 , n − 1 ] k \in [0, n-1]k∈[0,n−1]检查这两字符拼成的两位数能否被4 44整除取最小的合法k kk即为答案。注意边界n 1 n 1n1时末两位不存在此时只需判断该单个数字能否被4 44整除即{ 0 , 4 , 8 } \{0, 4, 8\}{0,4,8}能则答案为0 00否则为− 1 -1−1。时间复杂度O ( n ) O(n)O(n)直接枚举即可。解题思路本题是字符串循环移位 倍数判定的简单模拟题。核心结论一个数是否为4 44的倍数只取决于它的末两位因为100 100100能被4 44整除。因此只需枚举所有可能的左移次数检查移位后数字串的末两位能否被4 44整除取最小的合法次数即可。1. 问题等价转化设原数字串为s ss长度为n nn。向左循环移动c cc位后新串的第i ii个字符对应原串下标( i − c n ) m o d n (i - c n) \bmod n(i−cn)modn。新串的末两位分别位于位置n − 2 n-2n−2和n − 1 n-1n−10-based因此它们对应的原串下标为倒数第二位i ( n − 2 c ) m o d n i (n-2 c) \bmod ni(n−2c)modn倒数第一位j ( n − 1 c ) m o d n ( i 1 ) m o d n j (n-1 c) \bmod n (i 1) \bmod nj(n−1c)modn(i1)modn拼接这两个字符得到两位数判断其是否能被4 44整除即可。枚举c cc从0 00到n − 1 n-1n−1一旦找到满足条件的c cc就输出若遍历完都没有则输出− 1 -1−1。特殊地当n 1 n1n1时上述公式中i j 0 i j 0ij0检查的是11 × s [ 0 ] 11 \times s[0]11×s[0]是否能被4 44整除等价于判断单个数字能否被4 44整除结果正确。2. 算法实现读入数字串s ss获取长度n nn。循环c cc从0 00到n − 1 n-1n−1计算i ( n − 2 c ) % n i (n - 2 c) \% ni(n−2c)%nj ( i 1 ) % n j (i 1) \% nj(i1)%n。将s[i]和s[j]转换为数字拼接成两位数num (s[i]-0)*10 (s[j]-0)。若num % 4 0输出c并结束程序。若循环结束仍未找到输出-1。3. 复杂度分析时间复杂度枚举c cc共n nn次每次O ( 1 ) O(1)O(1)计算总时间复杂度O ( n ) O(n)O(n)。n ≤ 10 5 n \le 10^5n≤105完全可行。空间复杂度仅需存储输入字符串O ( n ) O(n)O(n)。总结利用“末两位决定能否被4 44整除”的性质将循环移位问题转化为枚举原串中循环相邻的两位字符。通过简单的下标变换直接检查所有可能的末两位组合找到最小的左移次数。算法简洁高效边界情况n 1 n1n1也自然涵盖。代码简要说明读入字符串sn s.size()。循环c从 0 到n-1i (n - 2 c) % nj (i 1) % n。计算((s[i]-0)*10 (s[j]-0)) % 4。若为 0输出c并return 0。循环结束输出-1。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);string s;cins;ll ns.size();for(ll c0;cn;c){ll i(n-2c)%n;ll j(i1)%n;if(((s[i]-0)*10(s[j]-0))%40){coutc;return0;}}cout-1;return0;}