| 单词拼接 |
|
南阳理工OJ 99 单词拼接（欧拉通路） |
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxcolor=26;
int G[maxcolor+1][maxcolor+1];
vector<string> ans;//存放结果数组
priority_queue<string, vector<string>, greater<string> >mm[maxcolor+1][maxcolor+1];//按字典序排
int abs(int x)
{
return x>0?x:-x;
}
void euler(int u)
{
int uu,vv,flag=1;
while(flag)
{
string str="{";//初始化str为最大
flag=0;
for(int v=1;v<=maxcolor;v++)//找其中字典序最小的
{
if(G[u][v])
{
flag=1;
if(str>mm[u][v].top())
{
str=mm[u][v].top();
uu=u;
vv=v;
}
}
}
if(flag)//继续深搜字典序最小的
{
mm[uu][vv].pop();
G[uu][vv]--;
euler(vv);
ans.push_back(str);//最小的存在结果数组里面
}
}
}
int f()//找起点函数
{
int ru,chu,res=0,start=0;
for(int i=1;i<=maxcolor;i++)
{
ru=chu=0;
for(int j=1;j<=maxcolor;j++)
{
if(start==0&&G[i][j]!=0)start=i;//如果是欧拉图，起点就是第一个字母最小的那个单词
chu+=G[i][j];
ru+=G[j][i];
}
res+=abs(chu-ru);
if(chu>ru)start=i;//如果是半欧拉图，起点就是出度大一点的那个单词
}
if(res>2)return -1;//如果不构成欧拉路，就跳出
return start;
}
int main()
{
// freopen("Input.txt","r",stdin);
int T,start;
string str,term;
scanf("%d",&T);
while(T--)
{
memset(G,0,sizeof(G));
int n;
scanf("%d",&n);
for(int i=1;i<=26;i++)
for(int j=1;j<=26;j++)
while(!mm[i][j].empty())mm[i][j].pop();
for(int i=0;i<n;i++)
{
cin>>str;
int len=(int)str.size();
G[str[0]-'a'+1][str[len-1]-'a'+1]++;//存图，单词的开始为出度点，结尾为入度点
mm[str[0]-'a'+1][str[len-1]-'a'+1].push(str);
}
start=f();
if(start==-1)
{
printf("***\n");
continue;
}
ans.clear();
euler(start);
if((int)ans.size()!=n)//如果单词没有找完，说明不连通，就输出***
{
printf("***\n");
continue;
}
for(int i=ans.size()-1;i>=0;i--)//输出结果
{
if(i!=0)cout<<ans[i]<<".";
else cout<<ans[i];
}
cout<<endl;
}
return 0;
}
|
| 南阳OJ 99 单词拼接 |
|
|
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
using namespace std;
const int maxcolor=26;
int G[maxcolor+1][maxcolor+1];
vector<string> ans;//存放结果数组
map<string,priority_queue<string, vector<string>, greater<string> > >mm;//按字典序排
int abs(int x)
{
return x>0?x:-x;
}
void euler(int u)
{
int uu,vv,flag=1;
while(flag)
{
string str="{",term;
flag=0;
for(int v=1;v<=maxcolor;v++)//找其中字典序最小的
{
if(G[u][v])
{
flag=1;
term=(char)(u+'a'-1);
term+=(char)(v+'a'-1);
if(str>mm[term].top())
{
str=mm[term].top();
uu=u;
vv=v;
}
}
}
if(flag)//继续深搜字典序最小的
{
term=(char)(uu+'a'-1);
term+=(char)(vv+'a'-1);
mm[term].pop();
G[uu][vv]--;
euler(vv);
ans.push_back(str);//最小的存在结果数组里面
}
}
}
int f()//找起点函数
{
int ru,chu,res=0,start=0;
for(int i=1;i<=maxcolor;i++)
{
ru=chu=0;
for(int j=1;j<=maxcolor;j++)
{
if(start==0&&G[i][j]!=0)start=i;//如果是欧拉图，起点就是第一个字母最小的那个单词
chu+=G[i][j];
ru+=G[j][i];
}
res+=abs(chu-ru);
if(chu>ru)start=i;//如果是半欧拉图，起点就是出度大一点的那个单词
}
if(res>2)return -1;//如果不构成欧拉路，就跳出
return start;
}
int main()
{
// freopen("Input.txt","r",stdin);
int T,start;
string str,term;
scanf("%d",&T);
while(T--)
{
memset(G,0,sizeof(G));
mm.clear();
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
cin>>str;
term=str[0];
term+=str[str.size()-1];
G[term[0]-'a'+1][term[1]-'a'+1]++;//存图，单词的开始为出度点，结尾为入度点
mm[term].push(str);
}
start=f();
if(start==-1)
{
printf("***\n");
continue;
}
ans.clear();
euler(start);
if((int)ans.size()!=n)//如果单词没有找完，说明不连通，就输出***
{
printf("***\n");
continue;
}
for(int i=ans.size()-1;i>=0;i--)//输出结果
{
if(i!=0)cout<<ans[i]<<".";
else cout<<ans[i];
}
cout<<endl;
}
return 0;
}
|
| 南阳理工OJ 99 单词拼接 |
|
|
错误的做法 单词拼接
#include<cstdio>
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<string.h>
using namespace std;
int linker[27];
bool mask[27];
int find(int x)
{
return linker[x]==x ? x : linker[x]=find(linker[x] ) ;
}
struct son
{
char e;
string str;
}term;
bool operator < (const son a,const son b)
{
return a.str>b.str;
}
struct node
{
int chu;
int ru;
priority_queue<son>q;
};
map<char,node>m;
int main()
{
freopen("in.txt","r",stdin);
int T,n,i,num,x,y;
char a,b;
string str;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(mask,0,sizeof(mask)) ;//初始化
for(i=0;i<27;i++)linker[i]=i;
for(i=0;i<26;i++)while(!m[i+'a'].q.empty())m[i+'a'].q.pop(); //用完回收
m.clear();
for(i=0;i<n;i++) //输出
{
cin>>str;
a=str[0];
b=str[str.size()-1];
mask[a-'a']=true;
mask[b-'a']=true;
x=find(a-'a');
y=find(b-'a');
if(x!=y)linker[x]=y;
term.e=b;
term.str=str;
m[a].chu++;
m[b].ru++;
m[a].q.push(term);
}
a='a';
for(i=0+'a',num=0;i<=0+'z';i++) //判断是否是欧拉通路
{
if(m[i].chu!=m[i].ru)num++;
if(m[i].chu>m[i].ru)a=i;
}
if(num>2)
{
printf("***\n");
continue;
}
for(i=0,num=0;i<26;i++) //判断是否是连通图
if(linker[i]==i&&mask[i]==true)num++;
if(num>1)
{
printf("***\n");
continue;
}
cout<<m[a].q.top().str;
b=m[a].q.top().e;
m[a].q.pop();
a=b;
while(!m[a].q.empty())
{
cout<<'.'<<m[a].q.top().str;
b=m[a].q.top().e;
m[a].q.pop();
a=b;
}
printf("\n");
}
return 0;
}
|
| Uva1394 - And Then There Was One |
|
|
#include<stdio.h>
int main()
{
int a;
int n,m,k,i;
while(scanf("%d%d%d",&n,&k,&m)!=EOF)
{
if(n==0&&m==0&&k==0)
{
break;
}
for(i=1,a=0;i<n;i++)
a=(a+k)%i;
printf("%d\n",(a+m)%n+1);
}
return(0);
}
|
