#PQJ1267x6628. QOJ 1267_6628

    ID: 2580 传统题 1000ms 2048MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2023 集训枚举双指针

QOJ 1267_6628

2023 Canadian Computing Olympiad Day 2, Problem 1 Flip it and Stick it Time Limit: 1 second Problem Description Finn is playing a game of “Flip it and Stick it” which is abbreviated as FiSi. FiSi is a one-player game played on two strings, S and T, of 0s and 1s. Finn is allowed to make moves of the following form: • Select a substring of S and reverse it, gluing the pieces of the string back together in their original order to form the new string S. For example, Finn may take the string S = 101100, take the substring 011 starting at index 2 (assuming 1-based string indexing), and create the string S = 111000 in one move. Finn wins the game if S does not contain T as a substring. Your task is to help Finn determine the length of the shortest winning sequence of moves or tell him that the game cannot be won. Input Specification The first line of input contains the string S (1 ≤|S| ≤200 000). The second line of input contains the string T (1 ≤|T| ≤3). In the table below, T1 is the first bit in T, T2 is the second bit in T, and T3 is the third bit in T, when reading from left-to-right. Marks Awarded Bounds on T |T| = 1 1 mark |T| = 2, T1̸ = T2 3 marks |T| = 2 4 marks |T| = 3, T1̸ = T3 5 marks |T| = 3, T1̸ = T2 5 marks |T| = 3 7 marks Output Specification Output the minimum number of moves needed or −1 if it is impossible to win the game. Sample Input 1 100110 10 Output for Sample Input 1 2 Explanation of Output for Sample Input 1 Finn starts with the string 100110. He cannot avoid 10 as a substring in one move, but he can in two moves. For example, his first move could be to reverse the substring from index 4 to index 6 (110) to get 100011. Then, his second move can be to reverse the substring from index 1 to index 4 (1000) to get 000111, which does not have 10 as a substring. Sample Input 2 000 00 Output for Sample Input 2 -1 Explanation of Output for Sample Input 2 No matter how many moves Finn makes, the string S will always contain T as a substring.