标题:发一道题,求出这个字符串
只看楼主
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:432
帖 子:10064
专家分:41463
注 册:2014-5-20
得分:0 
以下是引用azzbcc在2016-12-14 10:43:25的发言:

正确性毋庸置疑,我也测试了len+1,吹水佬版主觉得呢

我是按规则数组各组顺序取出(不重复)的字符作为初始输出字符串。
这个要看首先假设的字符串排列,如果一开始就是 abcde 就快好多了, 可以试试初始为 edcba, 看看有什么不同。
可以跟踪一下m的变化看看。
2016-12-14 11:03
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:432
帖 子:10064
专家分:41463
注 册:2014-5-20
得分:0 
这个初始输出字符串是否还有考究。
按规则数组各组的列顺序取,先取所有的第1列,再取所有的第2列,最后取所有的第3列。
这样是否会快点?
2016-12-14 11:45
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
得分:0 
回复 25楼 azzbcc
运行没问题啊?怎么回事!今天干脆把4楼代码(原7楼)也修正了,测试也正常。同时测试了错误数据(如:c d a,a b c),不会限于死循环.

[此贴子已经被作者于2016-12-16 08:48编辑过]

2016-12-16 08:45
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
回复 33楼 xzlxzlxzl
哪管测试怎么变,原理不倒就没问题啦~我的测试也正常~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2016-12-16 09:05
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
得分:0 
回复 34楼 九转星河
测试你修改后的8楼代码真的没通过,估计你代码不是复制,是在原来基础上修改,没改完全(早期代码通过)。
2016-12-16 11:23
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
回复 35楼 xzlxzlxzl
你说的是那组测试代码???似乎没问题啊~

懂了,原代码本来就没有通过,我先细看一下是什么问题(对比一下我的库存样板)~

[此贴子已经被作者于2016-12-16 12:34编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2016-12-16 12:31
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
回复 35楼 xzlxzlxzl
冬瓜这行没改~//check(array,sizeof(array));//change(array,p,sizeof(array));

已经改正~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2016-12-16 12:44
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
得分:0 
好久不见小黑了,路过问好。

这个问题考点是拓扑排序。拓扑排序往往没有唯一解。比如小黑10楼的例子
3
 d e f
 a b c
 b d e
 abcdef

其实,abdcef,abdecf,abdefc也都满足要求。想要唯一解,应该规定个顺序,如按字典序排列。

好久没玩ACM了,凑个热闹。由于空间很小也就不做什么优化了。哦改了你的函数原型。
程序代码:
#include <stdio.h>

char * fun(char array[][3], int len, char * ans)
{
    char m[26][26] = {0}, d[26] = {0}, t[26] = {0}, * r = ans;
    int i, j;

    for(i = 0; i < len; i++)
    {
        char a = array[i][0] - 'a';
        char b = array[i][1] - 'a';
        char c = array[i][2] - 'a';
        if(!m[a][b]) m[a][b] = 1, d[b]++;
        if(!m[b][c]) m[b][c] = 1, d[c]++;
        t[a] = t[b] = t[c] = 1;
    }
    for(i = 0; i < 26; i++)
    {
        if(!t[i] || d[i]) continue;
        for(t[i] = j = 0; j < 26; j++) d[j] -= m[i][j];
        *(r++) = i + 'a';
        i = -1;
    }
    *r = 0;
    return ans;
}

int main()
{
    char array[1024][3], ans[32];
    int len, i, j;
    
    for(; ~scanf("%d\n", &len); puts(fun(array, len, ans)))
    for(i = 0; i < len; i++)
        scanf(" %c %c %c", &array[i][0], &array[i][1], &array[i][2]);
    return 0;
}
收到的鲜花
  • lyl9301302016-12-19 23:43 送鲜花  1朵   附言:真想把b版脑子切下来用...
  • azzbcc2016-12-20 11:45 送鲜花  1朵   附言:哈哈哈

重剑无锋,大巧不工
2016-12-17 16:03
xiajingran
Rank: 2
等 级:论坛游民
帖 子:31
专家分:28
注 册:2016-12-14
得分:0 
大神

小程序大智慧
2016-12-18 13:15
lyl930130
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:323
专家分:111
注 册:2013-5-13
得分:0 
回复 20楼 azzbcc
20楼 fix函数中的 i 设为 static 的话,时间还能减一大半。
2016-12-19 23:03



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-472197-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.076305 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved