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 #746 (Div. 2) C. Bakry and Partitioning
Codeforces Round #746 (Div. 2) C. Bakry and Partitioning
91 0
Educational Codeforces Round 113 (Rated for Div. 2)A. Balanced Substring
Educational Codeforces Round 113 (Rated for Div. 2)A. Balanced Substring
94 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.
266 0
Leetcode-Medium 152. Maximum Product Subarray
Leetcode-Medium 152. Maximum Product Subarray
122 0