E2. String Coloring (hard version)

时间：2024-07-09

原题：Codeforces Round 617 (Div. 3) E2. String Coloring (hard version)

题意

给一串小写字母组成的字符串，要求上色，只有颜色不同的相邻字母能换位置

不考虑交换次数，问最少涂几种颜色才能使最后的序列有序

思路

假定当前遇到的都是有序的，当遇到下一个字母，假定是无序的，就需要将无序的穿插进来

穿插途中会遇到比自己序列大的字母，那么需要与这些数的颜色不同就行

比如abcfed，abcf有序，都涂色1，遇到e时，e之前大于e的只有f，需要越过f，即颜色要不同，为2

d前有fe，需要越过两个，颜色不同，为3

代码

string s;

int arr[N];
int ans[N];
int maxmp(map<int, int>m) {
    for (int i = 0; i <= 26; i++) 
        if (!m[i])return i;
}

void solve() {
    cin >> n;
    cin >> s;
	//先将字母处理成数字
    for (int i = 0; i < n; i++) 
        arr[i] = s[i] - 'a';

    map<int, int>ans_choice[26];
    //先处理0，不过其实不用处理的。。。不过我觉得这样便于理解，写的时候没想这么多
    rep(ii, 0, 26) {ans_choice[ii][0]++;}
	//mp存储一下出现过的颜色，方便计数
    map<int, int>mp;
    for (int i = 0; i < n; i++) {
        //先获取答案
        ans[i] = maxmp(ans_choice[arr[i]]);
        mp[ans[i]]++;
        //然后将所有序列小于当前位的ans_choice中加上ans[i]
        //因为后续再出现，意味着需要越过本位，即需要与本位不同
        for (int j = 0; j < arr[i]; j++) 
            ans_choice[j][ans[i]]++;
    }

    cout << mp.size() << endl;
    for (int i = 0; i < n; i++) 
        cout << ans[i] << " ";
    
    cout << endl;
}

D. Paint the Tree

时间：2024-07-08

原题：Codeforces Round 592 (Div. 2) D. Paint the Tree

题意

给一颗树，有n个结点并且有三种颜色供选择，其中每个结点涂色的代价不同

现在要求将所有相连的三个节点涂色，保证三个节点的颜色不同

即对于u v w，u和v相连，v和w相连，三者颜色各不相同

思路

首先能确定，能成功涂色的必定是单链

然后先假定这条链是按顺序的，1->2->3...

那么涂色顺序就有两种，123或者321，当然由于开始的点不同，所以总共需要枚举6种

枚举结束，找最小答案和对应的涂色方式输出

然而，好像是前六个例子是有序的，后面是无序的，所以就需要用桶的思想

代码

int c[3][N];

int cnt[N] = { 0 };
// T[i]表示标记为i的点在链中的顺序   
int T[N];

unordered_map<int, vector<int>>mp;
//123顺序
int get1(int i) {
    int ans = 0;
    rep(jj, 0, n) {
        ans += c[i][T[jj] - 1];
        i++;
        i %= 3;
    }
    return ans;
}
//321顺序
int get2(int i) {
    int ans = 0;
    rep(jj, 0, n) {
        ans += c[i][T[jj] - 1];
        i--;
        i = (i + 3) % 3;
    }
    return ans;
}

void solve() {
    cin >> n;
    rep(ii, 0, n) { cin >> c[0][ii]; }
    rep(ii, 0, n) { cin >> c[1][ii]; }
    rep(ii, 0, n) { cin >> c[2][ii]; }

    int u, v;
    rep(ii, 0, n - 1) {
        cin >> u >> v;
        mp[u].push_back(v);
        mp[v].push_back(u);

        cnt[u]++;
        cnt[v]++;
    }

    //判断是不是一条链
    int beg = 0;
    rep(ii, 1, n + 1) {
        if (cnt[ii] == 1)beg = ii;
        if (cnt[ii] > 2) { cout << -1 << endl; return; }
    }

	//按链的顺序存桶里
    T[0] = beg;
    for (int i = 1; i < n; i++) {
        auto t = mp[T[i - 1]];
        if (i - 2 >= 0) T[i] = (t[0] != T[i - 2] ? t[0] : t[1]);
        else T[i] = t[0];
    }

    int ans1 = 1e18, ans2 = 1e18, ans3 = 1e18;
    int ansi1 = 0, ansi2 = 0, ansi3 = 0;
	//枚举答案
    rep(ii, 0, 3) {
        int t = get1(ii);
        if (t < ans1) {
            ans1 = t;
            ansi1 = ii;
        }
    }

    rep(ii, 0, 3) {
        int t = get2(ii);
        if (t < ans2) {
            ans2 = t;
            ansi2 = ii;
        }
    }
    //存数字和对应颜色,就是ans
    int p[N] = { 0 };
	
    if (ans1 < ans2) {
        cout << ans1 << endl;
        rep(ii, 0, n) {
		    //同样 根据桶来填充答案
            p[T[ii]] = ansi1 + 1;
            ansi1++;
            ansi1 %= 3;
        }
    }
    else {
        cout << ans2 << endl;
        rep(ii, 0, n) {
            p[T[ii]] = ansi2 + 1;
            ansi2--;
            ansi2 = (ansi2 + 3) % 3;
        }
    }
    rep(ii, 1, n + 1) {
        cout << p[ii] << " ";
    }
}