2021-team12-003

从 Trac 迁移的文章

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

原文章内容如下：

 [/wiki/2021-team12 返回]

[[Image(rank.jpg,1000px)]]
[[Image(submit.png,1000px)]]
= 概述 =

 solved: 7/11

 rank: ??

= 流水账 =

今天开场gym开了C发现是一道有点繁琐的模拟, PaperCloud看H, xLLLx看榜开了I, '''I1Y15'''。之后看榜PaperCloud开了E, xLLLx开了F, 之后E, F各wa了一发。xLLLx发现并查集没有更新改了发交了'''F2Y48''', PaperCloud发现E可能卡精度改了下交了'''E2Y49'''。在gym写C的时候, xLLLx读了A, PaperCloud读了G。gymC写好由于一个小错误wa了一发, '''C2Y64'''。PaperCloud会了H，gym会了G。期间G的题意看假过一次。xLLLx看榜读J想题罚坐。gym过了G '''G1Y110'''. PaperCloud继续写H. 胡出A题做法后gym去码了A. PaperCloud过了H '''H1Y158'''. 处理好细节后gym过了A '''A1Y168'''. xLLLx读完K。过完7题后瞬间rk上升 接下来的时间PaperCloud想K. gym和xLLLx胡了个J题方向 但细节不会处理。gym又读了D。继续口胡D,交了一发wa了。PaperCloud接过J，比赛结束没过样例。
= 总结 =

=== PaperCloud： ===

觉得今天总体的表现是挺好的。感觉我们每场都在进步。

罚时的次数也很小。

看错了G的题意，多亏Gym，不然可能要在错误的方向上浪费好多时间。（不能看着样例自己臆想题意）

后期有点垮，但是菜是原罪。中间潜水了好久想K，本来应该多去看些其他的题目。

应该多参加讨论。

码力还是很弱，还要继续复健。

=== xLLLx： ===


今天开场看榜过了I，然后才开了EF，看榜不够及时。

写F的时候并查集忘记最后更新，忘记了之前常踩的坑。

最后抱着队友的大腿过了最后两个小时。

最后的两小时不能说是一点思路没有，但也确实没有想到比较好的解决办法。

做题能力和代码能力还需要提升。

=== gym： ===
今天签到慢了一些，开始的时候我去看了C题，可能剩两个人看题目会慢一点，以后反应应该迅速一些。（但是我们应该3个人一起签到吗？我以为两个人看签到题，一个人去想稍微难一点的题是比较合理的。）

C题我因为脑子不清楚Wa了一发，非常不应该

一小时到三小时之间做了4题，速度还算合理。对A题印象比较深刻，因为这题细节比较多，虽然思路很清晰，但还是卡了有一会儿的，在处理细节上我确实不太擅长。

后来两小时一题都没有写出来，j题两个人一起想了很久，但是遇到了一个障碍，一直没有解决掉。D题最后一小时写的，码了半小时左右，速度还行，但是质量不高，到最后还是有bug

其实今天是三场里表现最好的一次了，罚时不多，甚至曾经rank很高过，可惜后继无力了。还要继续加油！


= 题解 =

 * A：
一个结论：如果一个人的分数加一 只有原本与他排名相同的人排名会有变化

每次更新，维护所有分数的排名 原分数的排名+1，现分数排名不动（继承原分数的排名）或者现分数已存在（不需要修改） 

这个排名可以使用到下一次排名变动 （变动可能是本人分数+1或是同分的人分数+1） 

记录某个分数的排名上一次改动的时间 每次该分数排名改变 先给这个分数的val数组加上t*rk

每次更新一个人的分数时将原分数的 val加入其ans，加入方式类似差分 

最后要全部更新一遍 

最多只有1e6次操作 


 * B：

 * C：

 * D：

 * E：

考虑新加进来的数无限大或者无限小的情况算必win或必不win。

如果有可能win直接使用中间的两个数。

 * F：

对数值离散化 对于每个数存入包含它的人

然后对于包含同一个数的人不在一个集合里就用边连起来。

并查集维护下就好了。
 * G：

 * H：

考虑询问很小，可以直接对每个询问在线回答。

发现所选的线段一定有一头在整点上，否则可以通过移动完成。

对每个左端点找符合条件的右端点，或者对每个右端点找符合条件的左端点。

符合条件要求，h[i]-ik<=h[j]-jk

直接按上式子排序，从大到小插入即可。

找到符合的端点后还要考虑是否可以再加入非整段。

 * I：
找到递减的相邻两个值往两边扩充找到最长不递增序列倒置

倒置后还是不行说明impossible

 * J：

首先处理掉有0且不进行create的情况。

考虑从小到大create的次数，为num1。

那么有一部分点可正可负。

每次新加入一个新的可正可负的数时，更新它的贡献。

先减去它会影响的区间的原贡献。

再加上它的新贡献。

贡献指的是本区间最多可以有多少交错的组。

总交错的组数记为num2。

ans=num1*c+(n-num)*r

upd:

num表示一个区间中需要删除的数量

左右端点用类似链表的办法处理，并且只需要维护非自由点即可。

总结：

原先的做法中，num表示的区间中最多能有多少交错的组

事实证明这样子维护明显要麻烦很多（对于每一个数字将它变成自由数前都要考虑它是否曾对num产生贡献）

