A.
模拟题。
B.
- 如果全部相等,输出 0
- 如果最小值为 1,那么一定不可能,输出 -1
剩下的情况必定有解,考虑每次用所有大于最小值的数字除掉最小值,最多不会超过 log 次。
C.
给一个字符串 $s$,排列成一个字符串 $t$,令 $t_{max} = \max{t, rev(t)}$。
输出最小的 $t_{max}$。
经过转化题意:求 $s$ 排列字典序最小的,且反转后的字典序小于等于本身的字符串。
考虑构造,显然可以从小枚举到大枚举 $s$ 的所有字符。
假设当前枚举到 $x$,若 $x$ 还剩下至少两个,则前缀后缀都加上 $x$。
若除 $x$ 还剩下另一种字符 $y$,先加上$\frac{cnt_y}{2}$ 个 $y$ 再加上 $x$ 再加上 $\frac{cnt_y}{2}$ 个 $y$。
否则按顺序随意添加即可。
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
| void run_case() { string s; cin >> s; int cnt[26] = {0}; tr(x, s) cnt[x - 'a']++; int n = sz(s); vector<int> ans(n); int l = 0, r = n - 1, p = -1; rep(i, 0, 26) { while (cnt[i] > 1) ans[l++] = ans[r--] = i, cnt[i] -= 2; if (cnt[i] == 1) { p = i; break; } } if (p != -1) { int c = 0; rep(i, 0, 26) if (cnt[i])++ c; if (c == 2) { rep(i, p + 1, 26) { while (cnt[i] > 1) { ans[l++] = ans[r--] = i; cnt[i] -= 2; } if (cnt[i] == 1) ans[l++] = i; } ans[r--] = p; } else { rep(i, p + 1, 26) { while (cnt[i]--) ans[l++] = i; } ans[r--] = p; } } for (auto x : ans) { cout << char(x + 'a'); } cout << "\n"; }
|
D.