社区讨论

WA 6分,求调

P9013[USACO23JAN] Find and Replace S参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m5ce8mpk
此快照首次捕获于
2024/12/31 19:37
去年
此快照最后确认于
2025/11/04 12:08
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int maxletter=52;
int T;
set<int> st;
vector<int> G[1005];
queue<int> q;
bool isedge[1005][1005];
int out[MAXN],in[MAXN];
bool vis[MAXN];
int convert(char ch){
    if(ch>='A'&&ch<='Z'){
        int tmp=ch-'A'+1;
        return tmp;
    }
    else{
        int tmp=ch-'a'+27;
        return tmp;
    }
}
void top_sort(){
    for(int i=1;i<=maxletter;i++){
        if(!in[i]) q.push(i);
    }
    while(!q.empty()){
        int u=q.front();
        vis[u]=1;
        q.pop();
        for(int i:G[u]){
            in[i]--;
            // if(u==27){
                // printf("in['b']: %d\n",in[i]);
            //     printf("vis['b']: %d\n",vis[i]);
            // }
            if(!vis[i]&&!in[i]) q.push(i);
        }
    }
}
void dfs(int key){
    vis[key]=1;
    for(int i:G[key]){
        if(!vis[i]) dfs(i);
    }
}
void init(){
    st.clear();
    for(int i=0;i<1005;i++) G[i].clear();
    while(!q.empty()) q.pop();
    memset(out,0,sizeof out);
    memset(in,0,sizeof in);
    memset(isedge,0,sizeof isedge);
    memset(vis,0,sizeof vis);
}
int main()
{
    scanf("%d",&T);
    while(T--){
        init();
        int ans=0;
        bool flag=0;
        string s1,s2;
        cin>>s1>>s2;
        for(int i=0;i<s1.length();i++){
            int num1=convert(s1[i]);
            int num2=convert(s2[i]);
            // printf("num: %d %d\n",num1,num2);
            if(isedge[num1][num2]) continue;
            isedge[num1][num2]=1;
            if(num1==num2){
                out[num1]++;
                st.insert(num1);
                continue;
            }
            // st.insert(num1);
            st.insert(num2);
            G[num1].push_back(num2);
            ans++;
            out[num1]++;
            in[num2]++;
        }
        for(int i=1;i<=maxletter;i++){
            if(out[i]>1){
                flag=1;
                break;
            }
        }
        // printf("ans1: %d\n",ans);
        if(flag||(st.size()==maxletter&&s1!=s2)){
            // printf("flag: %d\n",flag);
            puts("-1");
        }
        else{
            top_sort();
            for(int i=1;i<=maxletter;i++){
                if(!vis[i]){
                    // printf("i: %d\n",i);
                    ans++;
                    dfs(i);
                }
            }
            printf("%d\n",ans);
        }
    }
    

    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...