loj#6508. 「雅礼集训 2018 Day7」B

原题传送门:>Here<

我们发现有性质$(a,n)=1$,也就是说,$a\cdot i+b \mod n$的取值不会重复。

我们考虑对$S[0\cdots m-1]$建线段树,线段树下标为$a\cdot i + b\mod n$,存储的值是当前区间内$T$上对应位置为$1$的数的个数。

这样说可能有点抽象,我详细说明一下。

以样例为例:

1
2
3
9 5 6 4 3
101
...

构成的$S$的$a\cdot i+b\mod n$数组的前$m$项为

luoguP4385 [COCI2009]Dvapravca

原题传送门:>Here<

我们考虑随机选两个点,然后连一条经过这两个点的直线,并向两边扩展。做10000组就可以AC了。

以上是乱搞做法。

我们考虑当平行线平行于$x$轴时怎么办。

在这种情况下,我们只要把点投影到$y$轴上,然后查询最长连续红点就可以了。

其实绝对位置不重要,所以我们只要把点对纵坐标排序就行了。

现在我们考虑旋转平行线。

每次我们只需要把点投影到与平行线垂直的直线上,然后查询最长连续红点。

我们发现旋转平行线时,当两个点构成的直线与平行线平行时,也就说明这两个点的投影重合。那么在旋转前后,两个点的位置会进行交换。

这可以用线段树来维护。

luoguP5072 [Ynoi2015]盼君勿忘

原题传送门:>Here<

本来是不会去做Ynoi的毒瘤题的。。。

但是为了珂朵莉怎么都要做一下!!!

不过谁让我水平太差。。。其他的那些神仙题都不会,只能做这道了。

hh

The article has been encrypted, please enter your password to view.

0112模拟赛 吃干饭

题目大意:选择$[l,r]$中的若干数异或起来(也可以不选),问答案有多少种可能。

首先此题有一个$r-l\le 10000$的部分分很显然,只要把所有数丢到线性基里就ok了。

现在我们考虑正解。

我们发现当一个数可以被比它小的数表示时,就不需要加入线性基中。接下来我们考虑减少加入线性基中的数字数量。

我们发现对于两个相邻的数,$(2n)\oplus(2n+1)=1(n\in \mathbb{N})$。

所以我们找到$[l,r]​$中的第一个偶数(设为$x​$),则从$x+3​$开始的所有奇数都可以被表示为

其中$y$为奇数。

这样在$[l,r]$的所有奇数中,只有$x-1$和$x+1$无法被这样表示。

以此类推,所有$\%4=2$的数也都是一样的:我们先找到第一个四的倍数$x$,然后把$x-2$和$x+2$加入线性基。

这样我们最多只需要加入$64\times 2$个数就ok了。

bzoj5405 platform

原题传送门:>Here<

我们考虑对原串反向建后缀自动机。这样后缀自动机上的每一个点表示的就是原串上的一堆前缀。

我们发现一个性质:这些前缀的排名必定是连续的。

我们考虑证明。

bzoj5403 marshland

原题传送门:>Here<

看到这个数据范围,果断选择网络流。

我们发现消掉偶数点是没有意义的,所以问题可以转化为:

每消掉一个奇数点,需要消掉两个互为对角的偶数点。

我们看到每次消掉两个点,考虑可以使一个点连源点,另一个点连汇点。

所以我们的算法就是:

  • 从源点向偶数行的偶数点连边;

  • 从偶数行的偶数点向相邻奇数点连边;

  • 从奇数点向相邻奇数行的偶数点连边;
  • 从奇数行的偶数点向汇点连边。

同时为了维护费用,奇数点需要拆点。

(偶数点其实是不需要拆点的,然而我脑残了。。。)

loj#6436. 「PKUSC2018」神仙的游戏

原题传送门:>Here<

我们发现$f(i)=0$,当且仅当存在一对01满足01间的距离为$n-i$的倍数。这样就可以得到第4个部分分了。

我们考虑优化这个过程。

定义$A_i=[s_i=0]$,$B_i=[s_i=1]$。

现在我们想要使得

我们考虑翻转$B$,即使得

这样就变成

这样就OK了。

luoguP3321 [SDOI2015]序列统计

原题传送门:>Here<

定义$f$为$S$的生成函数。

则答案为

其中多项式卷积定义为

这个卷积比较难做。

我们发现出题人给了一个性质:$M$为质数。因此$M$必定有原根。

所以$1\cdots M-1$中的每一个数都可以被表示为原根的整次幂。

我们定义

则卷积就变成

答案就变成

此文章已加密

The article has been encrypted, please enter your password to view.
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×