标题统计

Description

输入一行可能带空格的字符串，求除空格外有多少个字符。

数据范围：$1\le \vert s\vert\le 5$。

Solution

使用 $\text{scanf}$ 或 $\text{cin}$ 读入每个字符串（不包含空格），然后统计字符串的长度之和即可。

时间复杂度：$\mathcal O(\vert s\vert)$。

Code

#include <cstdio>
#include <cstring>

int main() {
    char s[6];
    int ans = 0;
    while (~scanf("%s", s + 1)) {
        ans += strlen(s + 1);
    }
    printf("%d\n", ans);
    return 0;
}

龙虎斗

Description

在数轴上有 $n$ 个点，第 $i$ 个点的位置为 $i$，权值为 $c_i$。现在给第 $p_1$ 个点的权值增加 $s_1$，你必须再给一个点的权值增加 $s_2$ 满足对于给定的一个坐标为 $m$ 的点，使得 $\sum_{i=1}^n c_i(i-m)$ 的绝对值最小。

数据范围：$1\le n\le 10 ^ 5$，$1\le c_i, s_1, s_2 \le 10 ^ 9$。

Solution

首先，我们直接把 $s_1$ 位工兵增加到第 $p_1$ 号兵营，设 $s=\sum_{i=1}^n c_i(i-m)$

我们考虑如果在第 $p_2$ 的位置增加 $s_2$ 位工兵，那么可以得到 $s'=s+s_2(p_2-m)$。我们只需要求出使得 $s'$ 的绝对值最小的 $p_2$。我们可以直接枚举 $p_2$，在 $\mathcal O(1)$ 的时间内计算出 $s_2$，更新答案的过程中要注意字典序最小的要求。

时间复杂度：$\mathcal O(n)$。

Code

#include <cstdio>

const int N = 1e5 + 5;
const long long INF = 0x7f7f7f7f7f7f7f7f;

int n, m, p1;
long long c[N], s1, s2;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &c[i]);
    }
    scanf("%d%d%lld%lld", &m, &p1, &s1, &s2);
    c[p1] += s1;
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += 1LL * (i - m) * c[i];
    }
    long long ans = INF;
    int pos;
    for (int i = 1; i <= n; i++) {
        long long now = sum + 1LL * (i - m) * s2;
        if (now < 0) now = -now;
        if (now < ans) ans = now, pos = i;
    }
    printf("%d\n", pos);
    return 0;
}

摆渡车

Description

有 $n$ 名同学在同一地点等车去同一目的地，第 $i$ 个人在第 $t_i$ 分钟开始等车。现在只有一辆车可以载人（车的容量可以视为无限大），往返一趟需要的时间为 $m$ 分钟。这辆车需要把所有同学都送到目的地。如果这辆车能在任何时间出发，回到等车地点后又可以即刻出发，求出这些同学的等车时间之和最小为多少。

数据范围：$1\le n\le 500$，$1\le m\le 100$，$0\le t_i \le 4\times 10 ^ 6$。

Solution

引理：对于每个乘客，如果他开始等待的时刻为 $t$，那么搭载他的车的发车时间 $t_0\in [t,t+m)$。

证明：如果存在一种发车时间 $\ge t+m$，那么发车时间一定可以提早若干个 $m$ 使得 $t_0$ 到达 $[t,t+m)$。这样不会影响其他 $\ge t+m$ 的发车时间，不会干扰后面的人等车。

我们考虑 $\text{DP}$ 状态设计：$f(i,j)$ 表示搭载了前 $i$ 个人，搭载第 $i$ 个人的摆渡车的发车时间为 $t_i+j$ 的最小等候时间总和。朴素的转移方程为：

$$ f(i, j)=\min_{0\le k<i,0\le p<m}\{f(k, p)+\text{cost}(k+1,i,t_i+j)\} $$

其中 $\text{cost}(i,j,k)$ 表示第 $i\sim j$ 个人在 $k$ 时间乘车的等候时间总和。注意转移过程中有 $t_i+j\ge t_k+p+m$（当前这趟车比上一趟车至少晚 $m$）的限制！

