「算进」[基构]HASH

首先,「算进」是什么?
就是《算法竞赛进阶》,大神写的书,一个蒟蒻怎么能不好好磕一下呢,于是就有了这第一篇文章。
[基构]是什么?
就是基础数据结构的意思呢,基础不扎实就要好好学基构。
从我最不好的地方开始学习,来Hash把! ......  查看更多

Snowflake Snow Snowflake

Snowflake Snow Snowflakes
这题的话就是明显可以用哈希表来做啦,对于两篇形状相同的雪花,那么他们的乘积也是一样的,但是又为了避免偶然,所以哈希函数的计算中增加了他们的和,Hash(x)=sum(x)+mul(x)这样就可以很好的做统计了。

 ......  查看更多

[SHOI2015]自动刷题机

[SHOI2015]自动刷题机
一题明显的二分,只要两遍二分分别搞一下最大值何最小值就好。

[PA2014]Iloczyn

[PA2014]Iloczyn
因为斐波拉契数列到了50已经很大了,所以预处理50然后离线处理就好。

[PA2014]Lustra

[PA2014]Lustra
就是随便排序一下然后就取个最大值比较一下就好了呀。

[HAOI2014]贴海报

[HAOI2014]贴海报
就是简单的线段树加上离散化解决就好,但是也可以用分块做,留个坑
就是先离散化一下,然后用线段树维护区间值,然后线段树维护相同值就好。

Nim

Nim
把他想像成一条链,那么这题就是简单的SA问题,简单异或一下就好,这个在树上的话我们就套一下树链剖分然后异或就好,因为异或满足分配率。
此题卡常,要优化一下,然后各种registedinline搞搞就好

 ......  查看更多

[SDOI2016]生成魔咒

[SDOI2016]生成魔咒
这题就是SAM后缀自动机的基本操作了。
对于当前新增节点x的操作,每次对ans的贡献就是dep[x]-dep[fail[x]],
x<=10^9怎么破,数组开不够大呢,那么我们就用map代替就好了呀

2018-4-13模拟赛:解题报告

比赛题目

2018-4-13模拟赛:A 2018-4-13模拟赛:B 2018-4-13模拟赛:C 2018-4-13模拟赛:D

解题概况

今天是休假后的第一场比赛,所以呢,很多东西都很陌生,这样的话我觉得我还是好好复习文化课吧,不存在的,那么,还是认真的写一下题解吧,加油。

解题详情

2018-4-13模拟赛:A

这题的话其实正负数没什么区别的呢。
最优的策略一定是尽量少走回头路,尽量往终点的方向跳。我们先一直跳,跳到已经超过终点,且离终点的距离为偶数时的步数即为答案,因为此时可以通过调整前面一些跳跃的方向,使得我们刚刚好到达终点,为什么呢?
当没有到达终点时,显然不行。
当超过终点且离终点的距离为奇数时,假设当前的位置在pos,若我们把之前往终点跳x距离的一步改为往终点的反方向跳x距离,那么我们的位置就到了pos-2x,只能到离当前位置为偶数距离的地方,并不能到达终点。
同理,当超过终点且离终点的距离为偶数时,我们就可以通过调整之前某些跳跃的方向,到达终点。
AcceptCode ......  查看更多

2018-4-13模拟赛:D

2018-4-13模拟赛:D
假如可以快速预处理出所有点的最远点那么就可以O(1)回答了。
有一个经典的树形dp套路就是dfs两遍,第一次维护子树内的信息,第二次求出答案(包括子树外)。
具体的实现/理解方法很多。对这题而言,在第一次dfs的时候求出子树内的最长链和次长链(这两条链需要从不同的儿子转移过来)。
然后再做一次dfs,这次要用fa更新儿子,假如最长链就是由这个点转移过来的话就用次长链更新,否则就用最长链。
因为上一问太水,所以强行套了个单调队列……
求极值不超过m的最长子串应该是单调队列的经典操作。
考虑双指针,因为r右移时l也是单调右移的,所以用两个单调队列得到l即可,一个单调上升,一个下降。
假如您nlogn过了那我也没办法…… ......  查看更多