?

A,B,C不讲

D题

给定一个序列，按顺序选取几个数组成一个新的序列，满足一个数和它两边的数的gcd都>1，求最大长度
正常的做法都是暴力n^2

我们考虑优化，对于一个数的因数，找这个因数的前一个最长的新序列（80pts）

我们发现，质因数肯定比因数优

于是我们直接nlogn预处理出质因数就好了

预处理代码：(不会有人不会吧)

for(int i=1;i<=M;i++){
    if(s[i][0]==0){
        for(int j=i;j<=M;j=j+i){
            s[j][++s[j][0]]=i;
        }
    }
}

s[j][0]代表有多少个质因数，s[j][1~9]代表有什么质因数

E题

两个单调队列就好了

F题

重量寄

前置芝士：昨天的斜率优化

题面：把n个数分成k个集合，让每段的（最大值-最小值）^2之和最小

我们先把序列排序

很容易写出这样一个转移方程：dp[i][j]=dp[k][j-1]+(a[i]-a[k+1])(a[i]-a[k+1])
拆开就是dp[k][j-1]+a[i]^2-2a[i]a[k+1]+a[k+1]^2
建坐标(a[k+1],dp[k][j-1]+a[k+1]^2) 把-2a[i]当作斜率
跑斜率优化

H

省选题
会打，但思维量很大，说不清楚

溜了