P1092分析(无代码)

November 9, 2019 · 算法 · 1064次阅读

P1092 分析

剪枝分析

  1. 从左到右分别编号1-n,则1号位的加法不应该有进位,否则无法保证对齐,因此剪掉
  2. 每一列都应该遵守(A+B)%n=C OR (A+B+1)%n=C,否则应当剪掉(即每一个加法结果位都应该是两个加数%n或者进一位之后%n,否则这个结果肯定是不正确的)


    结果判定分析

  3. 从第n位开始往前判断,添加一个x变量用于存上一位加法的进位(1 or 0),从而通过比较计算机加法计算结果和题目给出的固定结果是否一致判定正确性


    细节

  4. 模拟竖式计算的时候必须严格从第n位向前计算,否则会导致计算过程中的进位没有正确的加入下一位,最后导致计算机计算结果的错误
  5. 注意题目并没有强调n的数量和字母的数量一致,换句话说就是并不一定n进制就一定要给出n个字母
  6. 注意给出的竖式中,同一行并不一定包括了所有的字母,也不一定没有重复字母。因此在程序最开始的位置应该统计给出的竖式中包含的所有为止字母
  7. 对于全排列的时间问题,由于每一次全排列并不一定真的会算下去,也许刚开始就被剪掉了,因此不需要考虑超时的问题
  8. 26个字母确实有26进制,但这里不需要去关心,照样算就ok


    留下的问题

    虽然已经AC了但是最后一个点是打表过的
  9. 剪枝仍然没剪彻底,目前还不知道是哪里的问题,只知道现在在n>=20的时候会出问题(但并不是算不出来,只是运行时间会拉长)

none

最后编辑于4年前

添加新评论