BestCoder-Round#33

写在前面

  • 这是我第一次做BestCoder, 熟悉的外观BestCoder模式.
  • BC上不仅能看到英文, 背部Chinese view是中文题目
  • 交的次数是会影响得分的. 所以有了把握再交. 至少例子要过吧.
  • 一定要考虑全部特殊情况, 由于有很多积极的Hacker正等着你上钩. 即使交过Accepted之后一旦被Hack成功一分都没有. 唉…
  • 我的第一次BestCoder比赛就以两个题被Hack两个题不会结束了.
  • 感觉BestCoder的比赛还是非常刺激的. 拼手速, 拼细心, 拼代码能力.
  • 题目: http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=571

赛后题解

  • 第一题字符串, 但我发现我字符串的基本功还是不行啊, 做了近一个小时(一開始不知道有中文题面, 到处找翻译也费了不少时间), 还是看别人代码打的.

    • 不能输出前导零
    • 结果是0也不能不输出
    • 被hack后改呀改, 最终发现我在输出时假设数字大于10也用的+’0’输出…
  • 第二题倒是挺顺利的想到解法. 首先, 拐点一定是1或者n. 把1作为拐点时, 假设1在第i个位置上, 除了1之外还有n-1个数字, 1的左面能够从n-1个数字中任选i-1个数字, 并且有且仅仅有一种排法(递减), 选完左側右側也就确定了, 且也仅仅有一种排法(递增). 而把n当作拐点的排法总数和1时相等, 同一时候要注意到1, 2, …, n 和 n, n-1, …, 1 的排列被计算了两次. 总结果要减去2. 那么总的排法就是

    ans=2∗∑i=0n−1C(n−1,i)−2=2∗2n−1−2=2n−2

    ans = 2 * \sum_{i = 0}^{n - 1}{C(n-1, i)} - 2 = 2 * 2^{n-1} - 2 = 2^n - 2

    假设在比赛时想到这里就提交, 你会发现你A了, 但假设你在Hack的时间时去群里看一下, 就会发现事情并不单纯.

    • 当n = 1时, 总的排法应该是 1 而不是 2^1 - 2 = 0. 全部递增的序列和全部递减的序列并没有被算两次. 由于它一共就一个序列.

      所以要加特判, n=1时输出 1

      完了吗?

      没有…(hack好强大)

    • 由于数据范围非常大, 10^18, long long ? 可是乘法时可能溢出, 所以还须要写高速乘, 在矩阵乘法的题里曾用到过. 我当时犹豫要不要写, 但看到第一次提交AC后就没有写. 我当时还不知道hack有多强大.

      到这里, 全部问题应该都攻克了吧?



      唉, 又调了好半天. 各种习惯不好导致的错误
    • 首先 n=1 时不能简单的输出1, 由于m还可能等于1
    • 然后, 记得把全部变量都开long long
    • 最后一个是我犯的错误, 在高速幂和高速乘的时候我先把传入的两个參数都模了…&%#……
  • A, B题都是基础的东西, 但掌握的都不好

  • 认为做BestCoder非常刺激样子.

  • 第三题后来看别人的代码弄明确了. 用map实现的DP

    • 先依照解决这个问题最早開始的时间先后排序
    • map<int, long long> f[2] 来记录状态. map是当前时间到最大分数的映射. f[2] 是滚动数组.
    • 假设选择放弃解决当前的问题, 就从上个状态的时间转移到当前状态的时间就可以, 分数不变.
    • 假设选择解决当前问题, 就从上个状态的一个时间(pre_t)转移到当前状态的一个合法时间, 分数加上当前问题的分数. 这里须要考虑哪个时间是合法的, 假设pre_t加上任务所需时间早于最早完毕时间, 就转移到最早完毕时间, 否则转移到pre_t加上任务所需时间.
    • 用迭代器遍历map须要满足map里至少有一个元素吧. 所以先插入一个(0, 0)预处理.
    • 用map实现的状压感觉好厉害…
    • 还有记得该开long long的时候就开… 又在这里卡了一阵

赛后代码

A: https://code.csdn.net/snippets/619782

B: https://code.csdn.net/snippets/619742

C: https://code.csdn.net/snippets/619822


比赛结果

被hack的非常慘, 事实上还是自己弱

BestCoder-Round#33

$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('

    ').addClass('pre-numbering').hide();
    $(this).addClass('has-numbering').parent().append($numbering);
    for (i = 1; i ').text(i));
    };
    $numbering.fadeIn(1700);
    });
    });

    版权声明:本文博客原创文章,博客,未经同意,不得转载。

    上一篇:flex 客户端缓存SharedObject


    下一篇:windows上MongoDB远程访问配置