A. 吔我大炮！

By Hetmes Askalana *

题意分析

给定三个正整数 $a, b, c$ ，判断是否满足 $a \times b \leq c$ 。

题解

直接按上文所述判断即可。

代码

void solve(){
    LL a, b, c;
    cin >> a >> b >> c;
    if(a * b <= c) yes; else no;
    return;
}

B(B1). 梦间

By Hetmes Askalana *

题意分析

原题很直白了，不分析了。

题解

首先明确中线到底是什么：三角形的一条边的中点和对点的连线。如果中线在坐标轴上，那么这个对点一定在坐标轴上，且对边的中点也在坐标轴上，那么就有： $x_1 + x_2 = 0$ 或者 $y_1 + y_2 = 0$ （假设对点是 $3$ 号点）

其他同理。

代码

void solve(){
    int x1, x2, x3, y1, y2, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    if(
        (y1 == 0 and (y2 + y3) == 0) or
        (x1 == 0 and (x2 + x3) == 0) or
        (y2 == 0 and (y1 + y3) == 0) or
        (x2 == 0 and (x1 + x3) == 0) or
        (x3 == 0 and (x1 + x2) == 0) or
        (y3 == 0 and (y1 + y2) == 0)
    )yes; else no;
    return;
}

C(B2). 坠入

By Hetmes Askalana *

题意分析

原题很直白了，不分析了。

题解

如果一条直线平行于一个坐标轴，那么这条直线上所有与该轴垂直的轴上的的坐标值都相同，也就是： $x_1 = \frac{x_2 + x_3}{2}$ 其等价于 $2x_1 = x_2 + x_3$

其他同理。

代码

void solve(){
    int x1, x2, x3, y1, y2, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    if(
        (2 * y1 == y2 + y3 or 2 * x1 == x2 + x3) or
        (2 * y2 == y1 + y3 or 2 * x2 == x1 + x3) or
        (2 * y3 == y1 + y2 or 2 * x3 == x1 + x2)
    )yes; else no;
    return;
}

D. 漫步

By Hetmes Askalana *

题意分析

给定一个 $x$ ，找到一个 $z$ 使得 $x$ 中为 $1$ 的二进制位在 $x + z$ 中也为 $1$ 。换言之， $x = x \& (x + z)$

题解

假设 $k = x + z$ ，在 $z = 0$ 时， $k = x$ ，我们需要保证在现有的 $1$ 不变的情况下进行操作，一定会比造成进位要强。同时因为 $z < x$ 的约束，我们只能选择比 $x$ 的二进制长度短的 $z$ ，那么自然，全是 $1$ 的 $2^p - 1(p \in Z^+)$ 型的肯定不行。

对于其他的，我们只需要随便选择一个 $x$ 中为 $0$ 的二进制位，构建一个只有这个位置是 $1$ 的 $z$ 即可过关。

代码

#define neg {cout << -1 << endl; return;}
void solve(){
    LL x; cin >> x;
    if(!(x & (x + 1))) neg;
    for(int i = 1; i < x; (i <<= 1)){
        if((x & (i + x)) == x){
            cout << i << endl;
            return;
        }
    }
    neg;
    return;
}

E. 密藏

By Hetmes Askalana *

题意分析

有两个轴，从一号轴的一号点开始，每次前进一格，并在钱够的情况下可以选择消耗 $k$ 点金币跃迁到另一条轴，然后拾起这个点的金币。求抵达 $n$ 号点并拾起金币后持有的金币最大值。

题解

假设表世界是 $0$ ，里世界是 $1$ ，令 $f_{ik}$ 表示在 $w$ 世界上抵达 $i$ 号点时的最大金币，令 $f_{1, 0}$ 初始为 $a_1$ ， $b_1$ 不可达，那么从 $i = 2$ 开始有转移方程 $f_{ik} = \max(f_{ik}, \max(f_{i-1, w}, f_{i-1, w \oplus 1} - k[k \leq f_{i-1, w \oplus 1}]) + world_{w, i})$

下面的代码没有极致压缩~~看上去比较正常~~。

代码

void solve(){
    LL n, k;
    cin >> n >> k;
    vector<LL> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];

    vector<vector<LL>> f(n + 1, vector<LL>(2, LLONG_MIN));
    f[0][0] = f[0][1] = 0;
    f[1][0] = a[1];
    for(int i = 2; i <= n; ++i){
        f[i][0] = max(
            f[i - 1][0] + a[i],
            (f[i - 1][1] >= k ? f[i - 1][1] + a[i] - k : LLONG_MIN)
        );
        f[i][1] = max(
            f[i - 1][1] + b[i],
            (f[i - 1][0] >= k ? f[i - 1][0] + b[i] - k : LLONG_MIN)
        );
    }
    cout << max(f[n][0], f[n][1]) << endl;
    return;
}

F. 回响

By Hetmes Askalana *

题意分析