这个式子直接计算是 $\mathcal O(n^3m^2)$的，接下来考虑转移如何优化。上述式子中，我们通过对 $t_i$ 做前缀和可以 $O(1)$ 计算出 $cost$ 的值。我们再记 $g(i, j)=\min_{0\le j<m}f(i, j)$（这个前缀 $\min$ 可以在转移过程中维护），转移方程化为 $f(i, j) = \min_{0\le k<i}\{g(k, x)+\text{cost}\}$，其中 $x=\min(m-1,t_i+j-t_k-m)$ 且 $x\ge 0$，时间复杂度优化为 $\mathcal O(n^2m)$ 。

时间复杂度：$\mathcal O(n ^ 2 m)$。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 505, M = 105;
int n, m, a[N];
long long sum[N], f[N][M];

long long query(int l, int r) {
    return sum[r] - sum[l - 1];
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    std::sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i];
    }
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++) {
        f[i][0] = 1LL * i * a[i] - query(1, i);
        for (int j = 0; j < m; j++) {
            for (int k = 1; k < i; k++) {
                int x = std::min(m - 1, a[i] + j - m - a[k]);
                if (x < 0) continue;
                f[i][j] = std::min(f[i][j], f[k][x] + 1LL * (i - k) * (a[i] + j) - query(k + 1, i));
            }
        }
        for (int j = 1; j < m; j++) {
            f[i][j] = std::min(f[i][j], f[i][j - 1]);
        }
    }
    printf("%lld\n", f[n][m - 1]);
    return 0;
}

对称二叉树

Description

一棵二叉树被称为对称二叉树当且仅当：这是一棵二叉树，将这棵树所有节点的左右子树交换，新树和原树的结构和点权完全相同。

现在给定一棵二叉树，希望找出它的一棵子树，使得该子树为对称二叉树，且节点数最多。

数据范围：$1\le n\le 10 ^ 6$，$1\le v_i\le 10^3$。

Solution

记 $u$ 的左右儿子分别为 $\text{lson}_u$ 和 $\text{rson}_u$。对于以 $u$ 为根的一棵子树，如果它是对称的那么必须满足：

1. $\text{lson}_u$ 和 $\text{rson}_u$ 是对称的。
2. 对于每一对左右儿子 $x,y$，必须满足 $\text{lson}_x$ 和 $\text{rson}_y$ 是对称的、$\text{rson}_x$ 和 $\text{lson}_y$ 是对称的。

我们可以对于每个节点暴力判断是否满足条件。判断的过程中，我们可以使用一些剪枝：左右儿子的大小、权值和等必须相同。

复杂度证明：每次判断子树 $x$ 和 $y$ 是否对称时，复杂度为 $\mathcal O(\min(\text{size}_x,\text{size}_y))$，如果一个点能往上继续产生贡献，那么大小至少乘以 $2$，总复杂度即为 $\mathcal O(n\log n)$

时间复杂度：$\mathcal O(n\log n)$。

Code

#include <cstdio>

const int N = 1e6 + 5;
int n, val[N], ch[N][2], sz[N];

void dfs(int u) {
    if (!u) return;
    dfs(ch[u][0]);
    dfs(ch[u][1]);
    sz[u] = sz[ch[u][0]] + sz[ch[u][1]] + 1;
}
bool same(int x, int y) {
    if (!x && !y) return 1;
    if (!x || !y || sz[x] != sz[y] || val[x] != val[y]) return 0;
    return same(ch[x][0], ch[y][1]) && same(ch[x][1], ch[y][0]);
}
bool check(int u) {
    return same(ch[u][0], ch[u][1]);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &val[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 1; j++) {
            scanf("%d", &ch[i][j]);
            if(ch[i][j] < 0) ch[i][j] = 0;
        }
    }
    dfs(1);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (sz[i] > ans && check(i)) ans = sz[i];
    }
    printf("%d\n", ans);
    return 0;
}