快速乘

16年北京网络赛遇到了这个技巧…但是竟然忘记记了下来?

快速乘是为了解决 计算ab % mod 时ab溢出LL 的问题

比如a=1E16,b=1E16,mod=1E18,虽然最后的结果没有溢出,但是中间溢出了。

原理和快速幂很类似,具体可以参考 晴川大爷的专栏

完全就是把快速幂中的乘法变成加法了嘛(从记忆角度考虑orz

 

 

 

hdu 4990 Reading comprehension (构造矩阵,快速幂)

题目链接

题意:

给出了一段程序,程序实际算的是f[n] = (f[n-1] + n%2)%m的值,其中f[1]=1,给出n,m(1E9),问f[n]

思路:

显然是矩阵快速幂,终点在于构造矩阵。

通过经验可得(这次真的是经验了。。。其实也挺容易的,要点大概在于先把需要的项列在一起,然后增加0或者多个,为了转移需要的辅助项。

根据当前列和下一列,手动构造转移矩阵)

转移矩阵M为

[2, 1,0]

[0,-1,1]

[0,0 ,1]

 

4A..都是一个原因。。矩阵乘法那里。。。就算你%了m..也是两个1E9在相乘。。。然后就炸了23333,改成LL即可。

 

 

 

 

hdu 5015 233 Matrix (构造矩阵,快速幂)

hdu5015题目链接

题意:

给出矩阵的构造规则: a[0][j] (j>=1) 分别为233,2333,23333….给出a[i][0] (i>=1),对于其余的i,j,a[i][j]=a[i-1][j] + a[i][j-1]

现在问a[n][m] 在% 1E7+7 下的值是多少  (n<=10,m<=1E9)

思路:

显然矩阵快速幂,但是不会构造矩阵,放弃。

看了很多题解…发现都是“显然”构造出矩阵。。。似乎是直接凑出来的。。。

可能需要积累一点经验。

对于这道题,我们观察到n很小

所以一个直觉就是从n-1列推到第n列,推到n+1列这样地推。

初始第一列的信息是(假设n为3)

[a1]

[a2]

[a3]

然后我们想要得到

[a1+233]

[a1+a2+233]

[a1+a2+a3+233]

我们发现我们需要233这个常数项体现在矩阵中

而且之后还需要233,2333,23333体现在矩阵中。

那么,我们可以在初始添加23和3两项,这样23…3就都可以构造出来了(我觉得关键点就在这一步,应该是凭借经验吧,虽然刚开始有点难想到orz)

因此现在初始列变成了(其实放置顺序无所谓,不过这样放可以让ai和行数对应,比较友好。

[23]

[a1]

[a2]

[a3]

[3]

设该矩阵为A

现在我们想得到下一列

[233]

[a1+233]

[a1+a2+233]

[a1+a2+a3+233]

[3]

设该矩阵为B

那么现在的问题就是构造一个矩阵5*5的矩阵X,使得X×A=B

凭借直觉(经验?

我们得到这样的矩阵X为

[10,0,0,0,1]

[10,1,0,0,1]

[10,1,1,0,1]

[10,1,1,1,1]

[0,  0,0,0,1]

 

接下来就是矩阵快速幂了,答案是 (X^m)×A.mat[n][0]

 

 

 

 

 

 

 

 

hdu 3642 Get The Treasury (线段树+扫描线,求长方体体积交)

hdu3642题目链接

题意:给出若干个(1000)长方体,求至少交三次的空间的体积。

尺寸为[x1,x2],[y1,y2],[z1,z2],其中x,y的坐标的绝对值不超过1E6,Z的坐标的绝对值不超过1E9.

思路:

线段树+扫描线。

由于Z的坐标范围比较小,我们的做法是 利用“微分”的思想,将每个长方体,想成若干的高度为1的矩形(矩形片)

因此就转化成了求矩形至少交三次的面积

其中和矩形交,也就是矩形至少交2次的面积比较类似,只不过线段树多维护一个至少三次覆盖的长度的域。

 

假设我们有一个长为5,宽为6,高为7的长方体

那么我们就要将其拆成7个,长为5,宽为6的矩形

将所有长方体处理完之后,枚举高度,对于每一个高度,如果矩形大于等于三个,就做一个“矩形的三次面积交”操作,将答案累加。

2A,PushUp的时候写错了一句。。。即如果父亲节点已经覆盖了两次,那么父亲节点被覆盖三次的是从左右儿子被覆盖一次的情况得来的

 

 

 

hdu 1828 Picture (线段树+扫描线 求 矩形周长并)

题目链接

题意:

求矩形周长并。

思路:

线段树+扫描线。

和前面的求面积并比较类似,我们先考虑平行x轴的线段,考虑线段树,维护的一段区间中被矩形覆盖的次数cnt和至少覆盖一次的长度的len.

只不过我们这次求的是每条扫描线的长度对周长的贡献,因此不需要乘高度。

 

需要注意的是,每条扫描线对周长的贡献,是目前扫描线的长度,与上一次扫描线长度的差的绝对值。(不是与上一次答案的差的绝对值!)

演示x轴求长度和的部分  图片来自 lwt聚聚的博客
这里写图片描述

以及一个小细节是,求面积的时候,最后一条扫描线对答案是没有贡献的(因为每次是求当前扫描线与下一条扫描线之间的面积)

但是求周长的时候,最后一条扫描线是一定会对答案有贡献的。

 

hdu 1255 覆盖的面积 (扫描线+线段树 求矩形面积交)

题目链接

题意:

求n(1000)个矩形的面积交,也就是至少有2个矩形覆盖的区域的面积

思路:

矩形面积并_hdu1542解题报告    类似

面积并问题中,线段树len维护的是至少覆盖一次的区域的长度

在面积交的问题中,我们需要多维护一个”至少覆盖两次的区域的长度”的域(设为double two;)

同时也要维护至少覆盖一次的区域的长度(设为double one;),是因为至少覆盖两次的区域的长度可以由至少覆盖一次的区域长度得到(好像是废话)

PushUp的时候要格外注意当前节点被完整覆盖一次的情况。

此时tree[rt].two 可以由两个子区间的one的情况想加得到

因为rt节点被完整覆盖了至少一次,那么如果rt儿子区间中被覆盖了至少一次,对于rt区间中被rt<<1和rt<<1|1覆盖至少一次的区间在对于rt区间就已经覆盖了至少2次

 

以及要注意题意说得不够清楚。最后保留2位小数是四舍五入。

读入的实际上是左下角和右上角的点。。。。

 

 

 

hdu 1542 Atlantis (线段树+扫描线求矩形面积并,模板题)

hdu1542题目链接

题意:

求n(100)个矩形的面积并。

思路:

扫描线+线段树

题目是2000年中欧区域赛的题目,虽然年代久远,但是有好几个点还是很值得学习的。

 

首先是离散化的适用范围:

之前比较常用的是将比较大的整数值离散化,常常是因为数值太大无法作为下标。

那么其实,浮点数有的时候也需要进行离散化,比如作为数组的下标,比如用来枚举。

做法上是和将较大的整数值离散化没有区别,因为遇到的题目不多,所以特意记录一下。

 

第二点是扫描线的思想:

其实扫描线的思想很早就接触过,noip2011的时候,tyvj上有一道类似的题目,不过是一唯的,当时印象深刻的是@Ocean 兄的那个比喻:

一段公路上右很多区间要收不同的费用,区间的开始给一个标记,表示该段区间对答案有贡献,区间的结束拿走该标记,表示该段区间对答案的贡献结束。

这就是扫描线的思想。

 

第三个是处理线段覆盖问题的一般做法:

通常线段树的节点处理的都是点,处理线段的时候就会比较麻烦。

  另外很重要的一点就是, 线段树都是维护一个点集, 但是对于边的问题就会变得很麻烦,  我们可以按照区间左端点建立线段树, 那么一个点表示的就不是点了, 而是起点在这个点的一个线段。  这样的话, 右区间就要相应的-1, 例如更新区间[1, 4], 就相当于更新标号为[1, 3]的线段。

这也是处理线段覆盖问题的通用方法。

对于上面引用中提到的例子中“更新[1,4],就相当于更新标号为[1,3]的线段”,是因为标号为1的节点代表区间[1,2],标号为2的节点代表区间[2,3],标号为3的节点代表期间[3,4]

 

接下来具体讨论这道题目的做法:

将矩形按平行x轴方形构建扫描线(只是思想,不用实际构造),

每个矩形2条平行x轴的边分类{上边,下边}2类,如果我们从下往上“扫描”线,那么[下边]就表示了对答案贡献的开始,[下边]就表示了对答案贡献的结束。

  • 扫描线扫描的过程(建议配合代码模拟)

    以下图转载自@kk303的博客

初始状态

初始状态

这里写图片描述

扫到最下边的线, 点13更新为1

这里写图片描述

扫到第二根线, 此时S=lcnt!=0h线, 得到绿色的面积, 加到答案中去, 随后更新计数

这里写图片描述

同上, 将黄色的面积加到答案中去

这里写图片描述

同上, 将灰色的面积加到答案中去

这里写图片描述

同上, 将紫色的面积加到答案中去

这里写图片描述

 

 

 

参考资料:

HDU 1542 Atlantis(线段树:扫描线)

HDU 1542 Atlantis(线段树求矩形面积并)

矩形面积并、矩形面积交、矩形周长并(线段树、扫描线总结)

 

 

 

zoj 3606 Lazy Salesgirl (线段树,单点更新,区间合并)

zoj3606题目链接

题意:有个小女孩卖火柴,有n个人会来买,分别在时间t[i],以价格p[i],买的火柴个数为1+(k-1)%3,其中k为这是小女孩第几次卖火柴。 如果有大于w的时间没人来买火柴,小女孩就会睡着。小女孩睡着后如果有人来买火柴,那小女孩就会醒过来,但是不会卖给这个人火柴。现在问使营业额最大的基础上最小的时间间隔w。

思路: 显然,w应该是某2个顾客的来访时间只差(而不是什么任意值).

因此我们可以通过枚举相邻访问时间的顾客的访问之间之差。

我们可以从小到大枚举w,这样就可以保证得到的最大营业额的对应w最小。

构造一颗线段树,维护4个域,cnt表示区间中,确实购买了火柴的顾客的人数,sum[i] (i属于0..2) 表示一个区间中最左边的顾客购买了i+1根火柴后,该区间的最大利润。

所以其实这道题类似hdu4288解题报告           

维护sum[i]的时候,右一点绕,需要注意对于tree[rt].sum[i],我们只是说该区间的最左边的人买了(i+1)根火柴,该区间的其他人买了几根火柴无所谓,我们只想知道该区间的利润。

wa了一次。。因为虽然我们分析出w一定是某2个连续的时间的差值,一定是整数值,但是为了迷惑人。。题目还是要以6位小数输出。

 

 

 

hdu 4288 Coder (离散化, 线段树,单点更新,区间合并)

题目链接

题意:n(1E5)个操作,分为三种,add x表示将x加到集合中(保证集合中之前没有x),del x表示从集合中删掉x(保证集合中一定右x),sum表示求集合中所有元素按从小到大排列后,所有的下标中满足i%5=3的a[i]的和。1=<x<=1E9

思路:很容易想到的是,由于插入和删除元素造成的位置改变是剧烈的,因此要分别维护i%5==k,k属于0..4的元素的和。

这道题的核心点在于,由于只有1E5个操作,我们可以将元素离散化,这样做的目的是,将每个数和位置一一对应,每个位置用1或者0,表示该位置对应的元素是否在集合中。

考虑线段树,维护6个域,1个是区间中,在集合中的元素个数,剩下5个域,分别表示以该区间的端点为位置1,位置x%i=k的元素的和(k属于0..4)。因此每个叶子节点都是位置1.

考虑PushUp, 区间元素和之间累加,难点在于其他5个域的维护。

假设当前区间为rt,那么对于sum[0..4] (sum代表的就是上面说的要维护的5个域),显然区间rt<<1的答案可以直接贡献给rt.

对于rt<<1|1的答案,考虑rt<<1|1中位置为%5==x的元素和,rt<<1中的元素个数为len个,那么rt<<1|1中sum[x]对 rt中的sum[(x+len)%5]有贡献。

反推出对rt 中 sum[i]有贡献的是rt<<1|1中的sum[(i-len+5)%5)]

 

 

 

codeforces 855 B. Marvolo Gaunt’s Ring (前缀最大,dp)

题目链接

题意:给出n,p,q,r,以及n(1E5)个数,所有数的范围都是[-1E9,1E9],现在问pa[i]+qa[j]+r*a[k]的最大值,满足1<=i<=j<=k<=n

思路:傻逼dp…

我。。好菜啊。。。万年dp苦手。

直接转载官方题解了。。。思路的重点是维护了一个最大前缀值。

dp[i][0] stores maximum of value p·ax for x between 1 and i. Similarly dp[i][1] stores the maximum value of p·ax + q·ay such that x ≤ y ≤ i and dp[i][2] stores maximum value of p·ax + q·ay + r·az for x ≤ y ≤ z ≤ i.

To calculate the dp:

dp[i][0] = max(dp[i - 1][0], p·ai)

dp[i][1] = max(dp[i - 1][1], dp[i][0] + q·ai)

dp[i][2] = max(dp[i - 1][2], dp[i][1] + r·ai)

The answer will be stored in dp[n][2]

 

 

codeforces edu #29 E. Turn Off The TV (思维,乱搞)

题目链接

题意:有若干线段,给出起点和终点,问是否有一个线段是冗余的。冗余的意思是说,对于该线段所覆盖的所有整数点,没有该线段,也能被其他一个或者多个线段覆盖到。如果有,输出任意一个冗余线段即可。

思路:画画图? 显然可以按照第一关键字左端点升序,第二关键字右端点降序(降序是为了处理 n=2,[1,2],[1,3] 这样的case容易一些),先考虑2种最简单的情况。

第一种是a[i+1]完全被a[i]包裹在里面,准确得说不一定是a[i],而是之前所有线段的最大右端点的那条线段,此时a[i+1]就是冗余的线段。

第二种是a[i+1]的左端点在之前所有线段的最大右端点右边,此时没有冗余,继续进行。

接下来考虑比较复杂的相交情况,我们画图发现,当前线段是否冗余,只与a[i-1]和a[i+1]有关。

如果第i条线段的左端点,不超过第i-2条线段的右端点的右边一个位置,此时第i-1条线段就是冗余的。

wa了2次。。原因是没认真看题,l,r的范围的最小值是从0开始而不是1。所以总体来说是道水题(调教场的题这么水了么。。。

 

 

 

 

Codeforces eductional round 29

比赛链接

10个月没写题了,菜啊。进行一点恢复性训练好了。

A: 给一个数,可以在填写若干(或者0)个前缀0,问能否变成回文数。

思路是直接删掉后面可能的出现的0再判断回文数就好。

 

B: 2*n个人,每个人的重量为w[i],要分成n-1组,每组2个人,以及2个单独的人。单独的人的不稳定性为0,每组的不稳定是该组的2个人的重量的差的绝对值。总的不稳定为所有组的不稳定性之和。问可能的最小不稳定性是多少。

思路:由于n才50,100个人,暴力枚举单独的人,复杂度O(nnnlg(n)),很稳。 注意n给的是组数,所以数组最大值应该为100而不是50.

 

C: Ali和Bob两个机器人进行一个类似”石头剪子布”的游戏,每次2个机器人同时出{1,2,3}中的一个。 2 beats 1, 3 beats 2 , 1 beats 3. 赢的得1分,输的得0分。数字一样2人都不得分。2个机器人当前回合的策略(也就是出哪个数字)只取决于上一回合2个机器人出的数字。并且规则完全已知,会用2张3*3的表的形式给出。现在要进行k场游戏,问最后的分数是多少。

思路:由于k比较大,所有可能的分数序列(x,y)又非常有限,因此显然是求个循环节搞。

需要注意几点:

  1. k的大小太小,比循环节开始的第一个位置还小
  2. K是LL类型,各种和k有关的变量也要记得是LL类型
  3. 为了寻找循环节第一次出现的位置,将循环节第二次的开始存了进去,但是在算一个循环节的分数以及其他的时候,记得不要把这个多余的一次算进去。

D:有n(2e5)个数的序列,q(2E5)个区间操作,操作有2种类型,一种是将区间[L,R]循环右移一位。另一种是将区间[L,R]中的数整体反转。最后m(100)个询问,每个询问问b[j] (j属于1..m,b[j]属于1..n)位置上的数是多少。

思路:观察发现m比较小,可以暴力。对于所有操作进行完,b[i]位置上的数是多少, 因为所有的数只是位置改变,大小没有改变.我们想要还原,到最后的b[i]位置,应该对应的是初始序列中的哪个位置。
如果当前位置是pos,那么在进行上一个反转操作之前的位置就是(L+R)-pos, 进行上一个移位操作的位置就是pos-1(注意边界)

 

反向传播学习笔记

先说下自己目前很笼统的理解:

反向传播是用来快速计算梯度的一种方法;

过程大概是把计算过程用计算图表示,这样每一个中间步骤都有一个节点,每一个local gradient都会比较容易计算;

思想涉及 chain rule + 计算图 + 记忆化

因为计算不同自变量的偏导数会存在很多共同路径,这部分就只计算了一次,因此可以加快计算速度。

所以核心的东西大概是两点:

  • 用计算图表示计算,局部gradient 替代繁琐的微积分计算
  • 共同部分只计算一次,类似一个记忆化。