CodeForces 510C Fox And Names

Dear 丶 2022-08-19 08:19 89阅读 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 条评论，89人围观）

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

相关阅读

相关 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 赞/ 104 阅读

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

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

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

相关 CodeForces 510C Fox And Names

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

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

相关 codeforces 459C - Pashmak and Buses 【构造题】

题目：[codeforces 459C - Pashmak and Buses][] 题意：给出n个人，然后k辆车，d天时间，然后每天让n个人选择坐一辆车去上学，要

妖狐艹你老母/ 2022年08月11日 03:29/ 0 赞/ 79 阅读

相关【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 赞/ 114 阅读

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

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

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

相关 Codeforces1092C. Prefixes and Suffixes——————思维，字符串

C. Prefixes and Suffixes Ivan wants to play a game with you. He picked some string s

àì夳堔傛蜴生んèń/ 2022年04月03日 09:54/ 0 赞/ 160 阅读

相关 Codeforces 1097C. Yuhao and a Parenthesis——————思维

[C. Yuhao and a Parenthesis][] One day, Yuhao came across a problem about checking if

偏执的太偏执、/ 2022年03月30日 15:54/ 0 赞/ 115 阅读

相关 CodeForces 1051c-Vasya and Multisets

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

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

相关 CF510E Fox And Dinner

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

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