题目链接:
https://acm.hdu.edu.cn/contests/contest_show.php?cid=985
A
Pro:
在(n*n*n)的三维空间中。
选择三个整点,构成等边三角形。
求方案数。
Sol:
瞎jb数一数
B
Pro:
区间加平方数列,单点查询。
放到树上。
Sol:
树链剖分写一写。
线段树写一写。
C
给定一张无向图。
alice和bob分别在一个点。
轮流移动,到达(x)点获胜。
不能向对方当前在的点移动(除了终点)。
双方各移动一步判断一次胜负,可以平局。
问胜负情况。
首先最短路不相等时,非常好判断。
最短路相等时dp,记录当前两人所在的位置,每次只能向最短路(-1)的点转移。
O(n^2)。
D
Pro:
多次询问((l,r,a,b)),(l,r)种有多少不同的数字(c)满 (c xor a<= b)
Sol:
1.
询问离线,Trie套个线段树
2.询问拆到log_n个(Trie)的子树上,每个子树暴力二维数点。
都是(log^2n)
3.(O(n*sqrt(n)*logn))硬冲,莫队奇偶优化+优化Trie树遍历。
E
签到题
F
题都看不懂
G
Pro:
Sol:
H
简单(dp)
I
不会
J
题意即判断排列的奇偶性。
考虑判断排列的奇偶性的公式。
代入后答案很简洁。
K
Pro:
给定数组A,B,计算数组C。
(C_k=max(a_i*b_j) (i and j>=k))
Sol:
考虑
(D_k=max(a_i*b_j) (i and j==k))
再求后缀(max),发现不好求。
但容易发现(D_k)数组的后缀(max)等价于(J_k)数组的后缀(max)
(J_k=max(a_i*b_j) (kin i and kin j))
而(J_k)数组很好求,直接求出(A,B)数组的正负高维前缀(max min),直接乘起来就可以了。
L
签到