BZOJ – Tgotp-Blog

4128: Matrix

简单观察即可发现用BSGS大力可做,然而算了算复杂度O(\sqrt p * n^3)炸掉了

此时用随机化的思想,生成一个1*n的矩阵,乘上原矩阵,即可少一个n,然后正常做即可.

c++代码如下:

 

5372: [Pkusc2018]神仙的游戏

这题务必用fft写,反正ntt我bzoj一直tle,loj 8s

做这题首先要知道一个性质,如果选取长度为len的串,那么该串可行,一定满足不存在一对 01,其距离相差len
(X而不是一开始我想的类似 另外一个fft的题...
那么如果存在一对01其距离差为len,那么对于所有k|len[......]

Read more

4653: [Noi2016]区间

水题,离散化一波然后线段树。

c++代码如下:

 

3329: Xorequ

打表发现对于2^x是个答案构成斐波那契数列

2^n直接 矩阵快速幂即可。

考虑n,通过打表也可以发现其实质就是数以二进制形式表示,没有任意相邻两位同为1,那么可把n分为多个x^n次方来搞,

如果有两位相邻,就跳过较小那位,搞定。

c++代码如下:
[crayon-5b4e0[......]

Read more

5313: 新Fib数列

很明显在%5的意义下只会有 0 1 2 3 4 这几个取值

且由于fib数列由前两项推出,那么很显然打个表就行了,,,

c++代码如下:

 

2018年5月7日 0 / /
Tag:  No Tags

2400: Spoj 839 Optimal Marks

发现异或每一位是互相独立的,且每一位只有 0 1取值

考虑网络流,显然是个最小割,

并且答案要最小,那么把s2 + 1 即可.

c++代码如下:

 

2396: 神奇的矩阵

一开始想了个fft 时间复杂度 O( t * n^2 log\ {n^2}) 应该超时了...
然后看了题解... 随机化...
c++代码如下:

 

4576: [Usaco2016 Open]262144

直接放聊天记录了...

Tgotp 2018/5/5 21:37:43

令f[i][j]表示

Tgotp 2018/5/5 21:37:55

第i个位置构成j需要几个位置

Tgotp 2018/5/5 21:38:07

首先

Tgotp 2018/5[......]

Read more

2018年5月5日 0 / /
Tag: 

3670: [Noi2014]动物园

仔细看完题以后,发现肯定和kmp有关,先搞出 next 数组

然后发现答案就是某一个next <i/2时的值

但是这个样子的话极限情况时n^2,发现瓶颈在于找next,然后考虑倍增一下就出来了.

注意卡常

c++代码如下:
[crayon-5b4e0d6adbfb24[......]

Read more

3083: 遥远的国度

唔,没初始化 wa了一次…
思路很一眼。
就是说 考虑 树剖
如果 查询点是首都的祖先,那么查询点构成的子树就是 整个树除了 查询点包含 首都的儿子以外所有点。
那么 知道一个子树在树剖上是连续一段区间, 即 现在需要求 出 包含首都的那棵子树的根,
用类似倍增lca的方法即可。
对于查[......]

Read more