当前位置: 代码迷 >> 综合 >> 2018ACM/ICPC全国邀请赛(江苏)总结 - i-Curve
  详细解决方案

2018ACM/ICPC全国邀请赛(江苏)总结 - i-Curve

热度:26   发布时间:2023-12-25 18:49:27.0

    在这场比赛中我首先看的是b题,lqs和xzq看的是a的,他们弄懂a题的题意后,想了一会有了思路,然后给我讲述并问我可不可行,我感觉可行,然后一起讨论具体实施,刚开始是让我上去敲的,他们两个想的是用优先队列,我用的不熟,如果要用的话我就用用结构体,但是我想了想,好像用优先队列敲得会更快点,然后xzq说他敲然后,我继续看题,然后lqs看了d题,我刚开始以为b题是要推一个公式,然后就开始在推b题。过了一会,xzq敲完了a题然后交了一发,T了,然后开始改进,lqs说弄明白了d题和我简单讲了一下是一个大的阶乘除法,最后取余,然后开始上去敲,这时我也推出了b题,发现也是用阶乘,然后我就看lqs的提交,并告诉他一会不要删除。最后,lqs敲完后,交了一次,W了。这是仔细想了想,发现除法取余的话和乘法是不同的,不能用那种方法,然后我就开始一直想除法怎么取余(注意:除法不存在取余的(0^v^0)~~),由于我印象中没有除法取余的题,因此,我开始一直用数学的方法推,看能不能推出来。lqs也想了一会,就开始看别的题了。过了一会,lqs看完j题后给我讲了一下,我简单理解了一下题意,没有什么直接的思路,然后我就没有深入想,继续推除法的取余公式了。

    然后,我们就一直在这里耗费时间了,一直等到午饭发下来,我们还没有A题,每个人也都比较紧张,害怕会在这种时候爆零,我吃完饭,发现xzq还在考虑a题,然后我就想最初想的这种方法也没有问题啊,为什么会T啊,然后我了一下他,然后他很确切的告诉我确实会T,然后还给我演示了一下他计算的复杂度,我一听,顿时感觉有点不对劲啊,他怎么复杂度都算的错的。然后我就停止了对话开始看他写的代码。刚开始我想看了一眼,由于代码风格不一样,我想自己写下的,不过仔细一想现在都什么时间了,再写都到什么时候了,然后就开始硬着头皮看他的代码。看完之后我还真的发现了一个问题,这其中有一个步骤是要把一个数组转移到另一个数组中,我发想他是在用装完一个删除一个数组空间的方法,我问他为什么这样写,他说不就是这样写的吗?以前就是这样写的。然后就说这样写会很浪费时间的呀,然后我就开始改他的代码,xzq就去和lqs讨论别的题了,过了一会我改完了xzq的代码,交了一次A了。

    这是后时间已经过去了3个小时左右了,我又看了一下手中推了半天的公式,发现不能再在这里耗时间了,我们到现在才之A了题,然后我就开始全心的准备别的题了,跟了下榜发现d题和j题做的人比较多,由于d题还在卡中,然后我就看j题,刚开始看了一会,发现j题可以用一个vector类型去存储,然后和他们讨论了一下,发现可行,我就开始理清思路准备上去敲,刚准备好,发现了问题,如果用数组的,发现到后面会数会多的存不下。然后我就开始想别的方法。想了一会,找到了其中具有dp的线索,应该是那种简单的一维dp,然后简单想了一下感觉可行,我就给lqs说了一下可能用dp,他感觉也是要用到dp然后我就开始推dp公式。过了一会推出了公式,然后我简单的验证了一下,可行,然后我给lqs简单的说了一下,我就让他继续验证我急忙的直接开始敲代码,我很快的敲完了到吗,lqs说了一个说让我验证,输入进去可行,然后又说了一个很大的数,发现输出是-1,然后我就开始吧这里面的所有答案按顺序输出,发现数据增长的很快,然后很快就爆了数据范围。这是lqs说可能要用大数,我一听一脸懵逼,大数,我虽然听学长说过,但是我从来没想过真的会出,我也就没敲过,然后以为一问我们三个人,发现我们三个都不会。然后打开ecilipse开始摸索,由于xzq的java学得比较好,然后让他去摸索,摸索了一会他说开始手动模拟。我和lqs开始看别的题,这时局比赛结束大概还有半小时,然后我俩就又想到了d题感慨,不知如何对大数的组合数阶乘算法使,xzq突然一说,组合数?我有模板法,我和lqs顿时吃惊,模板........。然后我就上去用模板敲d题,过了一会交了一次,A了。然后由于我之前推过b题,然后是卡在了大数的阶乘上,然后我继续敲b题交了一次,W了。我发我的公式推错了,然后继续让xzq去模拟,然后这是时间大概就剩10分钟了,xzq模拟了继续去敲。最后也没敲完。

    最后一个简单的总结,这次对我来说最大的意外是题的范围,大数和组合数这些我完全没想过会出,因此也从为敲过,不过,这场比赛中我感到自豪的是全程我都在思考,没有挂机。这次也算是一个教训吧,努力扩展自己的知识吧。奋斗,努力(0^v^0)~~

  相关解决方案