Unique Palindromes-526互联

<a href="https://www.cnblogs.com/LuoGuyexc/articles/17397324.html">更好的阅读体验</a>。
一道贪心题。
首先，本质不同的回文串最多只有 $n$ 个.
我们注意到 $k$ 很小，甚至小于字符集的大小，我们不难发现一个长度为 $x$ 的由相同字母组成的串能够贡献 $x$ 个本质不同回文子串。
所以其实每一段我们都可以使用一种相同的字母来实现回文子串数量的增加，因为 $k$ 小于 $26$，所以字母数量是够用的。
下面还有个问题就是要把相同串之间填充，使得不产生新的回文子串。
我们可以考虑第一段用后面全部为 $c$ 的方式填充，然后中间空余的部分就不停地用重复的循环串来填充，可以发现这样不会产生新的回文子串。
<pre><code class="language-cpp">for (int i = 0; i < k; i++) {
if (c[i] > x[i]) {
s.clear();
break;
}
if (i == 0) {
s += "ab", s += string(c[i] - 2, 'c');
int cnt = x[i] - c[i];
s += add.substr(st, cnt), st += cnt;
} else {
if (c[i] - c[i - 1] > x[i] - x[i - 1]) {
s.clear();
break;
}
int need = c[i] - c[i - 1];
int cnt = x[i] - x[i - 1] - need;
s += add.substr(st, cnt);
st += cnt;
s += string(need, char('a' + i + 2));
}
}
</code></pre>