社区讨论
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 条回复,欢迎继续交流。
正在加载回复...