讨论详情 - QY code

8.4日总结

今天的考试内容有几道水题，还有几道很简单就能骗分的题目，但是我在细节处理上好像并没有做得多好，然后就丢失了一点点分（“亿”点点）。今天的考试内容差不多都是dp，除了一道签到题和一道数学题以外，考了线性 DP、计数 DP 容斥、树上 DP、数学转化贪心（这个似乎也不是dp）、签到、区间 DP。

考试题目：

T1:Mortal Kombat Tower

链接：Mortal Kombat Tower - 题目详情 - QY code

题意：朋友先手，交替回合，每回合可以消灭 1 或 2 个 boss；朋友遇到 hard boss (1) 消耗 1 点 skip，我方不消耗。求打完所有 boss 朋友最少消耗多少 skip。

算法：线性 DP
状态设计：dp[i][0/1]处理前i个 boss，下一轮操作的人是朋友 / 自己，最小消耗点数。
转移：每回合取 1 个或者 2 个 boss；朋友操作时统计区间内 1 的数量加到代价，我方操作代价不变。
边界：第一个回合一定是朋友；数据范围 $n \leq 2 \times 10^5$ ，要求 $O(n)$ 。
关键点：状态第二维保存接下来是谁操作，而不是刚刚是谁操作；每次只能连续拿 1‑2 个元素

代码：

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int s[200010];
int a[200010]; 
int dp[200010][2];
int main () {
    freopen ("mkt.in", "r", stdin);
    freopen ("mkt.out", "w", stdout);
    int T;
    scanf ("%d", &T);
    while (T--) {
        int n;
        scanf ("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf ("%d", &a[i]);
            s[i] = s[i - 1] + a[i];
        }
        for (int i = 0; i <= n; i++) {
            dp[i][0] = INF;
            dp[i][1] = INF;
        }
        dp[0][0] = 0;
        for (int i = 0; i <= n; i++) {
            if (dp[i][0] == INF && dp[i][1] == INF) continue;
            if (dp[i][0] != INF) {
                if (i + 1 <= n) {
                    int cost = s[i + 1] - s[i];
                    dp[i + 1][1] = min (dp[i + 1][1], dp[i][0] + cost);
                }
                if (i + 2 <= n) {
                    int cost = s[i + 2] - s[i];
                    dp[i + 2][1] = min (dp[i + 2][1], dp[i][0] + cost);
                }
            }
            if (dp[i][1] != INF) {
                if (i + 1 <= n) dp[i + 1][0] = min (dp[i + 1][0], dp[i][1]);
                if (i + 2 <= n) dp[i + 2][0] = min (dp[i + 2][0], dp[i][1]);
            }
        }
        printf ("%d\n", min (dp[n][0], dp[n][1])); 
    }
    return 0;
}

T2:k-Tree:

链接：k-Tree - 题目详情 - QY code

题意：从根出发走路径，边权可取1~k，路径边权总和恰好等于n，求至少一条边权≥d的路径总数，对 $10^9+7$ 取模。

算法：计数 DP + 容斥原理
思路：“至少一个” 经典容斥：答案 =全部合法总路径 −所有边都小于d的路径。
dp 定义：dp[s]总和为s的路径方案数；(dp[0]=1)。
关键点：不要在 dp 里增加标记是否选过大边的维度，用容斥简化；(n,k\le100)，小范围 DP。

做对这道题目是要有一定的代码实现能力的，而且在没有大数据的情况下，要做对需要对细节的处理把控的很严，我今天就栽在这了。

代码：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007; 
int n, k, d;
int dp[110];
int query (int m) {
    memset (dp, 0, sizeof (dp));
    for (int i = 1; i <= n; i++) dp[i] = 0;
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min (m, i); j++) {
            dp[i] = (dp[i] + dp[i - j]) % MOD; 
        }
    }
    return dp[n];
}
int main () {
    freopen ("ktree.in", "r", stdin);
    freopen ("ktree.out", "w", stdout); 
    scanf ("%d%d%d", &n, &k, &d);
    if (d > n) {
        puts ("0");
        return 0;
    } 
    int sum = query (k);
    int tmp = query (d - 1);
    int ans = (sum - tmp + MOD) % MOD;
    printf ("%d", ans);
    return 0;
}

在考试的时候我写的代码里是没有memset(dp, 0, sizeof (dp))和求ans的那两行的，所以我痛失8分，那可是整整8分啊！

T3:Parsa's Humongous Tree:

链接：Parsa's Humongous Tree - 题目详情 - QY code

题意：树上每个点u可以选 $[l_u, r_u]$ 内任意整数，最大化所有边 $|a_u-a_v|$ 的总和。

