竞赛讨论区 > 【题解】牛客IOI周赛17-提高组

【题解】牛客IOI周赛17-提高组

头像
Deep_Kevin
发布于 2020-06-06 21:58:53 APP内打开
赞 0 | 收藏 0 | 回复1 | 浏览454
相信大家在这次比赛中获得了很愉(zi)悦(bi)的体验。

T1

      题意大致就是给出一棵白色边的树和一堆黑色边,要你求割掉一条白色边和一条黑色边,使得星星恰好被分成两部分的方案数。
      这题就是题面太长了来恶心人的,但是善良的出题人已经把重点部分表明出来了,这个东西就可以直接对于黑边,用树上差分做了。
      当割掉一条白边时,如果连接两边的黑边只有一条,那么就有一种方案,如果没有,那么断任意一条黑边都是可行的,否则,就没有方案。
      当然也可以有更多其他的方法,log^2的也给过了。

T2

      题意明显,发现有a,b<=1的数据点,选择打表找规律,发现
      然后继续找规律,发现,递推输出即可,考虑到大部分人都会矩阵优化,就没有把n开到更大。
      教练,我不会找规律
      也是可做的,其实很多人都写了NTT,主要是依据这样的一条式子:,把模数开到998244353也是为了误导大部分人写NTT。😁
      
      那么你就可以获得60分的好成绩,加上数据里面有a=1,b=0这样简单的点,就可以获得70分的好成绩。
      这样已经十分接近正解了,我们尝试用a,b,x将F表示出来:
     
      Ans(x)是ans的母函数。
      把它像f转换过来一样转换回去,就可以得到ans的递推式了。
      教练,我不会生成函数
      如果你的数学学的足够好,其实可以直接脑子里面想一个这样的东西:
      fi表示一步走i格的方案数是多少,那么其实可以看成一共走n格,每次可以走至少一步,那么会形成一个步数集合{a1,a2,...,ak}(a1+a2+...+ak=n),那么使用这个步数集合的方案数就是
      考虑ans的实际意义,我们可以考虑给当前最后一步扩长两格或者扩长一格,或者新增一步。
      当你要扩长一格时,相当于从中转移过来,因为扩长一格的方案数是a。
      当你要扩长两格是,相当于从中转移过来,因为扩长两个的方案数是b。
      当你要新增一步时,相当于从中转移过来,因为新增的一步只能从1格开始,为什么?
      所以也可以得到答案的递推式。

T3

      这次撞题不能责怪出题人,真的没有碰到过。
      其实考虑补集转化后,只要求出一个交点和两个交点的组的方案数就可以了。
      想想一格交点的是什么样子的?肯定是线段的两个端点,一个在三角形里面,一个在三角形外面,这个可以直接用bitset来做,统计一个向量逆时针方向的点集合,然后枚举一个三角形,算内部的点就是按位与,时间复杂度
      两个交点的怎么算?可以用(全部方案的交点数目-一个交点的方案数)/2,考虑对于一个四边形,对角线一定有一个交点,有2*(n-4)种方案形成三角形(任意加一个点,然后分别与对角线形成三角形,求四边形个数跟上面的方法类似。
      减减就是答案。

1条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