CodeForces 510C Fox And Names

Dear 丶 2022-08-19 08:19 141阅读 0赞

一道拓扑排序题!!

注意判断各种情况，两个字符串比较的时候，从左向右开始比较，当出现不同的字母后，不再向后比较。一个是另一个的前缀，那么长的在后面。

当给出的顺序出现环的时候，或者有串的前缀在串的后面时，出现错误。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<vector>
    char a[1001][1001];
    int in[10001],v[1001][101],cnt;
    char b[1001];
    using namespace std;
    int topsort()
    {
    	int t1,t2,i,j;
    	for(i=0;i<26;i++)
    	{
    		for(j=0;j<26;j++)
    		{
    			if(in[j]==0)
    			{
    				t1=j;
    				in[j]=-1;
    				break;
    			}
    		}
    		if(j==26)
    			return 0;
    		b[cnt++]=j+'a';
    		for(j=0;j<26;j++)
    		{
    			if(v[t1][j])
    			{
    				in[j]--;
    			}
    		}
    	}
    	return 1;
    } 
    int main()
    {
    	int i,j,m,n,l;
    	while(~scanf("%d",&n))
    	{
    		cnt=0;
    		memset(v,0,sizeof(v));
    		memset(in,0,sizeof(in));
    		for(i=0;i<n;i++)
    		{
    			scanf("%s",a[i]);
    		}
    		for(i=0;i<n-1;i++)
    		{
    			int f=0;
    			int l1=strlen(a[i]);
    			int l2=strlen(a[i+1]);
    			for(j=0;j<min(l1,l2);j++)
    			{
    				if(a[i][j]!=a[i+1][j])
    				{
    					f=1;
    					int t1=a[i][j]-'a';
    					int t2=a[i+1][j]-'a';
    					if(!v[t1][t2])
    					{
    						in[t2]++;
    						v[t1][t2]=1;						
    					}
    					break;
    				}
    			
    			}
    			if(l2<l1&&f==0)
    			{
    				printf("Impossible\n");
    				return 0;
    			}
    		}
    		if(topsort())		
    			puts(b);
    		else
    			puts("Impossible");
    		
    	} 
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #290 (Div. 2) B. Fox And Two Dots dfs

E - E Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u Submit [St

梦里梦外;/ 2022年09月25日 05:18/ 0 赞/ 141 阅读

相关 510-C++问题总结(1)

1、C++this指针干什么用的？ 1个类型定义的对象都有各自的成员变量，但是是共享一套成员方法，在成员方法里，是访问谁的成员变量，这个是靠this指针区分的。1个类型定义

迈不过友情╰/ 2022年09月09日 12:56/ 0 赞/ 167 阅读

相关 CodeForces 552C-Vanya and Scales【思维】

C. Vanya and Scales time limit per test 1 second memory limit per test 256 megabytes

女爷i/ 2022年08月21日 06:49/ 0 赞/ 31 阅读

相关 CodeForces 510C Fox And Names

一道拓扑排序题!! 注意判断各种情况，两个字符串比较的时候，从左向右开始比较，当出现不同的字母后，不再向后比较。一个是另一个的前缀，那么长的在后面。当给出的顺序出现环的时

Dear 丶/ 2022年08月19日 08:19/ 0 赞/ 142 阅读

相关 codeforces 389A. Fox and Number Game

题目链接\[CF 389A.\] ([http://codeforces.com/problemset/problem/389/A][http_codeforces.com_p

男娘i/ 2022年08月10日 06:10/ 0 赞/ 9 阅读

相关 Codeforces 659C Tanya and Toys

Codeforces 659C Tanya and Toys time limit per test 1 second memory limit per test 25

逃离我推掉我的手/ 2022年07月18日 01:48/ 0 赞/ 15 阅读

相关【codeforces 766C】Mahmoud and a Message

C. Mahmoud and a Message time limit per test 2 seconds memory limit per test 256 meg

男娘i/ 2022年07月12日 05:05/ 0 赞/ 159 阅读

相关 Codeforces Round #510 (Div. 2) D. Petya and Array

题目：[点击打开链接][Link 1] 题意：给定一个数组，问有多少个不同的区间\[l,r\] (l<=r)使得区间和小于给定的数t。分析：先求个前缀和，则问题转化

朱雀/ 2022年05月15日 18:24/ 0 赞/ 215 阅读

相关 CodeForces 1051c-Vasya and Multisets

题目衔接：[http://codeforces.com/problemset/problem/1051/C][http_codeforces.com_problemset_pr

桃扇骨/ 2022年02月15日 13:37/ 0 赞/ 158 阅读

相关 CF510E Fox And Dinner

[题面][Link 1] 题解首先可以发现：由于\\(a\_i \\geq 2\\)，所以质数肯定是被拆成一个奇数和一个偶数。这样的话很类似一个二分图模型，所

谁践踏了优雅/ 2021年10月15日 14:55/ 0 赞/ 226 阅读