《牛客算法周周练9》

E：
思路：区间dp.
dp[i][j]表示区间[i,j]的最优解
对于划分区间[i,j]这个面积区域时。
起点为i,终点为j,显然划分点k为[i+1,j-1]之间的某一点.
从这个图可见,我们现在划分区间[1,5]的面积。
对于分割点肯定是2,3,4中的任意一点。
例如我们选定点3位划分点。那么显然三角形{1-3-5}为新划分出来的面积区域,面积大小为 a[1] * a[3] * a[5].
然后剩下的两个区间是区间长度较小的区域,显然已经在之前更新了最优值,那么可以直接加上dp[1][3]+dp[3][5].
那么这样最终划分好了区域dp[1,5],然后对于区间[5,1]并不需要去管,因为我们现在划分的是区间[1,5].别的区域会在别的时候划分.
那么显然转移方程就是
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+a[i] * a[j] * a[k]).
注意的是这里三个a相乘会爆longlong,所以用了int128.
Code:

typedef __int128_t TT; 
void print(TT x)
{
    if(x < 0){putchar('-');x = -x;}
    if(x > 9) print(x/10);
    putchar(x%10+'0');
}
LL a[55];
TT dp[55][55];
int main()
{
    int n;sd(n);
    for(int i=1;i<=n;++i) sld(a[i]);
    for(int len=2;len<=n;++len)
    {
        for(int i=1;i<=n;++i)//枚举起点.
        {
            int j = i+len;//终点
            if(j > n) continue;
            dp[i][j] = INF;
            for(int k=i+1;k<j;++k)//枚举分割点
            {
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+TT(a[i])*a[j]*a[k]);
            }
        }
    }
    print(dp[1][n]);
    system("pause");
    return 0;
}

D:
对于奇数进行一个拆分可以发现
9
2 7
4 5
6 3
8 1
不管怎么样拆分最终都是先后手操作抵消。
那么显然奇数对结果没有影响，那么只需要去统计偶数的操作次数即可.
Code:

int a[N];
int main()
{
    int n;sd(n);
    int cnt = 0;
    for(int i=1;i<=n;++i)
    {
        sd(a[i]);
        if(a[i]%2 == 0) cnt++;
    }
    int f = -1;
    while(cnt > 1)
    {
        f = -f;
        cnt--;//-2+1
    }
    if(f == 1) printf("Alice\n");
    else printf("Bob\n");
    system("pause");
    return 0;
}

C:
思路：
结论：
对于一颗树。
假设树上的两种节点颜色为x,y.
那么节点x与节点y的最远距离为。
x颜色类的节点中两个距离最远的点中的某一点.
到y颜色类的节点中距离最远的两个点中的某一点.
证明：
设x颜色节点最远的两个点为x1,x2.
y颜色节点最远的两个点为y1,y2.
如果y1到x3距离很大。显然y1到x1,x2中的某一点的距离更大.
因为当x3在x1-x2的路径中时,显然到两端更大。
当不在路径中时,显然可以通过x3到路径上,且更大.
很抽象,画图更容易理解.
所以枚举四个点的距离即可.这里需要注意的是不一定所有颜色都有两个以上节点。
所有需要特判

因为c[i]过大,所以先离散化颜色.然后将各种颜色的点放入。
然后预处理出每种颜色的节点最远距离的两个点。
树上两点距离可以通过Lca计算.
Code:

int n,q;
int f[N][20],c[N],b[N],dep[N],lg[N];
vector<int> col[N],G[N];
void init()
{
    lg[0] = 1;for(int i=1;i<20;++i) lg[i] = (lg[i-1]<<1);
}
void dfs(int u,int fa)
{
    dep[u] = dep[fa]+1;
    f[u][0] = fa;
    for(int i=1;i<20;++i) f[u][i] = f[f[u][i-1]][i-1];
    for(auto v:G[u])
    {
        if(v == fa) continue;
        dfs(v,u);
    }
}
int Lca(int x,int y)
{
    if(dep[x] < dep[y]) swap(x,y);
    int dix = dep[x]-dep[y];
    for(int i=19;i>=0;--i)
    {
        if(dix >= lg[i]) dix -= lg[i],x = f[x][i];
    }
    if(x == y) return x;
    for(int i=19;i>=0;--i)
    {
        if(lg[i] <= dep[x] && f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
    }
    return f[x][0];
}
int dis(int x,int y)//求树上两点的距离
{
    return dep[x]+dep[y]-2*dep[Lca(x,y)];
}
int main()
{
    init();
    map<int,int> mp;//记录颜色是否在树上
    sdd(n,q);
    for(int i=1;i<=n;++i) sd(c[i]),b[i] = c[i],mp[c[i]]++;
    sort(c+1,c+n+1);
    int len = unique(c+1,c+n+1)-c-1;
    for(int i=1;i<=n;++i)
    {
        int x = lower_bound(c+1,c+len+1,b[i])-c;//节点i-离散化后的颜色
        col[x].pb(i);
    }
    for(int i=1;i<n;++i)
    {
        int u,v;sdd(u,v);
        G[u].pb(v),G[v].pb(u);
    }
    dfs(1,0);
    for(int i=1;i<=len;++i)//枚举颜色
    {
        for(int j=0;j<col[i].size();++j)//默认把col[i][0]和col[i][1]看成距离最远的两点
        {
            int dis1 = dis(col[i][0],col[i][j]);
            int dis2 = dis(col[i][1],col[i][j]);
            int dis3 = dis(col[i][1],col[i][0]);
            if(dis1 > dis3 && dis2 > dis3)
            {
                if(dis1 > dis2) col[i][1] = col[i][j];
                else col[i][0] = col[i][j];
            }
            else if(dis1 > dis3) col[i][1] = col[i][j];
            else if(dis2 > dis3) col[i][0] = col[i][j];
        }
    }
    while(q--)
    {
        int xx,yy;sdd(xx,yy);
        int ans = -1;
        if(mp[xx] == 0 || mp[yy] == 0){printf("0\n");continue;}//当这种颜色不存在时
        int x = lower_bound(c+1,c+len+1,xx)-c;
        int y = lower_bound(c+1,c+len+1,yy)-c;
        int x1 = col[x][0],y1 = col[y][0];
        int dis1 = dis(x1,y1);
        ans = max(ans,dis1);
        if(col[x].size() > 1 && col[y].size() > 1) 
        {
            int x2 = col[x][1],y2 = col[y][1];
            int dis2 = dis(x1,y2);
            int dis3 = dis(x2,y1);
            int dis4 = dis(x2,y2);
            ans = max(ans,max(dis2,dis3));
            ans = max(ans,dis4);
        }
        else if(col[x].size() > 1)
        {
            int x2 = col[x][1];
            int dis2 = dis(x2,y1);
            ans = max(ans,dis2);
        }
        else if(col[y].size() > 1)
        {
            int y2 = col[y][1];
            int dis2 = dis(x1,y2);
            ans = max(ans,dis2);
        }
        pr(ans);
    }
    system("pause");
    return 0;
}