2017-Sp67-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,500px)]]
 * 题目来源：XVIII Opencup, Grand Prix of Khamovniki, MosCode Fest Online Round
 * Camp&现场排名：https://official.contest.yandex.com/itmo2018china/contest/7384/standings/
== 流水账 ==
开场各自看题，不久后A和C各有人过，yzc和sub讨论了下A就上机写，cjb和sub讨论了下C也确定了做法。A写了一会儿，之后 wa了，yzc打印检查，cjb上机写C，C wa了一发后很快找到了错误，'''C2y89'''。之后三个人又花了一会儿研究A，结果还是wa。sub想好了K，无奈之下决定放弃A，sub上机写K。cjb和yzc研究H，很快提出了做法。sub的K获得wa，sub下机思考，yzc上机写H，很快也获得了wa。sub找到了错误，修改后'''K2y132'''，cjb提出了一个bug，修改后'''H2y140'''。接下来cjb和yzc研究F，sub推G。之后sub上机获得G的wa。cjb和yzc接力写F，sub多次上机调试G，之后'''G2y225'''。F过了样例后'''F1y250'''。过G后sub研究I，最后'''I1y275'''。最后20min三个人一起研究A，多次提交无果，以非常规的6题结束了比赛。
== 总结 ==
=== chenjb ===
  * A题是我和yzc的责任，我们俩对于博弈dp不够熟悉导致掉进了naive的陷阱，之后两个人都要做博弈dp的专题训练。
  * 这几天开场我们状态都不是很好，不能马上进入状态，除了休息要好之外，要多组织正规时间的训练。
  * 6天下来，只要发挥正常都是属于第二梯队的位置，但是遇到一点小问题就会掉下来一档，所以基本看到了目前自己的上限和下限，上限要强调个人刷题和坚决补题，下限的话，就是要多训练，而且要多做难题，多做毛题。
  * 吸取了之前的教训，今天A卡太伤的时候，及时放弃，把另外的几个题都做出来了，双开也非常稳健，dirt率其实还算优秀，算是一次比较好的经验。
  * 有些时候题目过不掉，一定要问自己：题目读对了吗，算法真的对吗，要分清楚隔靴搔痒和一针见血的区别，敢于去推翻。
  * 在camp中看到了自己其实还是非常naive，有一定的经验，但是还不足以应付各种各样的情况，wood cube不仅是个人实力优秀的队伍，他们真的非常老练，要向他们多学习。
  * 目前盯着Nightfall看吧，心中对自己基本有个定位。
