洛谷2017春节联欢赛 Hello Dingyou 比赛结果&题解

回复帖子

@Created_equal1  管理员 2017-01-30 22:22 回复

恭喜@Claris 获得Rank1并以700分满分的成绩AK!Claris将可以获得"化物语"L型文件夹一个(挂号信包邮)。

神秘奖励获得者:本场比赛分数与201.7最接近的选手

恭喜@zhouyonglong 获得神秘奖励——舰娘的手机链(挂号信包邮)

所有在本场比赛中获得209分以上的选手均可以获得洛谷最新版的明信片一张。

奖品收取地址:奖品

@q234rty 2017-01-31 21:31 回复 举报

%%% 说某题是原题大概是因为[USACO09FEB]庙会班车Fair Shuttle这题吧233

@kczno1 2017-02-01 10:49 回复 举报

最后一题:"分块,预处理任意两块之间的bitset,然后每个询问只需要加入log个数就可以了",为什么是log个数而不是根号个数

@q234rty 2017-02-01 12:03 回复 举报

@kczno1 大概是类似于容斥一样的东西?对于每个子集,有奇数个数就乘上它们的gcd,有偶数个数就除以它们的gcd

@q234rty 2017-02-01 14:12 回复 举报

@kczno1 出现过的gcd数量很少,考虑用一个map维护每个出现过的gcd的出现次数%mod-1的值,每次添加一个数时把每个出现过的gcd跟这个数取gcd,然后更新一下?

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。