10.16 补题记录

https://codeforces.com/gym/105386/problem/E
E题：要求gcd最大值然后可以改变一次数组使选中的那一节增大k，然后我们一开始想dp[i][0/1][0/1]来维护前i个里这个数加k/不加k，以及之前加k/不加k,看起来非常的完美吧 然后wa15了，是因为我们每次只记录了一个点的一种值 但是一个点有可能会有好几个值，然后就要震惊了gcd数值的个数只和你数值里的最大值有关 然后大概的数量关系是log(MA)然后我们这里最大值就1e18大概就18个完全够我们for一下 所以我们可以优化一层n只需要既然上一个点的所有gcd可能值在此基础上转移就不会爆
void solve() {
int n, k;
std::cin >> n >> k;
std::vectora(n + 1), pa(n + 2), sa(n + 2);

for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    pa[i] = std::gcd(pa[i - 1], a[i]);
}

std::vector<int>b(n + 1);
for (int i = 1; i <= n; ++i) {
    b[i] = a[i] + k;
}

for (int i = n; i; --i) {
    sa[i] = std::gcd(sa[i + 1], a[i]);
}

int ans = pa[n];

std::set<int>st[2];
for (int r = 1; r <= n; ++r) //你遍历到一个r要么是他是开头又是结尾（对应int t 的特判） 要么他前一个也变了（对应下面那个循环lst）
{
    int now = r & 1, lst = now ^ 1;
    //now是0时lst就是1 反正相反
    for (auto& x : st[lst]) 
    {
        int t = std::gcd(x, b[r]);//从前一个变了转移过来
        st[now].insert(t);//保存了把当前r这个点替换了的gcd
    }

    int t = std::gcd(pa[r - 1], b[r]);//这里表示只有r这一个点替换的gcd
    st[now].insert(t);

    st[lst].clear();//每次把这个清空了下一次就直接用了 因为这里的now 和 lst是交替的 因为这一次的now就是下一次的lst

    for (auto& x : st[now]) {
        int w = std::gcd(x, sa[r + 1]);
        ans = std::max(ans, w);//统计一下最后的答案 就是再gcd上后面那一段
    }

}

std::cout << ans << "\n";

}

https://codeforces.com/gym/105386/problem/M
M题：看起来挺好想的 就是很难写 就算是我们先找到里第一个点最远的合法点 然后不断枚举下一个点作为开头 这个时候另外一个点只会不断逆时针转 不可能倒回去 就是这个计算和判断很难写 会想到很复杂 好吧可能是高中忘光光的缘故吧看了题解感觉是学过的 但是全部忘记啦！！！但是下次先把这些公式单独写出来就会变得好清晰
// 叉乘（https://www.cnblogs.com/gxcdream/p/7597865.html）
lll cross(P a, P b)//两个向量
{
return a.x * b.y - a.y * b.x; // 计算新加点是否在左边界与圆心连线的另一侧（>0表示a向量在b的左边）同时如果把ab移到统一起点或者终点的话 这个值还表示这个三角形的面积的两倍
}

// 点积
lll mul(P a, P b)//得到的结果反应出两个向量的夹角（<0就是钝角）
{
return a.x * b.x + a.y * b.y;
}

// 点平方和
lll mul(P a)
{
return a.x * a.x + a.y * a.y;
}

// 计算矢量
P del(P a, P b)
{
return {a.x - b.x, a.y - b.y};
}

void solve()
{
int n;
read(n);

P C;
read(C.x);
read(C.y);

lll R;
read(R);

vector<P> a(n);
for (int i = 0; i < n; i++)
{
    read(a[i].x);
    read(a[i].y);
}
lll ans = 0;
lll S = 0;
for (int l = 0, r = l + 1; l < n; l++)
{
    while (1)
    {
        // 处理首尾循环
        int rr = r % n + 1;
        // 计算新加点是否在左边界与圆心连线的另一侧
        lll s = cross(del(a[rr], a[l]), del(C, a[l]));
        // 如果在另一侧，说明新加边与圆相交或凸包包含了圆，移动l
        if (s <= 0)
            break;
        // s同时也是新加边与圆心构成的三角形的面积的两倍，利用s=len*d计算边与圆心的距离
        // 如果距离小于R，说明新加边与圆相交，移动l
        if (s * s < mul(del(a[rr], a[l])) * R * R)//（mul(del(a[rr], a[l])) * R）是垂直与R的
            break;
        // 利用叉乘公式计算凸包新增加的三角形面积
        S += cross(del(a[r], a[l]), del(a[rr], a[l]));
        // 移动r
        r = rr;
    }
    ans = max(ans, S);
    // 处理首尾循环
    int ll = l % n + 1;
    // 减去左边界的三角形面积
    S -= cross(del(a[r], a[l]), del(a[r], a[ll]));
}
write(ans);
putchar('\n');

}