D. Dividing Strings
题意：
把一个数字串划成若干段（至少两段，每段不能有前导0），使得最大值和最小值的差尽量的小。
数字串长度：(N<=10^5)
思路：
如果划分为单个数字，显然 ans<=9。
接着考虑，哪些情况下会出现更小的答案？
- 最大值的长度和最小值的长度相同。枚举 N 的所有约数作为每个子段的长度，切割原串计算最大值和最小值的差，更新答案，复杂度为 (O(Nsqrt{N}))。
- 最大值的长度和最小值的长度相差1。因为只有小于9的方案才有效，我们只要判断最小值为999x 和 最大值为 1000y 这样的形式，其中 x = 2~9，y = 0~7。
注意情况：
- 注意子段可能很长，不能用 int 或 long long 存。
- 对第2种情况，如果最小值是1位，最大值是2位，最小值前没有前缀9，需要特判。
- 对第2种情况，找最长连续9可能会出问题，如 “9999991001”。因此应找最长的 1000y 来判断。
丑陋的代码QAQ：
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define vi vector<int>
#define SZ(x) (int)x.size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
int check(string s, int len) {
string Max, Min;
for(int i = 0; i < len; i++) {
Max += '0';
Min += '9';
}
for(int i = 0; i <= SZ(s) - len; i += len) {
string tmp = s.substr(i, len);
Max = max(Max, tmp);
Min = min(Min, tmp);
}
if(Min[0] == '0' && SZ(Min) > 1)
return 10;
int ans = 0;
for(int i = 0; i < len; i++) {
ans = (Max[i] - Min[i]) + ans * 10;
if(ans > 9)
return 10;
}
return ans;
}
int solve1(string s) {
int x = -1, yy = 20;
for(int i = 0; i < SZ(s);) {
if(s[i] == '1') {
if(i + 1 == SZ(s))
return 10;
if(yy == 20)
yy = stoi(s.substr(i, 2));
else
yy = max(yy, stoi(s.substr(i, 2)));
i += 2;
} else {
if(x == -1)
x = s[i] - '0';
else
x = min(x, s[i] - '0');
i++;
}
}
return yy - x;
}
bool cmp(string a, string b) {
if(SZ(a) != SZ(b))
return SZ(a) > SZ(b);
return a > b;
}
int solve2(string s) {
vector<string> tmp;
for(int i = 0; i < SZ(s);) {
if(s[i] != '1') {
i++;
continue;
}
int j = i + 1;
if(j == SZ(s))
return 10;
while(j < SZ(s) && s[j] == '0')
j++;
if(j == SZ(s)) {
tmp.pb(s.substr(i, j - i));
break;
}
if(j + 1 == SZ(s)) {
tmp.pb(s.substr(i, j - i + 1));
i = j + 1;
} else {
if(s[j + 1] == '0') {
tmp.pb(s.substr(i, j - i));
i = j;
} else {
if(s[j] == '9') {
tmp.pb(s.substr(i, j - i));
i = j;
} else {
tmp.pb(s.substr(i, j - i + 1));
i = j + 1;
}
}
}
}
if(tmp.empty() || SZ(tmp[0]) <= 2)
return 10;
sort(tmp.begin(), tmp.end(), cmp);
string MaxStr = tmp[0];
string Min;
for(int i = 0; i < SZ(MaxStr) - 1; i++)
Min += '9';
int pos = s.find(MaxStr);
string s1 = s.substr(0, pos);
string s2 = s.substr(pos + SZ(MaxStr), SZ(s) - pos - SZ(MaxStr));
for(int i = 0; i < SZ(s1);) {
if(s1[i] != '1' && s1[i] != '9')
return 10;
if(i + SZ(MaxStr) <= SZ(s1) && s1.substr(i, SZ(MaxStr)) <= MaxStr) {
i += SZ(MaxStr);
} else {
if(i + SZ(MaxStr) - 1 > SZ(s1))
return 10;
Min = min(Min, s1.substr(i, SZ(MaxStr) - 1));
i += SZ(MaxStr) - 1;
}
}
for(int i = 0; i < SZ(s2);) {
if(s2[i] != '1' && s2[i] != '9')
return 10;
if(i + SZ(MaxStr) <= SZ(s2) && s2.substr(i, SZ(MaxStr)) <= MaxStr) {
i += SZ(MaxStr);
} else {
if(i + SZ(MaxStr) - 1 > SZ(s2))
return 10;
Min = min(Min, s2.substr(i, SZ(MaxStr) - 1));
i += SZ(MaxStr) - 1;
}
}
Min = "0" + Min;
int ans = 0;
for(int i = 0; i < SZ(MaxStr); i++) {
ans = ans * 10 + (MaxStr[i] - Min[i]);
if(ans > 10)
return 10;
}
return ans;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
string s;
cin >> s;
int ans = 9;
for(int i = 1; i * i <= n; i++) {
if(n % i != 0)
continue;
if(i < n)
ans = min(ans, check(s, i));
if(n / i < n)
ans = min(ans, check(s, n / i));
}
ans = min(ans, solve1(s));
ans = min(ans, solve2(s));
printf("%d
", ans);
}
}