原先的做法中，非自由区间的左右端点是用并查集来维护的。

容易出错且不必要。

 * K：

[/wiki/2021-team12 返回]

概述

solved: 7/11

rank: ??

流水账

今天开场gym开了C发现是一道有点繁琐的模拟, PaperCloud看H, xLLLx看榜开了I, I1Y15。之后看榜PaperCloud开了E, xLLLx开了F, 之后E, F各wa了一发。xLLLx发现并查集没有更新改了发交了F2Y48, PaperCloud发现E可能卡精度改了下交了E2Y49。在gym写C的时候, xLLLx读了A, PaperCloud读了G。gymC写好由于一个小错误wa了一发, C2Y64。PaperCloud会了H，gym会了G。期间G的题意看假过一次。xLLLx看榜读J想题罚坐。gym过了G G1Y110. PaperCloud继续写H. 胡出A题做法后gym去码了A. PaperCloud过了H H1Y158. 处理好细节后gym过了A A1Y168. xLLLx读完K。过完7题后瞬间rk上升 接下来的时间PaperCloud想K. gym和xLLLx胡了个J题方向 但细节不会处理。gym又读了D。继续口胡D,交了一发wa了。PaperCloud接过J，比赛结束没过样例。

总结

PaperCloud：

觉得今天总体的表现是挺好的。感觉我们每场都在进步。

罚时的次数也很小。

看错了G的题意，多亏Gym，不然可能要在错误的方向上浪费好多时间。（不能看着样例自己臆想题意）

后期有点垮，但是菜是原罪。中间潜水了好久想K，本来应该多去看些其他的题目。

应该多参加讨论。

码力还是很弱，还要继续复健。

xLLLx：

今天开场看榜过了I，然后才开了EF，看榜不够及时。

写F的时候并查集忘记最后更新，忘记了之前常踩的坑。

最后抱着队友的大腿过了最后两个小时。

最后的两小时不能说是一点思路没有，但也确实没有想到比较好的解决办法。

做题能力和代码能力还需要提升。

gym：

今天签到慢了一些，开始的时候我去看了C题，可能剩两个人看题目会慢一点，以后反应应该迅速一些。（但是我们应该3个人一起签到吗？我以为两个人看签到题，一个人去想稍微难一点的题是比较合理的。）

C题我因为脑子不清楚Wa了一发，非常不应该

一小时到三小时之间做了4题，速度还算合理。对A题印象比较深刻，因为这题细节比较多，虽然思路很清晰，但还是卡了有一会儿的，在处理细节上我确实不太擅长。

后来两小时一题都没有写出来，j题两个人一起想了很久，但是遇到了一个障碍，一直没有解决掉。D题最后一小时写的，码了半小时左右，速度还行，但是质量不高，到最后还是有bug

其实今天是三场里表现最好的一次了，罚时不多，甚至曾经rank很高过，可惜后继无力了。还要继续加油！

题解

  • A：

一个结论：如果一个人的分数加一 只有原本与他排名相同的人排名会有变化

每次更新，维护所有分数的排名 原分数的排名+1，现分数排名不动（继承原分数的排名）或者现分数已存在（不需要修改）

这个排名可以使用到下一次排名变动 （变动可能是本人分数+1或是同分的人分数+1）

记录某个分数的排名上一次改动的时间 每次该分数排名改变 先给这个分数的val数组加上t*rk

每次更新一个人的分数时将原分数的 val加入其ans，加入方式类似差分

最后要全部更新一遍

最多只有1e6次操作

  • B：
  • C：
  • D：
  • E：

考虑新加进来的数无限大或者无限小的情况算必win或必不win。

如果有可能win直接使用中间的两个数。

  • F：

对数值离散化 对于每个数存入包含它的人

然后对于包含同一个数的人不在一个集合里就用边连起来。

并查集维护下就好了。

  • G：
  • H：

考虑询问很小，可以直接对每个询问在线回答。

发现所选的线段一定有一头在整点上，否则可以通过移动完成。

对每个左端点找符合条件的右端点，或者对每个右端点找符合条件的左端点。

符合条件要求，h[i]-ik<=h[j]-jk

直接按上式子排序，从大到小插入即可。

找到符合的端点后还要考虑是否可以再加入非整段。

  • I：

找到递减的相邻两个值往两边扩充找到最长不递增序列倒置

倒置后还是不行说明impossible

  • J：

首先处理掉有0且不进行create的情况。

考虑从小到大create的次数，为num1。

那么有一部分点可正可负。

每次新加入一个新的可正可负的数时，更新它的贡献。

先减去它会影响的区间的原贡献。

再加上它的新贡献。

贡献指的是本区间最多可以有多少交错的组。

总交错的组数记为num2。

ans=num1*c+(n-num)*r

upd:

num表示一个区间中需要删除的数量

左右端点用类似链表的办法处理，并且只需要维护非自由点即可。

总结：

原先的做法中，num表示的区间中最多能有多少交错的组

事实证明这样子维护明显要麻烦很多（对于每一个数字将它变成自由数前都要考虑它是否曾对num产生贡献）

原先的做法中，非自由区间的左右端点是用并查集来维护的。

容易出错且不必要。

  • K：
附加文件