感觉省选好难的说。。。反正我数据结构太垃圾正解想到了也打不出来打一打暴力就滚粗了！
DAY1
0+20+30
DAY2
60-20+0+60
最后170-20分，暴力分还是没有拿全！
然而这次是给了50+20+30+60+10+60=230分的暴力分的。
妈蛋数据加强gi掉了两个点
写一写那两个60分的暴力是怎么打出来的吧0.0
day2 t1 sequence
显然暴力n^3是没什么希望了只有10分，那么注意到前两个点的值很小，直接n^2预处理答案就可以了，还有前30-40分的预处理时候不可以只记录一维前缀，要处理出所有答案（一路推过去）就行了。
另外的50-60分的时候n=100000,q=10。那么我们就只要优化预处理就可以过了，这个时候空间也开不下了（这是得不到60分的主要问题，数据点比较水，n^2的暴力都可以过），推导一个公式：以某一个点位置左右拓展创建子串，在这个点的子串总数为（左端连续比其小的数字个数+1）*（右端连续比其小的数+1）n^2预处理（但是可以单调栈或者随机跳表来优化）
qn 查询，这样就有60分了。（公式仅仅成立于数字互不相等的情况）
举一个例子：
母序列：5 4 2 1 3
2的左边有2个连续的数字比大，左边0个，那么2这个位置的影响值为：（2+1）*（0+1）=3,也就是说在这5个数子的所有子序列中，有3个子序列的最小值为2。
所以预处理每一个数字左右各有多少个连续的数字比它小，它的每一个子问题都也都满足这一个性质，查询每一个位置的数字的影响值，就选取较小值(min(l,l1)+1)*(min(r.r1)+1)就可以了。
E哥的AC正解就是分治加上记忆化搜索，动态存储了每一次询问的情况（居然是在线的！%%jump写的离线解法）
当然这题别的乱搞优化也可以AC--0.0
|
|
5 |
4 |
2 |
1 |
3 |
|
L |
0 |
1 |
2 |
3 |
0 |
|
R |
0 |
0 |
0 |
1 |
0 |
|
Val（影响值） |
1 |
2 |
3 |
8 |
1 |
|
L=1,r=5时对于答案的贡献 |
5 |
8 |
6 |
8 |
3 |
不加优化的核心代码O（n^2+nq）
void doit1()
{
if
(n>5000) {erfen(1,n);}else{
for
(i=1;i<=n;i++)
{
x=i;
while
(a[x-1]>a[i] && x>1) x--;
l[i]=i-x+1;
x=i;
while
(a[x+1]>a[i] && x<n) x++;
r[i]=x-i+1;
}}
while
(q--)
{
scanf("%lld%lld",&x,&y);
ans=0;
for
(i=x;i<=y;i++)
{
f1=min(i-x+1,l[i]);
f2=min(y-i+1,r[i]);
ans+=a[i]*f1*f2;
}
printf("%lld\n",ans);
}
}
day2
t3 number
数位dp（或许不算DP吧）f[i]来统计以第i位结尾的子串有多少个可以被p整除。Vector数组动态地存储下第i位结尾可以被P整除的数的开头位置，查询O（n）扫描加二分查找就可以了。
复杂度O（n^2+nmlogn）
讲道理N^2不带常数是可以过的哟。（毕竟评测姬很优秀）
最后说几句（总结）
这次省选在我们机房里相较考得似乎还可以，但是运气成分很大啊。机房里很多人都去想了正解并且几乎成功实现了，大多只是失手而已。我只是老实的打打暴力。这样下去是不行的，所以接下来的学习中我应该改变方向，改变我在数据结构上的弱势，多去想正解，还有就是几何，概率，博弈方面我基本都不会，需要去学习！
再多努力一点吧0^0!