算法：树上 DP
核心结论：要让绝对值最大，每个节点最优取值只能是区间的两个端点 $l_u$ 或者 $r_u$ ，中间数值一定不会得到更优解。
状态：dp[u][0]u 取左端点，子树最大贡献；dp[u][1]u 取右端点，子树最大贡献。
转移：对每个儿子，4 种组合取最大值累加。
关键点：树上绝对值最大化固定结论； $n≤10^5$ ，DFS 线性遍历，不能暴力枚举区间内所有数。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l[100010], r[100010]; 
vector <int> eg[100010]; 
ll dp[100010][2];
bool vis[100010];
void dfs (int u, int fa) {
    dp[u][0] = 0;
    dp[u][1] = 0;
    for (int v : eg[u]) {
        if (v == fa) continue;
        dfs (v, u);
        ll a = max (dp[v][0] + abs (l[u] - l[v]), dp[v][1] + abs (l[u] - r[v]));
        ll b = max (dp[v][0] + abs (r[u] - l[v]), dp[v][1] + abs (r[u] - r[v]));
        dp[u][0] += a;
        dp[u][1] += b;
    }
}
int main () {
    freopen ("parsatree.in", "r", stdin);
    freopen ("parsatree.out", "w", stdout);
    int T;
    scanf ("%d", &T);
    while (T--) {
        int n;
        scanf ("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf ("%lld%lld", &l[i], &r[i]);
            eg[i].clear ();
        }
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf ("%d%d", &u, &v);
            eg[u].push_back (v);
            eg[v].push_back (u);
        } 
        dfs (1, -1);
        printf ("%lld\n", max (dp[1][0], dp[1][1]));
    }
    return 0;
}

这道题，怎么说呢，算是一道细节题，你甚至要思考出思路来十分容易。首先，你要知道，因为有T组数据，所以作为全局变量的eg[]是需要clear()的，不然就会与上一轮的数据混淆，那就完蛋了。其次，对于这道题目，在做状态转移的时候，千万不能直接什么dp[u][0]=...，然后再dp[u][1]=...，那样dp[u][0]会被先覆盖掉，等你来更新dp[u][1]的时候就晚了~~（这个小错误我改了将近10分钟）~~

T4:Four Segments

链接：Four Segments - 题目详情 - QY code

题意：给定数组，选取三个分隔下标 $delim_0≤delim_1≤delim_2$ ，最大化$res=sum(0,d_0)-sum(d_0,d_1)+sum(d_1,d_2)-sum(d_2,n)$，输出一组分割下标。

思路：

考场上一开始：

算法：前缀和数学变形 + 预处理最优位置
数学化简：把区间和全部改写为前缀数组S，原式等价最大化 $2*(s[d_0]-s[d_1]+s[d_2])$ ，s[n]为常数不影响选择
做法：预处理每个位置左边最大s的下标、右边最大s的下标；枚举中间 $d_1$ ，快速拿到最优 $d_0,d_2$ 。
关键点：代数化简是本题核心，把四重区间运算降维；需要输出方案，不能只算最大值； $n \le 5000$ 。

这个思路多么的棒，但是我的代码跟屎山一样，而且，它，还是错的：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll a[5010], s[5010];
ll pre[5010], suf[5010];
int ppos[5010], spos[5010];
int main () {
    int n;
    scanf ("%d", &n);
    s[0] = 0;
    for (int i = 0; i < n; i++) {
        scanf ("%lld", &a[i]);
        s[i + 1] = s[i] + a[i];
    }
    pre[0] = s[0], ppos[0] = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] > pre[i - 1]) {
            pre[i] = s[i];
            ppos[i] = i;
        }
        else {
            pre[i] = pre[i - 1];
            ppos[i] = ppos[i - 1];
        }
    }
    suf[n] = s[n];
    spos[n] = n;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] > suf[i + 1]) {
            suf[i] = s[i];
            spos[i] = i;
        }
        else {
            suf[i] = suf[i + 1];
            spos[i] = spos[i + 1];
        }
    }
    ll best = -INF;
    int ans0, ans1, ans2;
    for (int d1 = 0; d1 <= n; d1++) {
        int d0 = ppos[d1];
        int d2 = spos[d1];
        ll res = pre[d1] - s[d1] + suf[d1];
        if (res >= best) {
            best = res;
            ans0 = d0;
            ans1 = d1;
            ans2 = d2;
        }
    }
    printf ("%d %d %d", ans0, ans1, ans2);
    return 0;
}

我看了之后，果断放弃了这种做法，选择了另一种暴力一点的方法。

思路：

枚举 $d_1$ ，再选择 $d_0和d_1$ 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll s[5010];
int main () {
    freopen ("fs.in", "r", stdin);
    freopen ("fs.out", "w", stdout);
    int n;
    scanf ("%d", &n);
    s[0] = 0;
    for (int i = 0; i < n; i++) {
        ll x;
        scanf ("%lld", &x);
        s[i + 1] = s[i] + x;
    }
    ll max = -INF;
    int a0, a1, a2;
    for (int d1 = 0; d1 <= n; d1++) {
        ll best0 = -INF;
        int pos0 = 0;
        for (int d0 = 0; d0 <= d1; d0++) {
            if (s[d0] > best0) {
                best0 = s[d0];
                pos0 = d0;
            }
        }
        for (int d2 = d1; d2 <= n; d2++) {
            ll cur = best0 - s[d1] + s[d2];
            if (cur > max) {
                max = cur;
                a0 = pos0;
                a1 = d1;
                a2 = d2;
            }
        }
    }
    printf ("%d %d %d\n", a0, a1, a2);
    return 0;
}

