[luogu1341][无序字母对]

luogu1341

思路

欧拉回路和欧拉路的裸题,首先判断是否存在欧拉路或者欧拉回路。当且仅当途中每个点的度数都为偶数时,存在欧拉回路。当且仅当图中度数为奇数的点的个数为2时,存在欧拉路。如果存在欧拉回路,就可以找一个最小的点开始dfs。如果存在欧拉路,那就只能从度数为奇数的两个点中更小的那个开始dfs。

欧拉回路的dfs过程大概就是一边删边,一边dfs。

如图,dfs的过程大概就是

1-2

2-3

3-6

6-5

5-4

4-1

1入队,返回

4入队,返回

5入队,返回

6-7

7-9

8-10

10-11

11-9

9-6

6入队,返回

9入队,返回

11入队,返回

10入队,返回

8入队,返回

7入队,返回

6入队,返回

3入队,返回

2入队,返回

1入队,结束

此时队列中刚是(1-4-5-6-9-11-10-8-7-6-3-2-1),就是一个合法的欧拉回路了。因为题目中要求按照字典序最小输出序列,所以每次搜索的时候先搜索字典序小的。然后将队列倒序输出才可以。

因为要按字典序从小到大搜索,所以邻接表似乎就有点麻烦了。所以直接用邻接矩阵。

代码

#include<cstdio>
#include<iostream>
using namespace std;
const int N = 1000;
int du[N],e[N][N],ji[N],ans[N*10],ansjs;
char c[5];
void dfs(int u) {
    for(int i = 'A';i <= 'z';++i) {
        if(!e[u][i]) continue;
        e[u][i]--;
        e[i][u]--;
        dfs(i);
    }
    ans[++ansjs]=u;
}
int main() {
//  freopen("text.in","r",stdin);
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;++i) {
        scanf("%s",c+1);
        e[int(c[1])][int(c[2])]++;
        e[int(c[2])][int(c[1])]++;
        du[int(c[1])]++;
        du[int(c[2])]++;
    }
    int js=0;
    for(int i = 'A';i <= 'z';++i)  if(du[i]&1)  ji[++js]=i;
    if(js != 0 && js != 2) {
        puts("No Solution");
        return 0;
    } 
    int s=1000;
    for(int i = 'A';i <= 'z';++i) {
        if(!du[i]) continue;
        if(js == 0) s=min(s,i);
        else if(du[i]&1) s=min(s,i); 
    }
    dfs(s);
    for(int i = ansjs;i >= 1;--i)
        printf("%c",ans[i]);
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 11:47
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务