D. Min Cost String
题意
思路
贪心地考虑 我们每次为当前字母 x 选择下一个字母 y 的时候 找到 {x,y} 出现的最小的 y 作为当前位置的选择
这样可以使得 字母对 重复的次数最少
代码
#include <bits/stdc++.h> //#define int long long #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 300050; int n, m; map<pair<int, int>, int> mp; int res[N]; int num[50]; void solve() { cin >> n >> m; res[0] = 0; for (int i = 1; i < n; ++i) { char s; int minn = 0x3f3f3f3f; int ff = 0x3f3f3f3f; for (int j = 0; j < m; ++j) { if (minn >= mp[{res[i - 1], j}]) { minn = mp[{res[i - 1], j}]; s = j; } } mp[{res[i - 1], s}]++; res[i] = s; } for (int i = 0; i < n; ++i) { printf("%c", res[i] + 'a'); } } signed main() { // int t; cin >> t; // while (t--) solve(); return 0; }