NOI2018模拟赛(十六)

xiz

给定字符串\(S\)和\(T\),定义两字符串匹配当且仅当可以构成一个映射使得\(S\)和\(T\)相同。

求\(T\)与\(S\)中多少个连续子串匹配,并输出开始位置。

只要两字符串同构就可以,相当于每个位置与和上一次出现位置的距离都相同,直接把每个权值变成与上一个位置的距离,hash即可。


yja

平面上\(n(1\le n\le 10)\)个点到原点距离分别是\(r_1,r_2,…,r_n\),最大化$latex n个点构成凸包的面积。

枚举在凸包上是哪些点以及顺序。面积为\(\frac{1}{2}(r_1r_2\sin(\theta_1)+r_2r_3\sin(\theta_2)+…+r_nr_1\sin(\theta_n))\)。
限制条件是\(\theta_1 + \theta_2 +…+ \theta_n=2\pi\)。

拉格朗日乘数有\(\lambda=r_1r_2\cos(\theta_1)=r_2r_3\cos(\theta_2)=…=r_nr_1\cos(\theta_n)\)。
二分\(\lambda\),求出\(\theta_1,\theta_2,…,\theta_n\),带回验证,求面积。


zkb

有一长度为\(n\)的数列\(a_i\),两种操作

  • \(1\ l\ r\ t\):将\([l,r]\)排序,\(0\)表示降序,\(1\)表示升序。
  • \(2\ l\ r\):询问区间\([l,r]\),元素之积的最高位。
  • 其中\(1\le n,q\le 2\times 10^5,1\le a_i\le n\)。

    直接乘显然会爆掉,把每个数以\(10\)为底取对数,乘法变加法,还可以直接算出最高位。(其实数据随机不卡精度,直接用double,一直保持不超过\(10\)也能过)。

    然后对于每一个块排过序的点用一颗权值线段树维护,一颗普通线段树维护所有权值线段树的和。

    排序操作直接分裂两端点的线段树,再把整个区间的所有线段树合并。询问也是分裂两端点的线段树,然后在全局的线段树上询问就好。

    没什么思维难度,就是有点码农。


    在《NOI2018模拟赛(十六)》上留下第一个评论