A Abstract Algebra

线性代数+分类讨论

好像可以利用抽象代数的理论求解 但是没学过

B Bracelet

题意:123456789101112……无穷长的数列

给定一个1e18以内的数,问该数列写到几的时候就可以把给定的数包含

比如8910就是写到10的时候包含

解:枚举被包含数由几位数构成。两边拼接一下看看相不相等。同时需要处理一些比较麻烦的情况 比如99100这种时候要进位。

C Countdown

签到

D Divisor

简单数学思维题

E Edge Game

简单博弈论

F Function-Cuber

其实题目还没读完

是个数学交互题

G Group QQ Speed

简单找规律,输入大于某个数,答案就都是3

补H Histogram in 3D

广告牌问题的3维扩展。数据2e5

首先发现二维问题的单调栈方法完全不能用了。把要求的答案公式化:
$$
设x(i,j)是i到j之间的最小的x,y(i,j)同理\\
ans=max{x(i,j)\cdot y(i,j)\cdot (j-i+1)}
$$
考虑分治。分治的每一次调用都统计跨过mid的答案。那么可以将答案产生的可能分为四个种类:x的最小值在左边还是右边取到,y的最小值在左边还是右边取到

如果x和y的最小值在同一端取到,那么假设是在左边:i从mid向左移动时,j必然向右扩展到比左边i-mid之间的两维数据都大或者等于的最远的地方。所以i向左移动时j必然单调向右移动,因此可以two pointers快速求出答案(eoj上的正确提交用了rmq 但实际上完全不必要吧)

如果x和y的最小值并不在同一端取到,那么假设x在左边取到最小值、y在右边:

分析答案的式子:
$$
ans_now=x(i,mid)\cdot y(mid+1,j)\cdot (j-i+1)\\
=x(i,mid)\cdot y(mid+1,j)\cdot j +x(i,mid)\cdot y(mid+1,j)\cdot(-i+1)\\
=\left( \begin{array}{c}
x(i,mid)\cdot(-i+1) \\
x(i,mid)
\end{array} \right)\cdot
\left( \begin{array}{c}
y(mid+1,j) \\
y(mid+1,j)\cdot j
\end{array} \right)
$$
这样就转化成了一个求向量集当中与所询问向量的内积最大的问题了。用SDOI 2014 向量集类似的方法可求(线段树维护凸包)。同时可以注意到,所询问向量是会按照凸包逆时针一个个排下去的,所以是有单调性的,可以用更小复杂度(无需像SDOI这题一样二分)解决问题。

假设是定i问j的话,那么需要在询问的区间为 使y在右边取到最小值的第一个位置 到 使x在左边取到最小值的最后一个位置。线段树当中每个节点都挂一个凸包,每次更新到使x在左边取到最小值的最后一个位置再进行询问。

同时可以发现,不在同一端取到答案的这种情况的求解过程中,需要求和同一端取到的一样的扩展位置,因此第一种和第二种情况可以合并写在一个函数内。

而且,仅考虑x在左边取到最小值、y在右边即可,做一遍之后将原数组reverse之后再做一遍就能求出x在右边取最小值、y在左边的情况。

I I Love You

签到题

J Just the Chosen One

概率DP

题目忘了

到时候做专题吧