用户工具

站点工具


2020-2021:teams:farmer_john:2020-2021_buaa_icpc_team_supplementary_training_02

这是本文档旧的修订版!


比赛名称

A.

upsolved by

题意

题解

B.

solved by

题意

题解

C.

solved by Bazoka13

题意

一个2000*2000的矩阵,给定$n$条线段,询问这些线段一共经过多少个格子

题解

枚举横坐标,计算纵坐标然后染色即可

D.

solved by

题意

题解

E.

upsolved by

题意

题解

F.

solved by Bazoka13

题意

重排一个序列,使得相邻两项差的绝对值的最小值最大

题解

根据二分的想法推出应该是选择n/2个连续元素后放到奇数位,从结束位置开始循环放到偶数位,但是这种情况只适用于奇数,在自己$hack$了自己的做法后,尝试偶数就直接从中间分开进行插值居然过了(?)

G.

solved by Bazoka13

题意

给定一个集合,每个元素都有相应权值,求权值和第$k$小的子集

题解

利用优先队列,每次取出最小的元素后将最贵的换成更贵的或者直接加入更贵的

H.

solved by 2sozx

题意

给定一个第一象限简单多边形,问一条从原点出发的直线最多将多边形分成多少块。$n\le10^5$

题解

首先忽略掉三点共线的点,这样的点是没有意义的,之后对剩余的点进行极角排序,让直线逆时针扫这些点,将这些点分成四种情况。

I.

solved by Bazoka13

题意

每次选两个叶子节点染色,并将其路径上所有节点涂黑,进行该操作直到不存在两个路径上节点全为白色的叶子节点,求最小操作数

题解

显然每个子树可以拿出来一个与尽可能远的叶子节点进行配对,而剩下的叶子节点可能会存在必须进行配对的,那就可以分情况考虑

  • 如果叶子节点数为1的子树多于2,就拿出来两个配对
  • 如果叶子节点数为2的子树多于1,就拿出来一个配对
  • 如果叶子节点数为1的子树多于1并且存在叶子节点数为2的子树,就拿出来将二者配对
  • 显然剩下的叶子节点最多给父亲传递两个叶子节点

J.

upsolved by

题意

题解

记录

0min:开局分题
10min:MJX发现C是签到冲C
33min:MJX WA,CSK冲G
46min:CSK AC,ZYF冲A
55min:ZYF AC A,MJX继续冲C
83min:MJX WA2,换CSK写C,MJX ZYF看J
167min:J WA3,CSK冲I
186min:CSK AC I,ZYF继续看J,MJX看H,CSK 看F
230min:CSK WA
232min:MJX AC H,继续看J
285min:CSK AC F,一起看J
295min:CSK想到了正解冲J
till end :CSK没写完,由于inque多开了几分钟

总结

  • MJX要尽量避免精度问题
2020-2021/teams/farmer_john/2020-2021_buaa_icpc_team_supplementary_training_02.1596788955.txt.gz · 最后更改: 2020/08/07 16:29 由 bazoka13