T5:Slime：

链接：Slime - 题目详情 - QY code

题意： 史莱姆每次吞噬相邻左右其中一个，新分数 = 自身−被吞史莱姆；全部合并成一个，求最终最大分数。

算法：思维 / 贪心，无 DP
核心模型：吞噬操作等价给每一个元素分配符号(+)或者(-)，至少要有一个元素为正，求 $\sum a_i$ 最大值。
结论：
1. 数组存在正数：答案等于全部元素绝对值之和；
2. 全是负数：保留最大的那个负数为正，其余全部取负。
关键点：不要模拟吞噬过程，模拟会 TLE； $n\le5*10^5$ 要求 $O(n)$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[500010];
int main () {
    freopen ("slime.in", "r", stdin);
    freopen ("slime.out", "w", stdout);
    int n;
    scanf ("%d", &n);
    ll sum = 0, minn = 1e18;
    bool flag1 = false, flag2 = false;
    for (int i = 1; i <= n; i++) {
        scanf ("%lld", &a[i]);
        sum += abs (a[i]);
        minn = min (minn, abs (a[i]));
        if (a[i] > 0) flag1 = true;
        if (a[i] < 0) flag2 = true; 
    }
    if (n == 1) {
        printf ("%lld", a[1]);
        return 0;
    }
    if (flag1 && flag2) {
        printf ("%lld", sum);
        return 0;
    }
    printf ("%lld", sum - 2 * minn);
    return 0;
}

这个代码把我打崩溃了，为什么这个题在我补题之前只拿了可怜的32分呢，因为我的输出全部都是printf ("%d",...)，但是，我应该输出的是全都是long long类型的，我全干成int类型了。

T6:Recovering BST

链接：Recovering BST - 题目详情 - QY code

题意： 给出 BST 的中序遍历（升序数组），构造一棵 BST，要求每条边连接两点，判断是否可行。

考场思路：

在考场上，我因为时间原因，连想正解的时间都没有，但我选择了最聪明的解决方法：看一眼样例输出就会发现，输出都是Yes和No，也就是说，我只要选择一个输出就能拿将近一半的分，于是我的代码产生了：

#include <bits/stdc++.h>
using namespace std;
int n;
int a[710];
int main () {
	freopen ("bst.in", "r", stdin);
	freopen ("bst.out", "w", stdout);
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++) scanf ("%d", &a[i]);
	puts ("Yes");
	return 0;
}

看看，就是这份伟大的代码，让我拿到了41一分！~~（也就是说，输出No能拿59分）~~

算法：区间 DP
BST 性质：中序遍历[l,r]，选取k做根，左子树[l,k-1]，右子树[k+1,r]。
dp 状态：dp[l][r]表示中序区间[l,r]能否构成合法子树；枚举根k，要求根和左右孩子gcd>1，左右子区间各自合法。
关键点： $n\le700$ ，朴素 $O(n^3)$ 会超时，需要做状态优化；BST 中序固定，区间选根是经典模型。

代码：

#include <bits/stdc++.h>
using namespace std;
int n;
int a[710];
bool L[710][710], R[710][710];
int gcd (int x, int y) {
    while (y) {
        int t = x % y;
        x = y;
        y = t;
    }
    return x;
} 
int main () {
    freopen ("bst.in", "r", stdin);
    freopen ("bst.out", "w", stdout);
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++) scanf ("%d", &a[i]);
    for (int i = 1; i <= n + 1; i++) {
        L[i][i - 1] = true;
        R[i][i - 1] = true;
    }
    for (int len = 1; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            L[l][r] = false;
            R[l][r] = false;
            for (int k = l; k <= r; k++) {
                bool leftok = R[l][k - 1];
                bool rightok = L[k + 1][r];
                if (!leftok || !rightok) continue;
                if (l > 1 && gcd (a[l - 1], a[k]) > 1) L[l][r] = true;
                if (r < n && gcd (a[k], a[r + 1]) > 1) R[l][r] = true;
            }
        }
    }
    for (int root = 1; root <= n; root++) {
        bool left = (root == 1 || R[1][root - 1]);
        bool right = (root == n || L[root + 1][n]);
        if (left && right) {
            puts ("Yes");
            return 0;
        }
    }
    puts ("No");
    return 0;
}

8.4总结

考试题目：

0 条评论

目前还没有评论...

8.4总结

考试题目：

0 条评论

目前还没有评论...

还没有账户？

登录