$Div.1+Div.2$
A New Year and Naming
大概是天干地支纪年法?随便模一下就好了.
B New Year and Ascent Sequence
用总数减掉不合法的,不合法的只能由两个单调不增的序列拼起来,且要求拼起来之后还是单调不增的.
记录一下单调不增的序列中,最后一个元素是 $i$ 的有多少个,求一个前缀和后再枚举前面那个序列就可以了.
C New Year and Permutation
考虑一个长度为 $i$ 的值域连续段的贡献.
它可以选 $n-i+1$ 个数, $n-i+1$ 个位置,内部有 $i!$ 种排列方法,外部有 $(n-i)!$ 种排列方法,全部乘起来就好了.
D New Year and Conference
考虑若两条 $a$ 的线段有交,那么为了尽可能让集合 $s$ 中的元素在 $b$ 中两两不相交,集合 $s$ 只会包含这两条线段.
即,只需要考虑大小为 $2$ 的集合 $s$ ,先处理所有在 $a$ 中有交的,检查它们在 $b$ 中是否有交,交换 $a,b$ 后再做一次.
处理在 $a$ 中有交时,将所有线段按照 $a_l$ 从小到大排序,依次加入.
加入一条线段 $i$ 时,前面所有 $a_{j,r}\ge a_{i,l}$ 的线段 $j$ 都与它在 $a$ 中相交,检查它们之中是否存在在 $b$ 中与 $i$ 不相交的.
只需要求出它们的 $\max l_b,\min r_b$ 进行判断,于是可以以 $a_{r}$ 为下标维护线段树进行修改与询问.
E New Year and Castle Construction
bzoj 1914 是问覆盖住点 $p$ 的三角形数目,这道题是四边形,拿来改一改就成了.
枚举每个点 $p$ ,考虑计算 $f(p)$ ,把其他点按照 $p$ 为原点做一个极角排序,双指针扫一下即可.
比赛时用的 long double ,精度被卡了,没时间写全整数,有点难受.