[HAOI2007]反素数ant&反质数加强版SAPGAP

这题其实和原来[HAOI2007]反素数ant是一道类似的题目,都是有DFS做,重点是在于有几个特殊的公式要先知道。

  1. 一个数约数个数=所有素因子的次数+1的乘积
  2. 一个2000000000以内的数字不会有超过12个素因子
  3. 较小的数的指数一定大于等于较大的数的指数

然后反质数加强版SAPGAP只要多预处理多几个质素然后就加个BIGNUMBER高精度跑一下爆搜就ok了,所以这题就精A算了。 ......  查看更多

「AHOI / HNOI2018」道路

2018-4-13模拟赛:道路
原本是最水的一题又因为题目啰嗦,题序不对好像当场只有两人A掉了呢。
但是这题的确很水,可惜我当场也是没想出来。
这题就是记忆化搜索啦!
我们用f[k][x][y]代表现在第k个节点,翻修x条公里,翻修y条铁路的最小代价,然后记忆化一下之后状态转移
f[k][x][y]=min(f[lc][x][y]+f[rc][x][y+1],f[lc][x+1][y]+f[rc][x][y]),lc,rc分别代表左右子树节点的编号。 ......  查看更多

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过了那我也没办法…… ......  查看更多

[ZJOI2010]count 数字计数

[ZJOI2010]count 数字计数
%%%静静 and 楠楠
这题就是数位DP的裸题,然而我还是要%题解,自己写的代码调不出来
f[i][j][k]表示若前i个位置有kj的此时的全局方案数
然后就是记忆化搜索