P8296 [COCI2012-2013#2] KRIZALJKA 题解

· · 题解

upd 2022.7.8：修改了对 map 做法的解释以及删去了一个错误的小方法。

简单看了下题解区，两位搜索的和一位循环枚举的。我个人倾向于循环的方式。

题意

在六个字符串中选三个组成矩阵，矩阵中的横竖六个字符串刚好是这六个原串的字典序最小的方案。

分析

输入保证按字典序给出。

这句话说明了我们在枚举答案时不需要统一储存取最小的，只要输出第一个答案即可。

接下来谈一些细节方面的实现方式。

当枚举出三个字符串时比较容易得到纵向的三个字符串。
然而目前的题解似乎想复杂了，其实不需要一一判断其唯一性。

方法是把所有的六个字符串（包括枚举的和求出的）排序后连接起来，然后将原来的序列也这样操作，比较两者是否一致就可以了。

代码

基于以上思路，代码见下。 

#include <bits/stdc++.h>
using namespace std;
string s[10],T,check;
bool flag=1;
int main()
{
    for(int i=1;i<=6;i++) cin>>s[i],check=check+s[i];
    for(int i=1;i<=6;i++)for(int j=1;j<=6;j++)for(int k=1;k<=6;k++)
        if(i!=j&&j!=k&&i!=k)
        {
            string px[10];
            for(int l=0;l<=2;l++)
                px[l+1]=T+s[i][l]+s[j][l]+s[k][l];
            px[4]=s[i],px[5]=s[j],px[6]=s[k];
            sort(px+1,px+7);
            string fl="";
            for(int l=1;l<=6;l++) fl=fl+px[l];
            if(fl==check)
            {
                cout<<s[i]<<endl<<s[j]<<endl<<s[k]<<endl;flag=0;
                return 0;
            }
        }
    if(flag) cout<<0;
}

注意到一段代码。

for(int l=0;l<=2;l++)
    px[l+1]=T+s[i][l]+s[j][l]+s[k][l];

这段代码中的 T 是什么？
其实在这一点上我借鉴了 @xt__ 的代码。如果去掉这个或者改成空字符串都会有 bug。例如去掉就会变成空值，加上空字符串会是乱码。

之前我说这题不能用 map 来解决，但其实遇到样例 1 这样的相同情况我们比较的就不是其存在性，而是直接比较其出现的次数和原来的是否一致即可。

同时弥补之前的学术谬误，此处再给出代码。 

#include <bits/stdc++.h>
using namespace std;
string s[10],T;
map<string,int> ans;
int main()
{
    for(int i=1;i<=6;i++) cin>>s[i],ans[s[i]]++;
    for(int i=1;i<=6;i++)for(int j=1;j<=6;j++)for(int k=1;k<=6;k++)
        if(i!=j&&j!=k&&i!=k)
        {
            map<string,int> mp;
            int flag2=1;
            string px[10];
            for(int l=0;l<=2;l++) px[l+1]=T+s[i][l]+s[j][l]+s[k][l]; 
            px[4]=s[i],px[5]=s[j],px[6]=s[k];
            for(int i=1;i<=6;i++) mp[px[i]]++;
            for(int i=1;i<=6;i++) if(!mp[s[i]]||mp[s[i]]!=ans[s[i]]) flag2=0;
            if(flag2)
            {
                cout<<s[i]<<endl<<s[j]<<endl<<s[k]<<endl;
                return 0;
            }
        }
    cout<<0;
}