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

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

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

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

适者

适者

我这题也是膜dalao的题解,这题用的是CDQ分治,也有用李超树的做法,其实两个复杂度是一样的了,就随便学一种就好。
首先考虑若一个炮塔都没有被秒杀,那么怎么安排攻击顺序最好
对于两个炮塔uv,若u在前那么v将多产生d[u] \times a[v]的伤害,vu前那么u将多产生d[v] \times a[u],显然我们要使伤害最小,即
当u在v前时,满足d[u] \times a[v]<d[v] \times a[u],整理得\frac{d[u]}{a[u]}<\frac{d[v]}{a[v]},等式两边都只与u或者v相关,满足偏序,排序一发即可。
再来考虑从中拿两个走,记拿x走总伤害减少c[x]
我们需要找到最大的i,j使得在第一次排序中ij前面,且c[i]+c[j]-d[i] \times a[j]最小
考虑对于每一个j,寻找能使上述表达式值最大的i
即使得c[i]-d[i] \times a[j],将它看成a[j]为自变量的一次函数,最后的取值显然是一个下突壳,单调队列维护即可,CDQ分治递归下去即可
可能说的有点抽象,给一下主程序的步骤:
1. 递归处理左右区间
2. 右区间按a[]排升序,即自变量从小到大
3. 左区间加入单调队列
4. 两个指针扫一下,把左区间的信息加到右区间上
5. 整个区间按d[]排序,即按斜率排升序(注意这里斜率取负数) ......  查看更多

小R的烦恼

小R的烦恼
这题我看了好久都没看出来到底是一发什么题目,然后看了看路牌,哇费用流。
这题要把每一天看成两个点,一个是能用的研究生,一个是病倒的研究生,然后st,ed分别连向这两个点来严格限制流量,然后再根据医院,连病倒的到能用的一条边,最后跑一次费用流就OVER了。 ......  查看更多

[NOI2014]动物园

[NOI2014]动物园
这题其实和前面有一题似乎在梦中见过的样子很像,只是这里要j*2>i时跳fail而已。

跳&最短路


最短路
先走长再走短,两条边。反正就是沿着边界走就行了,为什么想走长再走短?你打个表就知道了,其实C就是一个组合数,然后自己枚举一下先走长还是想走短就知道了。

最短路

最短路

这题看看就是叫你建边跑最短路的,但眨眼一看,哇赛,为什么这么多边!这样明显就是为了卡SPFA了。所以我们就要用到Dij算法去解答这题,Dij算法就是让当前路径最短的那个点去找边,减少枚举情况。具体如何去找当前路径最短的点,我们可以使用堆优化的Dij算法,但是呢规模还是太大呢,自己写的堆不够高效,所以我们要采用系统配对堆进行解答。 ......  查看更多

[SDOI2008]Cave 洞穴勘测

[SDOI2008]Cave 洞穴勘测
此题又三个操作,连接x,y一边,摧毁x,y一边,问x,y是否联通。着就是动态树LCT裸题了,连接就link,摧毁就cut,询问联通就问x,y的根是否一样即可。

DZY Loves Chinese

DZY Loves Chinese
做这题时发现这里原来有第二道题,于是点进去看了看
DZY Loves Chinese II
注意对比两题红字部分
这题的K同样被异或了,然而后面又输入K个数字,这样预处理一下,就知道异或的到底是个什么东西了。
于是这题就变成简单的字符串模拟,然后暴力求一下最后一次的并查集即可。 ......  查看更多

[JLOI2014]松鼠的新家

[JLOI2014]松鼠的新家
这题想让你求一条路径里面经过每个点次数多少次。
一看到树就要想到树链剖分,剖分时候就加上路径之间相邻的两个点的值,由于是在某一段区间加上一个相同的值,所以可以用树状数组解决,然而每两个路径之间首尾都会有一个点重复,最后一个点不用计算,所以除了路径开头的那个点,其他点都要将答案减1 ......  查看更多