csp-s模拟110

倒计时三天。

这场又是巨头们的AK场，大众分200+，貌似真实的csps？

然而T1又炸了，$1<<62$暴int，要$1ll<<62$。T2试图打70部分分，T3也只会40分，可能省一卡线了。

最近做题不认真，没有思考，思路一直是歪的，不想正解，太想乱搞。态度有点消极。

T1：

　　如果没有下界限制，一定是把R的每个$0$位或上$1$。有了$L$的限制，找到$L$和$R$从高到低位第一个不同的位，在此位一个数取$1$，其余往后全$0$，另一个数在此位取$0$，后面全取$1$即可让这一位后或起来全是$1$。

T2：

　　如果直接dp出随机答题者的得分概率，进行前缀和找出第一个大于等于$P$的位置即可。但是时间、空间双双超限。再转化一下，先把随机答题者的所有得分方案枚举出来，答案就是总方案数（$2^N$）乘上概率$P$（向上取整）的位置上的得分。直接枚举更是不行。而数据范围$N=40$可以考虑折半搜索。分别枚举得到用前一半题和后一半题的得分方案集合，接着求两个集合中取数之和的第$\lceil 2^N*P \rceil$大。二分答案。对两个集合排序，一边扫，一边用单调指针便可以$O(2^{\frac{N}{2}})$ $check$一次比$mid$小的个数。

T3：

　　合法点对就是距离为$2$并且不是三元环的点对。

　　对于求和，用一个小容斥。先求出任意距离为2的点对的联合权值，减掉三元环的。前者直接用一点权值成上相邻点的相邻点的权值和并减去自己重复的权值的平方。考虑如何找三元环。

　　一种方法是，先把原图构造成有向无环图：按（度数大小，点编号）的大小确定无向边的方向，然后便可以枚举起点，标记中间点，判断每个中间点是否可达另一个中间点。具体三层循环枚举点、边、点。前两层总和$M$，第三层是点的出度。实际上总的是所有有向边的终点的出度和。对于出度小于$\sqrt M$的点，枚举总和小于$M*\sqrt M$，对于度数大于$\sqrt M$的点，这样的点的数量不会超过$\sqrt M$，因为所有点度数和为$2*M$，这样的枚举总和也小于$M*\sqrt M$。所以三元环最多$M*\sqrt M$个，复杂度亦$O(M*\sqrt M)$。

　　还有一种不优秀的方法：$bitset$临接矩阵，压与某一点直接相连的点，枚举边，$bitset::count()$求相邻两点的相邻点的交集大小，减掉相应贡献。理论复杂度$O(\frac{N^2}{32})$。

　　对于最大值，从大到小枚举合法点对一定最优。排序相邻点。枚举中间点，找到第一个合法的最大点对就可以。最多枚举次数也就是三元环的数量。$O(M*\sqrt M)$。

　　由于点数多，边稀疏，判两点直接联通可以哈希/unordered_map压临接矩阵，两点压成30位整形。

巴特西

csp-s模拟110

T1：

T2：

T3：

最新文章

热门文章