BZOJ – Tgotp-Blog

4653: [Noi2016]区间

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

c++代码如下:

 

3329: Xorequ

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

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

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

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

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

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-5b083793d4bb61[......]

Read more

3083: 遥远的国度

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

Read more

4241: 历史研究

回滚莫队 ...
就是说对于这题来说,添加容易,但是删除困难,那么就不考虑删除,即把左右端点分别放在块的两边,中间的是可以直接处理出来,然后块中的暴力更新,完了以后再变更为更新前的状态即可.
复杂度O(n\sqrt {n})
c++代码如下:
[crayon-5b083793d51f[......]

Read more

2654: tree

容易想到,对于 当前这个图,如果要得到恰好need条边,且边权和最小,
那么就要控制白边在生成图中的数量…那么想到如果给所有白边加一个值,
跑克鲁斯卡尔的话白边数量就会变化,那么考虑二分即可。
c++代码如下:

 [......]

Read more

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