HELP!!!!!
查看原帖
HELP!!!!!
948553
Johnsmz楼主2023/6/21 12:00

求救大佬帮帮忙,我觉得我写的没有问题,但是13-15过不了。 我是用图论来解的,好像思路和题解的第一个题解的差不多,但是实现方法不同。

拿第十三个测速点点最后一个例子来说,答案是51,但是我判成 了-1。具体思路看第一篇题解:判了一个纯环且所有字母都用完的情况下判-1。

我用映射表做了一个图,很明显有一个三元纯环(I-l-H),且所有字母都用完了。不是很明白为什么不是-1而是51

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void proc(){
    int len = 0, ans = 0, assigned = 0;
    int * has_behind = calloc(150,sizeof(int)); //check how many nodes are pointing this node to check loop
    char * from = calloc(1e5+5,sizeof(char)), * to = calloc(1e5+5,sizeof(char)), * map = calloc(150,sizeof(char));fgets(from,1e5+3,stdin);fgets(to,1e5+3,stdin);len=(int)strlen(from);len--; //input
    for(int i = 0; i < len; i++){
        if(map[from[i]]){if(map[from[i]]!=to[i]){printf("-1\n");free(from);free(to);free(map);return;}}//if one character is mapping to two different characters, return -1
        else{map[from[i]]=to[i];has_behind[to[i]]++;assigned++;}//assign this character and count one more character
    }
    int check_num = 0; _Bool * already = calloc(150,sizeof(_Bool));
    for(int i = 'A'; i <= 'Z' && check_num!=52; i++){//for characters from 'A' to 'Z'
        if(already[i]){continue;}//skip when this character is already calculated
        int cur = i, next = map[i], last = 0, lastlast = 0;
        _Bool * check_loop = calloc(150, sizeof(_Bool));
        while(1){
            if(already[cur]){//if current character is already calculated
                if(check_loop[cur]){//check loop
                    int cc = cur;
                    if(has_behind[cc]>1){break;}
                    cc=next;_Bool add = 1;
                    while(cc!=cur){if(has_behind[cc]>1){add=0;break;}cc=map[cc];}//for every characters in the loop, if it is has braches that is not included in the loop, it does not need to add 1
                    if(add){
                        if(assigned==52 && lastlast!=cur){printf("-1\n");return;}//if every element is used, return -1
                        ans++;
                    }
                }
                break;
            }
            already[cur] = 1; check_loop[i] = 1; check_num++;//mark the character is already calculated
            if(next==0 || next==cur){break;}//check break
            lastlast = last; last = cur; cur = next; next = map[cur]; ans++;//swap current character
        }
        free(check_loop);
    }
    for(int i = 'a'; i <= 'z' && check_num!=52; i++){//same for 'a' to 'z'
        if(already[i]){continue;}
        int cur = i, next = map[i], last = 0, lastlast = 0;
        _Bool * check_loop = calloc(150, sizeof(_Bool));
        while(1){
            if(already[cur]){if(check_loop[cur]){
                int cc = cur;
                if(has_behind[cc]>1){break;}
                cc=next;_Bool add = 1;
                while(cc!=cur){if(has_behind[cc]>1){add=0;break;}cc=map[cc];}
                if(add){if(assigned==52 && lastlast!=cur){printf("-1\n");return;}ans++;}
            }break;}
            already[cur] = 1; check_loop[i] = 1; check_num++;
            if(next==0 || next==cur){break;}
            lastlast = last; last = cur; cur = next; next = map[cur]; ans++;
        }
        free(check_loop);
    }
    free(from);free(to);free(map);
    printf("%d\n",ans);
}

int main(){int t; scanf("%d",&t); fgetc(stdin); while(t--){proc();}}// scan examples


2023/6/21 12:00
加载中...