专栏文章

题解：CF1784B Letter Exchange

wwasz
CF1784B题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minduabg
此快照首次捕获于
2025/12/02 00:47
3 个月前
此快照最后确认于
2025/12/02 00:47
3 个月前
查看原文

CF1784B 题解

题目传送门

题目大意

有 3m3m 张纸条，分别写有 w，i，n，现在随机发给 mm 个人，现在请进行次数最少的两两交换操作，使恰好每人手中是 win。

思路

采用一下映射，win 分别对应 11，22，33。
然后略微贪心的匹配一下，首先一定是的多 11 缺 22 与多 22 缺 11 的匹配（包括类似的），然后剩下的大概就是像样例中的一圈循环多 11 缺 22，多 22 缺 33，多 33 缺 11，或者多 11 缺 33，多 22 缺 11，多 33 缺 22，且只有这两种，把他们三个分为一组，一组只需要两次操作。
那么为了方便记录开一个二维 vector 一维记录多余，后一维记录所缺，注意到一人手中只有可能多于一个字符，但有可能缺两个字符，比如 www，要把它存在 vec[1][2] 与 vec[1][3]。记录之后模拟前面的操作就好了。

代码

代码长但是很多是复制粘贴。码风抽象，不必在意。
CPP
int main()
{
    scanf("%d", &ttt);
    while(ttt--)
    {
        b[1][2].clear(), b[2][1].clear(), b[1][3].clear(), b[3][1].clear(), b[2][3].clear(), b[3][2].clear();//多测清空
        scanf("%d", &m);
        char op;
        for(int i = 1; i <= m; i++)
        {
            int st1 = 0, st2 = 0, st3 = 0;
            for(int j = 1; j <= 3; j++)
            {
                cin >> op;
                if(op == 'w') st1++;
                if(op == 'i') st2++;
                if(op == 'n') st3++;
            }
            //记录所缺与所多
            if(st1 == 3) b[1][2].push_back(i), b[1][3].push_back(i);
            if(st2 == 3) b[2][1].push_back(i), b[2][3].push_back(i);
            if(st3 == 3) b[3][1].push_back(i), b[3][2].push_back(i);
            if((st1 == 1) && (st2 == 2)) b[2][3].push_back(i);
            if((st1 == 1) && (st3 == 2)) b[3][2].push_back(i);
            if((st2 == 1) && (st1 == 2)) b[1][3].push_back(i);
            if((st2 == 1) && (st3 == 2)) b[3][1].push_back(i);
            if((st3 == 1) && (st2 == 2)) b[2][1].push_back(i);
            if((st3 == 1) && (st1 == 2)) b[1][2].push_back(i);
        }
        string ans = "";//统计答案
        int cnt = 0;//记录操作次数
        int l12 = b[1][2].size(), l21 = b[2][1].size(), l13 = b[1][3].size(), l31 = b[3][1].size(), l23 = b[2][3].size(), l32 = b[3][2].size();
        //第一层模拟[2][1]与[1][2]
        int ww = min(l12, l21);
        for(int i = ww-1; i >= 0 ; i--)
        {
            int u = b[1][2][l12-1], v = b[2][1][l21-1];
            l12--, l21--, cnt++;
            ans += to_string(u);
            ans += 'w';
            ans += to_string(v);
            ans += 'i';
        }
        ww = min(l13, l31);
        for(int i = ww-1; i >= 0 ; i--)
        {
            int u = b[1][3][l13-1], v = b[3][1][l31-1];
            l13--, l31--, cnt++;
            ans += to_string(u);
            ans += 'w';
            ans += to_string(v);
            ans += 'n';
        }
        ww = min(l32, l23);
        for(int i = ww-1; i >= 0 ; i--)
        {
            int u = b[3][2][l32-1], v = b[2][3][l23-1];
            l32--, l23--, cnt++;
            ans += to_string(u);
            ans += 'n';
            ans += to_string(v);
            ans += 'i';
        }
        //分组型模拟
        int res = l23+l31+l12;
        cnt += (res/3)*2, res /= 3;
        int rr = l23;
        while(res--)
        {
            rr--;
            ans += to_string(b[2][3][rr]);
            ans += 'i';
            ans += to_string(b[1][2][rr]);
            ans += 'w';
            ans += to_string(b[2][3][rr]);
            ans += 'w';
            ans += to_string(b[3][1][rr]);
            ans += 'n';
        }
        res = l21+l32+l13;
        cnt += (res/3)*2, res /= 3;
        rr = l21;
        while(res--)
        {
            rr--;
            ans += to_string(b[2][1][rr]);
            ans += 'i';
            ans += to_string(b[3][2][rr]);
            ans += 'n';
            ans += to_string(b[2][1][rr]);
            ans += 'n';
            ans += to_string(b[1][3][rr]);
            ans += 'w';
        }
        printf("%d\n", cnt);
        int wwww = 0;
        for(int i = 0; i < ans.size(); i++) 
        {
            //按输出要求输出
            if((ans[i] == 'w') || (ans[i] == 'i') || (ans[i] == 'n')) cout << " ";
            cout << ans[i];
            if((ans[i] == 'w') || (ans[i] == 'i') || (ans[i] == 'n')) cout << " ", wwww++;
            if(wwww == 2) cout << '\n',  wwww = 0;
        }
    }
    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...