48分求助,真的看不出什么问题了。。。

P3065 [USACO12DEC] First! G

找到问题了,赋优先值时的问题,例: ``` 2 acc acb ``` 正确答案应该是acb在字母顺序为abc时可以满足第一字典序,而我自己的思想把顺序写成了acb。
by _DtrIsta3int @ 2022-11-09 21:58:34


@[_DtrIsta3int](/user/430202) 请问可以具体描述吗?(我刚好也错了这几个点
by Acerakoi @ 2023-01-04 10:28:48


@[Acerkaio](/user/514850) 就是2楼我写的那个样例的问题,如果acb要满足第一字典序,那么字母顺序的规则应该是a>b>c,但是按照我的代码的思想排成了a>c>b,因为我的思想是字母首次出现得越早优先度就越高,但是再排c的优先级的时候没有考虑到如果存在字符串与他有相同的前缀剩下不同的后缀要怎么排的问题(我表达的不是太好sry,而且我现在也没过,弃了
by _DtrIsta3int @ 2023-01-06 00:25:45


@[_DtrIsta3int](/user/430202) 我知道我错哪了,我拓扑的时候,把入度为 0 的加了一次就 break; 了
by Acerakoi @ 2023-01-06 08:32:08


@[_DtrIsta3int](/user/430202) 我和楼主的问题一样,后来发现26个字母的优先度可以用拓扑排序解决,有环时立刻返回就可以了
by Dog_E @ 2023-10-15 21:06:57


确切的说是构造一个单向图,字典序最小的时候是不会有环的
by Dog_E @ 2023-10-15 21:09:19


|