nowcoder第四场

比赛总结

比赛历程：

10:30看见了nowcoder，于是开始打。
第一题，2的幂在long long范围内共60几个，3的幂更少，所以直接枚举就行了。
然后忘了特判0和1的幂，就超时了。。。题目中有说：在这道题中认为0^0=1。
第二题，枚举一个数忘左往右到哪，可以同上一个到的位置直接转移，复杂度的话....加上fread 100分，不加90，幸亏加了。。
第三题，40分暴力，最后的区间长度是r-l，not r-l+1。这里写错得了20。

T1

T2

如果一个数，是另一个更小的数的倍数，那么它不会是gcd。直接从最小的开始枚举，枚举过的就不要在枚举了。复杂度O(nlogn+n)。
3 6 6 6 9 9 9
3这个位置可以扩展到9，6可以扩展到6，如果假设6也扩展到9，那么对答案没有影响，并且扩展的位置就单调了，于是可以做到O(n)。

for(int i = 1, j = 1; i <= N; ++i) {
    v = a[i];
    while(j <= N && a[j] % v == 0) ++j; 
    r[i] = j;
}
for(int i = N, j = N; i >= 1; --i) {
    v = a[i]; 
    while(j >= 1 && a[j] % v == 0) --j; 
    if(r[i] - j - 1 > ans) ans = r[i] - j - 1;
}

T3

考虑每个位置只用前缀来表示。

两条这样重合的线段，然后第一条只保留前面蓝色的前缀。

这样有两种情况，但是我们仍然用第一种，让考前的线段保留一个前缀。

考虑如何定义状态：
f[i][j]，到第i条线段，最远的右端点小于等于 j的长度，这个状态巧妙的借助上面的前缀表示 可以来转移了。

1、如果这条线段往右，那么考虑第一张图的情况，用（f[i-1][p[i]]+r[i]-p[i]）转移即可，到上一条线段最远的右端点在p[i]的最大的答案。
2、如果这条线段往右，那么考虑第二张图的情况，用（f[i-1][l[i]]+p[i]-l[i]）转移即可，到上一条线段最远的右端点在l[i]的最大的答案。

但是还有两种情况未考虑到：

两个线段方向不同，有相交。
这种情况假设现在是多了一条蓝色的线段。依次考虑每个这样的j，然后如果他们的r[j]超过了p[i]，就假设多了一条蓝色的线段。

（没相交的情况？其实在第一种情况已经考虑了，f[i-1][p[i]]，为最远的右端点小于等于p[i]的最大长度。）

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 3005;
struct Node{
    int l, r, p;
    bool operator < (const Node &A) const {
        return p < A.p;
    }
}a[N];
int l[N], r[N], p[N], disc[N * 3];
int f[N][N * 3];
int main() {
    int n = read(), m = 0;
    for (int i=1; i<=n; ++i) {
        a[i].p = read(), a[i].l = read(), a[i].r = read();
        disc[++m] = a[i].p - a[i].l, disc[++m] = a[i].p + a[i].r, disc[++m] = a[i].p;
    }
    sort(a + 1, a + n + 1);
    sort(disc + 1, disc + m + 1);
    int cnt = 1;
    for (int i=1; i<=m; ++i) if (disc[i] != disc[cnt]) disc[++cnt] = disc[i];
    m = cnt;
    for (int i=1; i<=n; ++i) {
        l[i] = lower_bound(disc + 1, disc + m + 1, a[i].p - a[i].l) - disc;
        r[i] = lower_bound(disc + 1, disc + m + 1, a[i].p + a[i].r) - disc;
        p[i] = lower_bound(disc + 1, disc + m + 1, a[i].p) - disc;
    }
    int Ans = 0;
    for (int i=1; i<=n; ++i) {
        memcpy(f[i], f[i - 1], sizeof(f[i]));
        f[i][p[i]] = max(f[i][p[i]], f[i - 1][l[i]] + a[i].l);
        f[i][r[i]] = max(f[i][r[i]], f[i - 1][p[i]] + a[i].r);
        for (int j=i-1; p[j]>=l[i]; --j) {
            if (r[j] < p[i]) continue;
            f[i][r[j]] = max(f[i][r[j]], f[j - 1][l[i]] + disc[r[j]] - disc[l[i]]);
        }
        for (int j=1; j<=m; ++j)
            f[i][j] = max(f[i][j], f[i][j - 1]);
        for (int j=m-1; j>=1; --j)
            f[i][j] = max(f[i][j], f[i][j + 1] - (disc[j + 1] - disc[j]));
        Ans = max(Ans, f[i][m]);
    }
    cout << Ans;
    return 0;
}