Atcoder ABC 401

· · 题解

C

给定正整数 N 和 K 。按如下所示定义长度为 N+1 的序列 A = (A_0, A_1, \ldots, A_N) ：

求 A_N 模 10^9 。

思路：第k项开始，后面每一项计算的整体变化很少，维护当前的和，减去最前面一项。注意：因为取模的原因，导致后面的计算会出现负数，所以计算时，把模数加上。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int mod = 1e9;
int n, k;
long long a[N],s;
signed main(){
    scanf("%lld%lld", &n, &k);
    for(int i = 0; i < k; i++) a[i] = 1;
    s = k;
    for(int i = k; i <= n; i++){
        a[i] = s;
        s = (s + a[i] - a[i - k] + mod) % mod;
    }
    //for(int i = 0; i <= n; i++)
    //  cout << i <<':' << a[i] << endl;
    printf("%lld", a[n]);
    return 0;
}

D

一个长度为 N 的字符串 S ，其中包含字符.，o，和？. 在 S 中，可以通过使用.或o，替换每个？.

设 X 是满足以下所有条件的字符串的集合：

保证 X 非空。

输出长度为 N 且满足以下条件的字符串 T （设 T_i 表示 T 的第 i 个字符）:

思路：S的?处能否确定为.或者是o, 不能确定 则输出为?

预处理，对于输入字符串中的每个?,如果与其相邻位置有确定的字符o，那么这个?肯定是.,可以直接修改。

同时，对于每一个确定的字符o,我们可以直接将其从数量中减去，之后让K表示还需要让多少个字符？修改成o.

确定最终字符 循环遍历字符串，找出最多还能放的 o 字符数量。若该数量等于 K ，按照上述规则，将每段数量为奇数的? 字符改为确定的字符。

E

给定一个具有 N 个顶点和 M 条边的无向图。顶点编号为 1,2,\ldots,N ，第 i 条边 (1 \le i \le M) 连接顶点 u_i 和 v_i 。

对于每个 k = 1,2,\ldots,N ，解决以下问题：

考虑以下操作。

判断是否可以重复此操作以满足以下条件：

如果可能，找出这样做所需的最小操作数。

思路:

对于每个k,我们需要满足以下条件：

1：连通性：顶点1到k必须构成一个连通块

2：隔离性：这些顶点不能与任何编号大于k的顶点相连（对应的顶点必须删除）

动态维护：按k从小到大处理，逐步构建连通块，并记录需要删除的顶点，放入set中维护。具体步骤：

处理到k时，若k的邻接点v：

若当前顶点1的连通块大小不为k，则输出-1. 否则输出集合大小。

F

两棵树：树 1 ，其 N_1 个顶点的编号为 1 到 N_1 。以及具有编号为 1 到 N_2 的 N_2 顶点的树 2 。树 1 的第 i 条边双向连接顶点 u_{1,i} 和 v_{1,i} ，树 2 的第 i 条边双向连接顶点 u_{2,i} 和 v_{2,i} 。可以在树 1 的顶点 i 和树 2 的顶点 j 之间添加双向边以获得单个树。

设 f(i,j) 是这棵树的直径。

查找 \displaystyle \sum_{i=1}^{N_1}\sum_{j=1}^{N_2} f(i,j) 。

这里，树的两个顶点之间的距离是在它们之间移动所必须使用的最小边数，

树的直径是两个顶点之间的最大距离。

思路:

给定两棵树，将两棵树通过添加一条边后形成新树，求所有可能的链接方式下新树的直径的总和。

1.树的直径与最远距离：

2.合并后的直径：

3.计算总和：

1.预处理每棵树的节点最远距离：

2.计算总和：

#include <bits/stdc++.h>
#define pb emplace_back

using namespace std;
typedef long long ll;

typedef pair<ll, ll> pii;

const int maxn = 200100;

ll n1, n2, a[maxn], b[maxn], c[maxn], d[maxn];
vector<int> G1[maxn], G2[maxn];

ll mxd, U;

void dfs(int u, int fa, int d, ll *a) {
    if (d > mxd) {
        mxd = d;
        U = u;
    }
    a[u] = d;
    for (int v : G1[u]) {
        if (v == fa) 
            continue;
        dfs(v, u, d + 1, a);
    }
}

void dfs2(int u, int fa, int d, ll *a) {
    if (d > mxd) {
        mxd = d;
        U = u;
    }
    a[u] = d;
    for (int v : G2[u]) {
        if (v == fa) 
            continue;
        dfs2(v, u, d + 1, a);
    }
}

void solve() {
    scanf("%lld", &n1);
    for (int i = 1, u, v; i < n1; ++i) {
        scanf("%d%d", &u, &v);
        G1[u].pb(v);
        G1[v].pb(u);
    }
    scanf("%lld", &n2);
    for (int i = 1, u, v; i < n2; ++i) {
        scanf("%d%d", &u, &v);
        G2[u].pb(v);
        G2[v].pb(u);
    }
    // 计算第一棵树每个点都能走的最远距离和直径 
    mxd = U = -1;
    dfs(1, -1, 0, a);//先找出第一个直径的端点 
    int u = U;
    mxd = U = -1;
    dfs(u, -1, 0, a);//再找出第二个直径的端点 
    ll x = mxd;
    int v = U;
    dfs(v, -1, 0, b);//每个点到第二个端点的距离 

    // 计算第二棵树每个点都能走的最远距离和直径 
    // 方法同上 
    mxd = U = -1;
    dfs2(1, -1, 0, c);
    u = U;
    mxd = U = -1;
    dfs2(u, -1, 0, c);
    x = max(x, mxd);
    v = U;
    dfs2(v, -1, 0, d);
    for (int i = 1; i <= n1; ++i)  
        a[i] = max(a[i], b[i]);// 取第一个端点还是第二个端点 

    for (int i = 1; i <= n2; ++i) 
        c[i] = max(c[i], d[i]);

    ll ans = 0;
    sort(a + 1, a + n1 + 1);
    sort(c + 1, c + n2 + 1);
    ll s = 0;
    for (int i = 1; i <= n2; ++i) 
        s += c[i];

    for(int i = n1, j = 0; i >= 1; i--){ // j要从0开始，因为有可能没有一个点能够满足<=x 
        while(j + 1 <= n2 && a[i] + c[j + 1] + 1 <= x){
            s -= c[j + 1];
            j++;
        }
        ans += x * j + (a[i] + 1) * (n2 - j) + s;
    }

    printf("%lld\n", ans);
}

int main() {
    solve();
    return 0;
}