D1讲题

T1

远超NOIPT1
30：枚举l,r
两重for，将区间扫一遍
60：思考这一做法
右端点每次向右移动一个位置
因此每一个字符都可以预处理前缀和
这样可以拿到60分
70：上述做法需要$26^2$次
由于对某一字符对另25个字符没有必要枚举
可以优化一下（并没有听懂
90：考虑假设字符串s，希望算得[L,R]的权值
这就相当于统计字符的频次
对每一个字符记录一个前缀和
则quanzhi[l][r]为sum[k][r]-sum[k][l-1]-sum[j][r]+sum[j][l-1]
若枚举R，我们希望找到L使得结果最大
就可以让sum[k][l-1]-sum[j][l-1]
这里可以再找一个前缀最小值维护
即sum[k][j][x]表示前x个sum[k][x]-sum[j][x]
复杂度O(n*26*26)
100:同70，O(n*26)

T2

计算几何野鸡题
46：输出Yes
54：输出No
玄学：rand()YesNo
能互相看到有两种情况：
1）直接看到
2）反射一下看到
直接看到的情况：是否有墙或镜子挡住
判断线段是否直接相交
过镜子的情况：是否存在和墙相交的情况
即做出虚像，判断线段相交
那么如何处理：
（1）算出反射光线的办法
将第一个人对称连接即可
（2）算对称点的坐标
解几算出垂线方程
用这条线算出与镜子的交点
用中点坐标公式解出另一个点坐标
（3）对直线x=k与直线y=k的情况的处理
用一般式回避
（4）判断相交
法1：直接叉乘，不相同则相交
法2：
若平行则不相交
否则，用交点判断是否在线段上即可

NOIP出数学题不超高中范围

存实数一定要用double

T3

20：随机
30：输出5
奇怪的BFS
判断联通：看做36个点的图，相邻连边
并查集维护
读入可以读入字符串规避影响