ABC267 - C,D,E,F Solutions

C - Index × A(Continuous ver.)

Problem Statement

You are given an integer sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$.

Find the maximum value of $\sum_{i=1}^{M} i \times B_i$ for a contiguous subarray $B=(B_1,B_2,\dots,B_M)$ of $A$ of length $M$.

Constraints

• $1 \le M \le N \le 2 \times 10^5$
• $-2 \times 10^5 \le A_i \le 2 \times 10^5$

Solution

不妨令 $R_k=\sum_{i=1}^{M} i \times B_i$，其中 $B=(A_k,A_{k+1},\dots,A_{k+M-1})$。直接计算是 $O(N^2)$ 的，需要进行优化。

首先可以考虑 $R_k$ 与 $R_{k+1}$ 的关系，会发现 $R_{k+1}-R_k=M\times A_{k+M}-\sum_{i=k}^{k+M-1}A_i$，于是简单前缀和就解决了。

另外也可以直接求，对 $A_i$ 与 $i\times A_i$ 都求前缀和，$R_k$ 即为两者做差的形式，此处不再赘述。

Implementation

1
signed main(){
2
    n=rd();m=rd();jk(i,1,n)a[i]=rd();
3
    jk(i,1,n)s[i]=s[i-1]+a[i];
4
    jk(i,1,m)R+=a[i]*i;r=R;
5
    jk(i,m+1,n)r=std::max(r,R=R-(s[i-1]-s[i-m-1])+m*a[i]);
6
    P(r);
7
}

D - Index × A(Not Continuous ver.)

Problem Statement

You are given an integer sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$.

Find the maximum value of $\sum_{i=1}^{M} i \times B_i$ for a (not necessarily contiguous) subsequence $B=(B_1,B_2,\dots,B_M)$ of length $M$ of $A$.

Constraints

• $1 \le M \le N \le 2000$
• $-2 \times 10^5 \le A_i \le 2 \times 10^5$

Solution

和上题不一样的地方在于 $B$ 的选择可以不连续，不难想到可以通过 dp 进行求解，于是令 $f(n,m)$ 表示 $(A_1,A_2,\dots,A_n)$ 中，选择了 $m$ 个数时 $\sum_{i=1}^{m} i \times B_i$ 最大的值。故转移方程为 $f(n,m)=\max(f(n-1,m),f(n-1,m-1)+m*A[n])$。

Implementation

$A_i$ 可能为负数，需要注意边界条件。

xxxxxxxxxx
8
1
#define IN -1000000000000000000ll
2
signed main(){
3
    n=rd();m=rd();jk(i,1,n)a[i]=rd();
4
    jk(i,1,n)jk(j,1,n)f[i][j]=IN;
5
    f[0][1]=IN; //Important!
6
    jk(i,1,n)jk(j,1,i)f[i][j]=std::max(f[i-1][j],f[i-1][j-1]+j*a[i]);
7
    P(f[n][m]);
8
}

E - Erasing Vertices 2

Problem Statement

You are given a simple undirected graph with $N$ vertices and $M$ edges. The $i$-th edge connects Vertices $U_i$ and $V_i$. Vertex $i$ has a positive integer $A_i$ written on it.

You will repeat the following operation $N$ times.

• Choose a Vertex $x$ that is not removed yet, and remove Vertex $x$ and all edges incident to Vertex $x$. The cost of this operation is the sum of the integers written on the vertices directly connected by an edge with Vertex $x$ that are not removed yet.

We define the cost of the entire $N$ operations as the maximum of the costs of the individual operations. Find the minimum possible cost of the entire operations.

Constraints

• $1≤N≤2×10^5$
• $0 \le M \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• The given graph is simple.

Solution

Minimize the maximum. 经典二分答案，需要注意删掉一个点时会导致相邻点的代价变小，所以开一个队列，在删掉后将相邻满足条件的点加到队列里。

Implementation

​x
1
bool ck(int x){
2
    memcpy(s,S,(n+1)*sizeof(int));memset(de,0,sizeof de);
3
    std::queue<int>q;
4
    jk(i,1,n)if(s[i]<=x)q.push(i);
5
    while(!q.empty()){
6
        int u=q.front();q.pop();if(de[u])continue;de[u]=1;
7
        for(int i=h[u];i;i=e[i].n){
8
            int v=e[i].v;if(de[v])continue;
9
            if((s[v]-=V[u])<=x)q.push(v);
10
        }
11
    }
12
    jk(i,1,n)if(!de[i])return 0;
13
    return 1;
14
}
15
​
16
signed main(){
17
    n=rd();m=rd();jk(i,1,n)V[i]=rd();
18
    int u,v;jk(i,1,m){u=rd();v=rd();ad(u,v);ad(v,u);}
19
    jk(u,1,n)for(int i=h[u];i;i=e[i].n)S[u]+=V[e[i].v];
20
    int l=0,r=MX*2,mi;while(l<r){mi=(l+r)>>1;if(ck(mi))r=mi;else l=mi+1;}
21
    P(l);
22
}

F - Exactly K Steps

Problem Statement

You are given a tree with $N$ vertices. The vertices are numbered $1, \dots, N$, and the $i$-th ($1 \leq i \leq N - 1$) edge connects Vertices $A_i$ and $B_i$.

We define the distance between Vertices $u$ and $v$ on this tree by the number of edges in the shortest path from Vertex $u$ to Vertex $v$.

You are given $Q$ queries. In the $i$-th ($1 \leq i \leq Q$) query, given integers $U_i$ and $K_i$, print the index of any vertex whose distance from Vertex $U_i$ is exactly $K_i$. If there is no such vertex, print -1.

Constraints

• $2≤N≤2×10^5$
• The given graph is a tree.
• $1 \leq Q \leq 2 \times 10^5$

Solution

需要知道一个性质：令直径两端点为 $X$ 与 $Y$，则对于树中的任意节点 $u$，$u$ 到 $X$ 的路径与 $u$ 到 $Y$ 的路径中必有一条为 $u$ 点出发可达的最长路径，此处性质在两边dfs求直径的方法中被证明过。

于是先求出直径，然后分别以 $X$ 与 $Y$ 为根建两棵树，使用树上倍增找点。

另：官方题解中把询问离线下来，$O(N+Q)$ 地解决了，回来补下这个做法。

Implementation

xxxxxxxxxx
17
1
void df(int u,int f,int o){
2
    D[u][o]=D[f][o]+1;F[u][0][o]=f;
3
    if(o)jk(i,1,L)F[u][i][o]=F[F[u][i-1][o]][i-1][o];
4
    for(int i=h[u];i;i=e[i].n)if(e[i].v!=f)df(e[i].v,u,o);
5
}
6
​
7
void pr(){
8
    int mx,mi;df(1,0,0);
9
    mx=D[1][0],mi=1;jk(i,2,n)if(D[i][0]>mx)mx=D[i][0],mi=i;
10
    memset(D,0,sizeof D);X=mi;df(mi,0,0);
11
    mx=D[1][0],mi=1;jk(i,2,n)if(D[i][0]>mx)mx=D[i][0],mi=i;
12
    Y=mi;df(X,0,1);df(Y,0,2);
13
}
14
​
15
int fi(int x,int d,int o){jk(i,0,L)if((d>>i)&1)x=F[x][i][o];return x;}
16
int wk(int x,int d){jk(o,1,2)if(D[x][o]>d)return fi(x,d,o);return -1;}
17
​