=== oipotato ===
菜菜。。。
=== subconscious  ===
== 题解 ==
 * A：
   * 题意：玩dota的技能征召模式，每个技能有一个值，两队都希望自己选的技能的值的和减去对面的尽量大。
   * 题解：f[i][mask]表示从第i轮往后，mask中对应位为1的人不能选大招的最大值，从后往前转移即可。
 * D：
   * 题意：给定n个二元组(a,b)，按顺序加入序列，假如当前序列已经有l个元素了，那就可以插在第[l+1-a,l]个元素之前，但是还要满足插入位置的两边至少有一边的b值与当前相同，否则插在序列尾部。求最终序列。
   * 题解：容易发现相同b值的元素若在序列中连续，则可以缩成一块，不影响插入操作。考虑使用线段树维护不同b值的段，并且对于每一种b值，维护一个vector表示对应b值的每一个段的编号。插入新元素时，去检查恰好在l-a位置，即能插入的最后一个位置的前一个位置对应的段的序号，如果我们保证了vector的有序性，那么就可以在当前元素对应的b值的vector中二分，找到自己属于的段插入，并记录自己当前插入的是哪个位置，同时维护段的size。假如没有段可以插，那么就只能插在末尾，也就是产生了一个新的段，并在对应vector当中加入新编号，那么显然vector是有序的。以上操作均可以用线段树很方便的维护。对于答案序列，我们考虑通过每个元素的插入位置来推出它最终实际所在位置。假设我们从后往前做，那么在做到第i个人的时候，假设它当时是插到了第k个位置，那也就是说，编号在它前面有k-1个人实际位置在他之前，而对于编号在它后面的，我们已经处理完了，所以我们只需要在剩余的位置中挑第k大的给他即可。这也能很方便的用线段树维护出来。
 * E：
   * 题意 & 题解 [[BR]][[BR]]   [[Image(E.png,1300px)]]
  * J：
   * 题意：两个楼梯，n个人要上楼，每个人有一个走完楼梯的时间，但是如果一个人前面的人到底比他晚，那他就要走得慢一点，最后和前一个人同时到，这样他就会晚t时间到，于是他就会骂t句脏话，求所有人骂的脏话的和的最小值。
   * 题解：一个显然的dp方程是f[i][j][k]表示前i个人，第一个楼梯的最大值是j，第二个是k的答案，显然，前i个人的最大值一定会是j，k中的一个，于是可以将方程简化为f[i][j]表示前i个人，最大值是一个楼梯的最大值，第j个人是另一个楼梯的最大值时的答案。写出所有f[i-1]到f[i]的转移可以发现，我们需要维护的是一些区间加减，区间求最值，插入一个节点，还有区间每个节点加上自己下标的操作，前几个操作均很容易用平衡树维护，对于最后一个操作（以下称为Raise操作），容易发现平衡树中的节点对应的答案是递减的，而一个下标更大的节点超过下标小的节点之后无论怎么进行Raise操作，均会一直超过，至于其他操作则显然不影响相对的差，所以只需用线段树维护平衡树中所有节点答案会超过前一个节点的时间并及时删除即可。
   * UPD：对于相邻两个点x,y，上述的y被删除的时间虽然x答案更小，但是不能保证一直更小。但是考虑x答案重新超过y的时候，一定是插入了一个x到y之间的人，这个人的dp值是上一次前缀的最小值，这个值小于上一次x的值更小于y的值，所以y依然可以被删掉。
 * [https://wiki-nightfall.icpc-camp.org/Day6 Solution by Nightfall]
== 补题 ==
 * ~~A~~ by yzc
 * B
 * ~~D~~ by yzc
 * ~~E~~ by sub
 * ~~J~~ by yzc

  • 题目来源：XVIII Opencup, Grand Prix of Khamovniki, MosCode Fest Online Round
  • Camp&现场排名：https://official.contest.yandex.com/itmo2018china/contest/7384/standings/

流水账

开场各自看题，不久后A和C各有人过，yzc和sub讨论了下A就上机写，cjb和sub讨论了下C也确定了做法。A写了一会儿，之后 wa了，yzc打印检查，cjb上机写C，C wa了一发后很快找到了错误，C2y89。之后三个人又花了一会儿研究A，结果还是wa。sub想好了K，无奈之下决定放弃A，sub上机写K。cjb和yzc研究H，很快提出了做法。sub的K获得wa，sub下机思考，yzc上机写H，很快也获得了wa。sub找到了错误，修改后K2y132，cjb提出了一个bug，修改后H2y140。接下来cjb和yzc研究F，sub推G。之后sub上机获得G的wa。cjb和yzc接力写F，sub多次上机调试G，之后G2y225。F过了样例后F1y250。过G后sub研究I，最后I1y275。最后20min三个人一起研究A，多次提交无果，以非常规的6题结束了比赛。

总结

chenjb

  • A题是我和yzc的责任，我们俩对于博弈dp不够熟悉导致掉进了naive的陷阱，之后两个人都要做博弈dp的专题训练。
  • 这几天开场我们状态都不是很好，不能马上进入状态，除了休息要好之外，要多组织正规时间的训练。
  • 6天下来，只要发挥正常都是属于第二梯队的位置，但是遇到一点小问题就会掉下来一档，所以基本看到了目前自己的上限和下限，上限要强调个人刷题和坚决补题，下限的话，就是要多训练，而且要多做难题，多做毛题。
  • 吸取了之前的教训，今天A卡太伤的时候，及时放弃，把另外的几个题都做出来了，双开也非常稳健，dirt率其实还算优秀，算是一次比较好的经验。
  • 有些时候题目过不掉，一定要问自己：题目读对了吗，算法真的对吗，要分清楚隔靴搔痒和一针见血的区别，敢于去推翻。
  • 在camp中看到了自己其实还是非常naive，有一定的经验，但是还不足以应付各种各样的情况，wood cube不仅是个人实力优秀的队伍，他们真的非常老练，要向他们多学习。
  • 目前盯着Nightfall看吧，心中对自己基本有个定位。

oipotato

菜菜。。。

subconscious

题解

  • A：
    • 题意：玩dota的技能征召模式，每个技能有一个值，两队都希望自己选的技能的值的和减去对面的尽量大。
    • 题解：f[i][mask]表示从第i轮往后，mask中对应位为1的人不能选大招的最大值，从后往前转移即可。
  • D：
    • 题意：给定n个二元组(a,b)，按顺序加入序列，假如当前序列已经有l个元素了，那就可以插在第[l+1-a,l]个元素之前，但是还要满足插入位置的两边至少有一边的b值与当前相同，否则插在序列尾部。求最终序列。
    • 题解：容易发现相同b值的元素若在序列中连续，则可以缩成一块，不影响插入操作。考虑使用线段树维护不同b值的段，并且对于每一种b值，维护一个vector表示对应b值的每一个段的编号。插入新元素时，去检查恰好在l-a位置，即能插入的最后一个位置的前一个位置对应的段的序号，如果我们保证了vector的有序性，那么就可以在当前元素对应的b值的vector中二分，找到自己属于的段插入，并记录自己当前插入的是哪个位置，同时维护段的size。假如没有段可以插，那么就只能插在末尾，也就是产生了一个新的段，并在对应vector当中加入新编号，那么显然vector是有序的。以上操作均可以用线段树很方便的维护。对于答案序列，我们考虑通过每个元素的插入位置来推出它最终实际所在位置。假设我们从后往前做，那么在做到第i个人的时候，假设它当时是插到了第k个位置，那也就是说，编号在它前面有k-1个人实际位置在他之前，而对于编号在它后面的，我们已经处理完了，所以我们只需要在剩余的位置中挑第k大的给他即可。这也能很方便的用线段树维护出来。
  • E：
    • 题意 & 题解

      • J：
    • 题意：两个楼梯，n个人要上楼，每个人有一个走完楼梯的时间，但是如果一个人前面的人到底比他晚，那他就要走得慢一点，最后和前一个人同时到，这样他就会晚t时间到，于是他就会骂t句脏话，求所有人骂的脏话的和的最小值。
    • 题解：一个显然的dp方程是f[i][j][k]表示前i个人，第一个楼梯的最大值是j，第二个是k的答案，显然，前i个人的最大值一定会是j，k中的一个，于是可以将方程简化为f[i][j]表示前i个人，最大值是一个楼梯的最大值，第j个人是另一个楼梯的最大值时的答案。写出所有f[i-1]到f[i]的转移可以发现，我们需要维护的是一些区间加减，区间求最值，插入一个节点，还有区间每个节点加上自己下标的操作，前几个操作均很容易用平衡树维护，对于最后一个操作（以下称为Raise操作），容易发现平衡树中的节点对应的答案是递减的，而一个下标更大的节点超过下标小的节点之后无论怎么进行Raise操作，均会一直超过，至于其他操作则显然不影响相对的差，所以只需用线段树维护平衡树中所有节点答案会超过前一个节点的时间并及时删除即可。
    • UPD：对于相邻两个点x,y，上述的y被删除的时间虽然x答案更小，但是不能保证一直更小。但是考虑x答案重新超过y的时候，一定是插入了一个x到y之间的人，这个人的dp值是上一次前缀的最小值，这个值小于上一次x的值更小于y的值，所以y依然可以被删掉。
  • Solution by Nightfall

补题

  • A by yzc
  • B
  • D by yzc
  • E by sub
  • J by yzc
附加文件