一道acm题目
发布网友
发布时间：2022-04-26 18:26
共2个回答
热心网友
时间：2023-10-20 22:58
当然题目描述还是有问题，因为最后的结果也不是按上面说的那种做法(题目的实际描述)，而是只要用来统计的那个变量一大于11519就令它减去11519，这个差别会使得总结果为11519*n (n>1)时最后的输出不一样(前者为0，后者为11519)。
我实在是不怎么看得懂你的程序的思路(贴代码的时候最好写上思路或注释)，但明显是走了弯路，直接排序很快就可以得到结果。
以下是我AC的代码，在Status的运行速度排第三。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char list[49999][30];
/*
int和long (int)的取值范围是一样的
*/
int cmp( const void* a, const void* b )
{
return strcmp( (char*)a, (char*)b );
}
// 判断是不是前缀
bool prefix( char* a, char* b )
{
for ( int t = 0; a[t]; t++ )
if ( a[t] != b[t] )
return 0;
return 1;
}
int main()
{
int test, n, ans, i, j;
scanf( "%d", &test );
while ( test-- )
{
scanf( "%d", &n );
for ( i = 0; i < n; i++ )
scanf( "%s", &list[i] );
qsort( list, n, sizeof( char ) * 30, cmp ); // 字符串快排
ans = 0;
// 对于每个字符串，遍历它之后的元素如果符合前缀则计数，不符合则再往后的字符串都不会符合
for ( i = 0; i < n - 1; i++ )
for ( j = i + 1; j < n; j++ )
if ( prefix( list[i], list[j] ) )
ans++;
else
break;
// 题目的描述有问题
while ( ans > 11519 )
ans -= 11519;
printf( "%d\n", ans );
}
return 0;
}
C语言不支持bool类型，把prefix的返回类型改成int就可以用C提交了。
学习ACM最好是到PKU、ZJU等OJ上，因为网上会有题目分类，便于你找到合适的题型。顺便说下HUST的OJ不能查看自己提交过的代码真的很不习惯……
希望会对你有所帮助！~
BY: http://acm.tju.e.cn/toj/user_swy.html
热心网友
时间：2023-10-20 22:58
