求救大佬帮帮忙,我觉得我写的没有问题,但是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