给定一个序列，在保持原序列中不为 $0$ 的地方不变的情况下，将 $0$ 的位置填上数字，使得 $\forall i \in [1, n - 1]$ 有 $|a_i - a_{i + 1}| = 1$ 。

题解

不需要太多思考，填就完事了。

对于每个区间，我们使其趋近于区间右端点的那个数，如果小了就 $+1$ ，大了就 $-1$ ，一样的话就往上加一加。如果最后构建出来的不满足上面的条件，就不行，如果满足，就行。

代码

void solve(){
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    int pm = 0, j = 0;
    if(a[0] == 0){
        while(pm < n and a[pm] == 0) ++pm;
        if(pm == n) for(int i = 0; i < n; ++i) a[i] = i + 1;
        else for(int i = pm - 1; i >= 0; --i) if(a[i + 1] > 1) a[i] = a[i + 1] - 1; else a[i] = a[i + 1] + 1;
    } // 对付首位为0的情况
    bool inConstruct = false, flag = true;
    for(int i = pm; i < n; ++i){
        if(a[i] == 0){
            if(!inConstruct){
                j = i;
                while(j < n and a[j] == 0) ++j;
                inConstruct = true;
            } //找到区间左端点，搜出区间右端点，开始构造模式
            if(a[i - 1] > a[j] and j != n) a[i] = a[i - 1] - 1;
            else a[i] = a[i - 1] + 1;
        }else inConstruct = false;
    }
    for(int i = 1; i < n; ++i) flag &= (abs(a[i] - a[i - 1]) == 1); //判定一下
    if(!flag) neg;
    for(int i = 0; i < n; ++i) cout << a[i] << " ";
    cout << endl;
    return;
}

G. 升~龙~~

By Hetmes Askalana *

题意分析

给定一棵根为 $1$ 的树，定义其权值为所有到叶子节点的简单路径上的点权之和的最大值，每次操作可以选择 $x, y$ ，使 $x$ 断开与其父的链接，并认 $y$ 做父。求这个操作下的树的权值，每次操作独立。

题解

我们首先搜出从根到各个节点的最大权值（这样到每个叶子的权值都能定下来）（ $v$ 数组中）和以 $i$ 为根且不包含其父的树的子树的权值( $f$ 数组中)，由于dfs的性质，我们在搜的时候顺便记录一下在dfn序下，一个节点什么时候被搜到和什么时候搜完它的全部子节点。

对于每次操作，我们首先把 $x$ 和所有子节点抠掉，就是抠掉 $x$ 在dfn序中进入dfs和搜完所有子节点离开dfs的点所构成的区间。之后剩下的所有可以抵达的节点的最大值就是被抠掉 $x$ 剩下的树的权值。

之后输出剩下的树的权值的最大值和 $f_x + v_y$ 即可。

代码

void solve(){
    LL n, q, x, y, cnt = 0; cin >> n >> q;
    vector<LL> a(n + 10, 0), v(n + 10, 0), pv(n + 10, LLONG_MIN), f(n + 10, 0), dp(n + 10, LLONG_MIN), ds(n + 10, LLONG_MIN), *** + 10, 0), op(n + 10, 0);
    vector<vector<int>> G(n + 10);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 2; i <= n; ++i){
        cin >> x;
        G[x].push_back(i);
    }
    auto dfs = [&](auto &&self, int np, int p) -> void {
        ***p] = ++cnt; // x进入
        if(~p) v[np] = v[p] + a[np]; else v[np] = a[np]; // 继承父节点往下
        f[np] = a[np];
        for(auto to : G[np]){
            self(self, to, np);
            f[np] = max(f[np], f[to] + a[np]); // 类似树形dp的东西
        }
        op[np] = cnt; // x离开
    };
    dfs(dfs, 1, -1);
    for(int i = 1; i <= n; ++i) pv[vp[i]] = v[i]; // 同步dfn序
    dp[1] = pv[1], ds[n] = pv[n]; // 下面都是前后缀最大值
    for(int i = 2; i <= n; ++i) dp[i] = max(dp[i - 1], pv[i]);
    for(int i = n - 1; i >= 1; --i) ds[i] = max(ds[i + 1], pv[i]);
    while(q--){
        cin >> x >> y;
        LL left = LLONG_MIN;
        if(vp[x] > 1) left = max(left, dp[vp[x] - 1]);
        if(op[x] < n) left = max(left, ds[op[x] + 1]);
        cout << max(left, v[y] + f[x]) << endl;
    }
    return;
}

牛客周赛88 - 题解

A. 吔我大炮！

题意分析

题解

代码

B(B1). 梦间

题意分析

题解

代码

C(B2). 坠入

题意分析

题解

代码

D. 漫步

题意分析

题解

代码

E. 密藏

题意分析

题解

代码

F. 回响

题意分析

题解

代码

G. 升~龙~~

题意分析

题解

代码