2016 Hunan Province Programming Contest
A. 2016
题意
- (1 le a le n, 1 le b le m) ，其中(1 le n,m le 10^9)
- 求正整数((a,b))对的数量，满足(ab \% 2016 = 0)
思路
- (2016=2^53^27)
- 根据(a)对因子的贡献对(a)分类，每种方案数对应(b)的数量，即$$lfloor frac{m}{frac{2016}{a}} floor$$
- 那么剩下的就是求每类(a)的数量，这个容斥一下即可。
代码
B. 有向无环图
题意
- 给一张有(N(N le 10^5))个点，(M(M le 10^5))条边的DAG
- 求$$sum_{i=1}{n}{sum_{j=1}{n}{count(i,j)a_ib_j%(10^9+7)}}$$，其中(count(i,j))表示点i到点j不同的路径数量。
思路
- (a_i)表示从i出发的每条边都要加上的权值，(b_i)则表示到达i的每条边的权值。
- 按照拓扑序转移下即可，注意要记忆化。
代码
D.Toll
题意
思路
- 算几何题吧，求一个凸包的面积，当然需要一些预处理。
代码
E.最长上升子序列
题意
- 给一个长度为(N(N le 10^5))的全排列，有些位置被挖掉，用0表示。
- 现在可以用被挖掉的值来填充0的位置，使得最后序列的最长上升子序列为(N-1)，求方案数。
思路
- 显然，如果|位移|>1的数大于1个，则无解，返回0即可。
- 如果|位移|>1的数(设为(x,p[x])表示位置)只有1个，那么最后的方案数已经固定，需要判断：
- (x)和(p[x])之间的数满足位移情况，就是(x)若往右跳，则中间的数要左移。
- 两边的数不能出现有位移的数。
- 如果没有|位移|>1的数，则判断位移1和位移-1的位置，以位移为1来说：
- 此时有两种情况，这些数是被动移动的，或者此时位移1的数只有一个，但是是主动移动的，而这种情况可以视为前一种情况处理。
- 找出位移1的所有位置，设(L)为最左的位置，(R)为最右的位置。
- 首先(1verb'~'L-1)和(R+1verb'~'N)是不能出现有位移的数，并且(Lverb'~'R)也不能有保持原位的数，否则无解；
- 假设与(L)相邻的连续0的个数为(x)，(R)位置为(y)，则可以让([R,R+y])放置于([L-x,L-1])位置上，则方案数有(x(y + 1))种。
- 两个数相邻（如(32)）的情况需要特判。
- 如果上述情况都没发生，则说明其余位置要么保持原位，要么是0。
- 对于一段连续的0的段，显然这中间的数不会越位到该段之外，比如(0,2,0,0)中的数1不会出现在(3,4)位置上，否则(2)会发生位移。所以若最后上升序列长度为(N-1)，则该段上升序列长度为(L-1)，其余位置保持原位，即变成了原问题的子问题。
- 用(f[i])表示全0段长度为i且最长上升子序列长度为(i-1)的方案数。
- 递推式：(f[i]=2f[i-1]+2-f[i-2])
- 但事实上，(f[i]=(i-1)^2)
- 可以自己多试一些小数据，比如(0,0,2,0)这样子的数据。
代码
F.地铁
题意
- 有(N(N le 10^5))个地铁站，(M(M le 10^5))条地铁路线。
- 每条路线需花费时间(t_i)，属于(c_i)号线。
- 换乘路线需要花费额外的(|c_i-c_j|)的时间。
- 求从地铁站(1)到(N)最少花费时间。
思路
- 最暴力的做法是，对于每个点连接的边，按(c_i)两两连边，时间花费为(|c_i-c_j|)，但这样菊花状的图就做不了了。
- 对于每个点，将其连边按照(c_i)从小到大构建新的点即可，最后跑遍单源最短路即可。
代码
H.Reverse
题意
- 给一个长度为(N(N le 10^5))的数。
- 求$$sum_{i=1}{n}{sum_{j=1}{n}{R(i,j)}}%(10^9+7)$$ (R(i,j))表示将区间([i,j])翻转后新的数。
思路
- 考虑每个位置(i)对答案的贡献，即计算其他位置上的数到位置(i)的次数和当前位置的数不发生改变的次数。
- 可以观察到，出现次数的规律为(1,2,...,i-1,i,i,i,....,i,i-1,...,2,1)
- 即([1,i])出现次数递增到(i)，([i,n-i+1])均为(i)，([n-i+1,n])则从(i)递减到(1)
- 位置不变则选取的区间在([1,i))和((i,n])内。
代码
I.Tree Intersection
题意
- 给一棵(N(N le 10^5))个点的树，每个点有一种颜色(c_i)。
- 对于每条树边，求在把该边去掉后，两棵树的点的颜色交集大小。
思路
-
对于每种颜色单独考虑
-
对于每种颜色的点，可以根据dfs序重新构建一棵新的树
-
对于每条路径，底部节点+1，顶部-1，表示这条路径的每条树边的交集+1。
代码
J.三角形和矩形
题意
- 给一个三角形和矩形，求面积交。
思路
- 比较无脑的做法就是套凸包面积交模板
代码
K.盖房子
题意
- 一个(N imes M(1 le N,M le 10^3))矩形。
- 每个格子要么为空地，要么为障碍。
- 选取两个不相交的矩形，且每个矩形不能包含障碍的方案数(mod(10^9+7))。
思路
-
利用单调栈，可以求出以某个点为顶点的矩形个数。
-
假设我们求出了以((i,j))为左上角的矩形个数，并规定该矩形的左上角不会在另一个矩形的左边。
-
-
那么可以发现这种做法有一种情况是统计不到的：
-
那么把整个矩形旋转90°，则可以统计上述的情况，但是同时会重复计数一些情况：
-
去掉这种情况即可。
代码