经典的区间翻转问题。
和挑战程序设计那本书的那个题几乎一样，就把那个代码敲上去改了几句话就可以过了
思路：
从大到小枚举区间大小，再枚举最后翻转成的那个数字
然后从第一个开始判断，应该翻多少下，并维护前K个翻转总次数sum
那么第二个又应该翻多少下，是确定的，可以求出来，依次求第三个，第四个。。
直到最后小于K个的时候，判断剩下的是否都等于我们枚举最后成的那个数字。
所以翻转的复杂度是O(n)，总的复杂度是O(10*n^2)
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1000 + 5;
const int INF = 0x3f3f3f3f;int N;
int dir[MX];
int f[MX];bool calc(int K, int p) {memset(f, 0, sizeof(f));int sum = 0;for(int i = 0; i + K <= N; i++) {if((dir[i] + sum) % 10 != p) {f[i] = ((p - (dir[i] + sum)) % 10 + 10) % 10;}sum += f[i];if(i - K + 1 >= 0) {sum -= f[i - K + 1];}}for(int i = N - K + 1; i < N; i++) {if((dir[i] + sum) % 10 != p) {return false;}if(i - K + 1 >= 0) {sum -= f[i - K + 1];}}return true;
}void solve() {int ans = 1;for(int k = N; k >= 1; k--) {bool sign = false;for(int p = 0; p <= 9; p++) {if(calc(k, p)) {ans = k;sign = true;break;}}if(sign) break;}printf("%d\n", ans);
}char S[MX];
int main() {int T;scanf("%d", &T);while(T--) {scanf("%s", S);N = strlen(S);for(int i = 0; i < N; i++) {dir[i] = S[i] - '0';}solve();}return 0;
}