题目描述：
给出一个长度为 $ n $ 的字符串 $ s $ ，以及两个整数 $ a,b $ ，其中 $ n $ 为偶数。
两种操作：
- 累加：加 $ a $ 加到 $ s $ 中下标为奇数的元素上。超过 $ 9 $ 时变成 $ 0 $ 。
- 轮转：将 $ s $ 向右轮转 $ b $ 位。
对 $ s $ 可以执行上述任意次操作，返回能够得到的字典序最小的字符串。
数据范围：
$ 2\le n \le 100,1\le a \le 9, 1\le b \le n - 1 $
题解：
解法一：
直接bfs，每次生成两个分支，直到队列为空。
解法二：
枚举。因为两个操作可以独立分离，因此可以直接枚举轮换的次数和累加的次数。因为轮换最多轮换 $ n $ 次，累加最多累加 $ 10 $ 次。但是 $ b $ 分奇偶，如果为奇数，累加时需要枚举奇数位置和偶数位置；如果为偶数，只需要枚举偶数位置。因此复杂度为 $ O(n^2 \times 10^2) $ .
考虑优化。假设轮换 $ x $ 次，最终的起始位置为 $ z = xb \mod{n} $ ，即 $ z = xb - ny $ ，根据裴蜀定理，该方程有解则必有 $ z $ 被 $ \gcd(b,n) $ 整除。因此枚举轮转只需要枚举 $ [0, n) $ 中 $ gcd(b,n) $ 的倍数即可。
再优化。由于轮转和累加可以分开考虑，同时需要使得字典序最小。因此只需要考虑 $ t[1] $ 和 $ t[0] $ 即可。先找到使得 $ t[1] $ 最小的累加次数， $ b $ 为奇数的话，再找到使得 $ t[0] $ 最小的累加次数。
会有一个疑问？如果存在多个累加次数得到的 $ t[1] $ 相等，但是 $ t[3] $ 不一样，那么就会有问题。
这种情况应该是不存在的，如果存在两个累加次数 $ t[1] $ 相等，那么说明这个累加次数得到的累加值是 $ 10 $ 的倍数，那么 $ t[3] $ 也会是相等的。
代码：
优化前：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
string findLexSmallestString(string s, int a, int b)
{
int n = s.size();
string ans = s;
s = s + s;
vector<bool> vis(s.size(), false);
for (int start = 0; vis[start] == false; start = (start + b) % n)
{
vis[start] = true;
for (int j = 0; j < 10; ++j)
{
int k_max = (b & 1) ? 9 : 0;
for (int k = 0; k <= k_max; ++k)
{
string tmp = s.substr(start, n);
for (int p = 1; p < n; p += 2)
{
tmp[p] = '0' + (tmp[p] - '0' + j * a) % 10;
}
for (int p = 0; p < n; p += 2)
{
tmp[p] = '0' + (tmp[p] - '0' + k * a) % 10;
}
ans = min(ans, tmp);
}
}
}
return ans;
}
};
|
优化后：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
string findLexSmallestString(string s, int a, int b)
{
int n = s.size();
string ans = s;
s = s + s;
int gcd = __gcd(b, n);
int minx, times, tmp;
string t;
for (int start = 0; start < n; start += gcd)
{
t = s.substr(start, n);
times = 0;
minx = 9;
for (int j = 0; j < 10; ++j)
{
tmp = (t[1] - '0' + j * a) % 10;
if (tmp < minx)
{
minx = tmp;
times = j;
}
}
for (int j = 1; j < n; j += 2)
{
t[j] = '0' + (t[j] - '0' + times * a) % 10;
}
if (b & 1)
{
times = 0;
minx = 9;
for (int j = 0; j < 10; ++j)
{
tmp = (t[0] - '0' + j * a) % 10;
if (tmp < minx)
{
minx = tmp;
times = j;
}
}
for (int j = 0; j < n; j += 2)
{
t[j] = '0' + (t[j] - '0' + times * a) % 10;
}
}
ans = min(ans, t);
}
return ans;
}
};
|
