跳至内容
CVBB ACM Team
用户工具
注册
登录
站点工具
搜索
工具
显示页面
修订记录
Copy this page
导出 PDF
反向链接
最近更改
媒体管理器
网站地图
注册
登录
>
最近更改
媒体管理器
网站地图
您在这里:
front_page
»
2020-2021
»
teams
»
farmer_john
»
2020-2021_buaa_icpc_team_supplementary_training_02
2020-2021:teams:farmer_john:2020-2021_buaa_icpc_team_supplementary_training_02
本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。
======2020-2021 BUAA ICPC Team Supplementary Training 02====== [[https://codeforces.com/group/azDPdoF24f/contest/290092|比赛链接]] =====A.===== **solved by JJLeo** ====题意==== 给定一个长度为奇数的序列,每次对一个区间进行升序排序或降序排序,问最后中间的数是啥。 ====题解==== 二分答案,然后将其它数字与他的大小关系变成$0$或$1$,使用线段树对$01$进行排序,最后看中间位置的数是否满足条件即可。 =====B.===== **upsolved by** ====题意==== ====题解==== =====C.===== **solved by Bazoka13** ====题意==== 一个2000*2000的矩阵,给定$n$条线段,询问这些线段一共经过多少个格子 ====题解==== 枚举横坐标,计算纵坐标然后染色即可 =====D.===== **upsolved by JJLeo** ====题意==== 给定一棵$n$个节点的树,每次等概率地选择一个节点,获得该节点所在连通块大小的权值,然后删除这个节点及其相连的边,重复$n$次操作,求期望权值。$(n \le 10^5)$ ====题解==== 考虑两个点$u,v$之间的贡献,只有当$u$到$v$路径上$v$是第一个删除的点,$v$才能对$u$产生$1$的贡献,设路径长度为$d$,则概率为$\dfrac{1}{d+1}$。因此答案转化为树上不同长度的路径各有多少条,其中长度为$0$的路径(即自己对自己的贡献)只用算一遍,长度大于$0$的路径要算两边(两者对互相都有贡献)。 具体做法为淀粉质+FFT,如果对于某一个分治中心,一个子树一个子树合并,很容易就被菊花图+一条超长链卡出TLE。因此需要使用容斥的思想,将所有子树的的贡献全部加在一起,只做一次FFT,这样会多算出每个子树内部自己和自己合并出来的答案,只需要处理每个子树过程中,将其内部的贡献做一次FFT减掉即可。这样FFT多项式的总长度是$O(n\log n)$的,因此总复杂度为$O(n\log^2 n)$。 =====E.===== **upsolved by** ====题意==== ====题解==== =====F.===== **solved by Bazoka13** ====题意==== 重排一个序列,使得相邻两项差的绝对值的最小值最大 ====题解==== 根据二分的想法推出应该是选择n/2个连续元素后放到奇数位,从结束位置开始循环放到偶数位,但是这种情况只适用于奇数,在自己$hack$了自己的做法后,尝试偶数就直接从中间分开进行插值居然过了(?) =====G.===== **solved by Bazoka13** ====题意==== 给定一个集合,每个元素都有相应权值,求权值和第$k$小的子集 ====题解==== 利用优先队列,每次取出最小的元素后将最贵的换成更贵的或者直接加入更贵的 =====H.===== **solved by 2sozx** ====题意==== 给定一个第一象限简单多边形,问一条从原点出发的直线最多将多边形分成多少块。$n\le10^5$ ====题解==== 首先忽略掉三点共线的点,这样的点是没有意义的,之后对剩余的点进行极角排序,让直线逆时针扫这些点,将这些点分成四种情况。{{:2020-2021:teams:farmer_john:加训第二天H.png?200|}}\\ 在扫到 $1,2$ 类点的时候块数会直接减一加一;扫到 $3,4$ 类点的时候继续移动块数会减一加一,但是刚扫到的时候并不会直接改变,可以通过叉积判断这四种情况。然而样例中给了一种特殊的情况。\\ {{:2020-2021:teams:farmer_john:加训第二天H2.png?200|}}\\ 此时下面这条线的两个点会被一起枚举到,并且此时的直线与这条线段重合,因此我们要避免重复计数的情况,取叉积的时候只在一侧添加等号。重合时还有一种情况时没有贡献的,只要调整叉积等号的取法即可,即如果一侧被计算到了,另一侧要减去,如果一侧没被计算到,另一侧也不会被计算到。 =====I.===== **solved by Bazoka13** ====题意==== 每次选两个叶子节点染色,并将其路径上所有节点涂黑,进行该操作直到不存在两个路径上节点全为白色的叶子节点,求最小操作数 ====题解==== 显然每个子树可以拿出来一个与尽可能远的叶子节点进行配对,而剩下的叶子节点可能会存在必须进行配对的,那就可以分情况考虑 * 如果叶子节点数为1的子树多于2,就拿出来两个配对 * 如果叶子节点数为2的子树多于1,就拿出来一个配对 * 如果叶子节点数为1的子树多于1并且存在叶子节点数为2的子树,就拿出来将二者配对 * 显然剩下的叶子节点最多给父亲传递两个叶子节点 =====J.===== **upsolved by JJLeo** ====题意==== 给定一个$01$序列,每次操作可以将一个字符移动到任意一个位置,问$k$次操作可以得到的连续$0$的最大长度。 ====题解==== 最优方案一定是将一个区间里的$1$挪出去然后再把一些$0$挪进来。\\ 然后我就莫名其妙将$01$绑定了,然后就莫名WA 4,直接葬送这把。\\ 设$sum_0,sum_1$分别为$0,1$的前缀和,答案为$\min(sum_0[n],sum_0[i]-sum_0[j]+k-(sum_1[i]-sum_1[j])$,要求区间内$sum_1[i]-sum_1[j] \le k$,直接单调队列即可。 =====记录===== 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 WA4,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要尽量避免精度问题 * CSK码力不够,最后五分钟有清晰思路的题都没有写出来,要继续锻炼 * ZYF全场梦游,J题看了三小时都没做出来,导致最后就差这一题,亏炸。下次要敢于换写法,不要沉迷于奇奇怪怪的做法。
2020-2021/teams/farmer_john/2020-2021_buaa_icpc_team_supplementary_training_02.txt
· 最后更改: 2020/10/07 21:25 由
jjleo
页面工具
显示页面
修订记录
反向链接
Copy this page
导出 PDF
回到顶部