Educational Codeforces Round 107 (Rated for Div. 2) D - Min Cost String

简介: 笔记

D. Min Cost String


题意

18.png


思路

贪心地考虑 我们每次为当前字母 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;
}


目录
相关文章
Codeforces Round #192 (Div. 2) (330B) B.Road Construction
要将N个城市全部相连,刚开始以为是最小生成树的问题,其实就是一道简单的题目。 要求两个城市之间不超过两条道路,那么所有的城市应该是连在一个点上的,至于这个点就很好找了,只要找到一个没有和其他点有道路限制的即可。
40 0
|
人工智能 测试技术
Codeforces Round #746 (Div. 2) C. Bakry and Partitioning
Codeforces Round #746 (Div. 2) C. Bakry and Partitioning
83 0
Educational Codeforces Round 113 (Rated for Div. 2)A. Balanced Substring
Educational Codeforces Round 113 (Rated for Div. 2)A. Balanced Substring
87 0
|
机器学习/深度学习
|
人工智能
Educational Codeforces Round 98 (Rated for Div. 2)B-Toy Blocks
You are asked to watch your nephew who likes to play with toy blocks in a strange way. He has n boxes and the i-th box has ai blocks. His game consists of two steps: he chooses an arbitrary box i; he tries to move all blocks from the i-th box to other boxes.
260 0