| 题目名称 | 2695. strcmp()函数 |
|---|---|
| 输入输出 | strcmp.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 mouse
于2017-05-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：4， 提交：16， 通过率：25% | ||||
 joel |
100 | 0.754 s | 36.41 MiB | C++ |
|
joel |
100 | 1.020 s | 7.07 MiB | C++ |
|
joel |
100 | 1.192 s | 6.77 MiB | C++ |
|
joel |
100 | 1.204 s | 7.77 MiB | C++ |
 Bennettz |
90 | 3.224 s | 80.71 MiB | C++ |
 Shirry |
80 | 3.365 s | 6.69 MiB | C++ |
|
Bennettz |
80 | 3.859 s | 82.84 MiB | C++ |
|
Bennettz |
80 | 4.187 s | 72.63 MiB | C++ |
|
Bennettz |
80 | 4.360 s | 80.47 MiB | C++ |
 rewine |
70 | 5.404 s | 112.64 MiB | C++ |
| 本题关联比赛 | |||
| 20170519 | |||
| 关于 strcmp()函数 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
lrj原书原题？
 rvalue
2017-06-02 20:51
2楼
| ||||
|
纯暴力也能过？
说好的trie树并没有出现。 纳尼考试时我连暴力都错了・゜・(PД`q｡)・゜・…… Shirry
2017-05-31 19:09
1楼
| ||||
【题目描述】
strcmp()是c/c++的一个库函数，它的作用是比较两个字符串的字典序大小。在本题中，考虑strcmp()的如下实现。
int strcmp(char *s,char *t)
{
int i;
for(i=0;s[i]==t[i];i++)
if(s[i]=='\0')
return 0;
return s[i]-t[i];
}
如上所述，比较操作一直进行到两个字符串的对应位置处的字符不相同为止（假定字符串总是以'\0'结尾）。比如，strcmp("than","that")和strcmp("there","the")各需要7次比较（注意s[i]==t[i]和s[i]=='\0'各有一次比较），如下图所示。
输入n个字符串，两两调用一次strcmp()(即一共调用n(n-1)/2次)，问字符比较的总次数是多少？
【输入格式】
输入文件包含不超过10组测试数据，每组测试数据的第一行为一个整数N(0<N<4001),即字符串总数，接下来N行每行包含一个不超过1000个由'0'~'9'、'a~z'和'A~Z'组成的非空字符串。输入结束标志为N=0。输入文件大小约为23M。
【输出格式】
对于每组测试数据，输出一行内容，先输出测试数据编号，再输出字符比较的总次数T（详细输出格式见样例）。输入保证T在64位带符号整数范围内。
【样例输入】
2 a b 4 cat hat mat sir 0
【样例输出】
Case 1: 1 Case 2: 6
【来源】
《算法竞赛入门经典-训练指南》