欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Hdu 6675 度度熊与排列

程序员文章站 2023-12-27 09:14:27
...

Hdu 6675 度度熊与排列

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6675
Hdu 6675 度度熊与排列
Hdu 6675 度度熊与排列
解题思路:用map暴力记录上面这串在下面这串里的出现次数,每一 次记录后判断这两串中每个字符数量是不是一样,如果不一样,那就表示不可能满足题目,标记flag直接输出-1即可,然后就是用for遍历m次,每次找出现次数最多(表示可能性最大),用map保证了出现次数一样的位置最小,(题目要求顺序字典序最小),找完后标记输出即可;
代码如下:

#include<bits/stdc++.h>
using namespace std;
char s[60],c[60];//上串和下串
int vis[60];//标记数组
map<int,int>mp[60];//记录数组
map<int,int>::iterator it;
bool flag;
int main() {
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d %d",&n,&m);
        flag=true;
        for(int i=1;i<=m;i++){//初始化map
            mp[i].clear();
        }
        for(int i=0;i<n;i++){
            scanf("%s %s",s+1,c+1);
            for(int j=1;j<=m;j++){
                for(int k=1;k<=m;k++){
                    if(s[j]==c[k]){//记录是j位出现在k位的次数,次数越多可能性越大
                        mp[j][k]++;//题目题目是位置对应,所以不需要考虑字母对结果的影响,只需要记录对应位置就行
                    }
                }
            }
            memset(vis,0,sizeof(vis));
            for(int i=1;i<=m;i++){//标记两串字符的出现次数,如果一样就都为0
                vis[s[i]-'a']++;
                vis[c[i]-'a']--;
            }
            for(int i=0;i<26;i++){//如果两串字符个数不对就表示不能组成
                if(vis[i]!=0){
                    flag=false;
                    break;
                }
            }
        }
        if(flag){
            memset(vis,0,sizeof(vis));
            for(int i=1;i<=m;i++){//找第i位应该出现的位置
                int s=0,e=0;//最多出现次数,对应的位置
                for(it=mp[i].begin();it!=mp[i].end();it++){//map保证字典序最小,次数相同,位置小的在前
                    if(s<it->second&&vis[it->first]==0){//如果当前出现次数更多且这个点的位置没有被确认
                        s=it->second;
                        e=it->first;
                    }
                }
                vis[e]=1;//标记e位已经有对应的上串位置了,避免重复标记导致错误
                printf("%d%c",e,i==m?'\n':' ');
            }
        }else{
            printf("-1\n");
        }
    }
    return 0;
}
相关标签: 补题

上一篇:

下一篇: