训练赛4题解

t1

题解
根据题意直接模拟即可，这里采用的写法是用一个变量维护上一个失败场次的位置
代码

#include <bits/stdc++.h>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> PII;
using ll = long long;
using i64 = long long;
vector<vector<int>> g;
void solve()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int ans = 0;
    int lst = -1;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'W')
        {
            if (i - lst >= 3)
                ans += k;
            else
                ans++;
        }
        else if (s[i] == 'L')
        {
            ans--;
            lst = i;
        }
    }
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

t2

题解
田忌赛马问题，一个比较显然的贪心是将 $a,b$ 排序后，将 $a$ 从大到小枚举，找剩余的 $b$ 中小于 $a[i]$ 的最大值
接下来我们使用归纳法进行证明

设数组 $a_1$ 为 $a$ 当前剩余的动作， $b_1$ 为 $b$ 当前剩余的动作考虑 $a_1$ 中最大的元素 $x$ 应该与 $b_1$ 中哪个元素配对，显然是与小于 $x$ 的元素中最大元素 $y$ 的那个配对最优，如果选择其他元素的一定，可以通过交换论证法，将 $b_1$ 中被配对的元素换为 $y$ 一定不影响结果不选 $x$ 的情况，也可以通过交换论证法证明

代码

// 不带T
#include <bits/stdc++.h>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> PII;
using ll = long long;
using i64 = long long;
vector<vector<int>> g;
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    vector<int> b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    sort(all(a));
    sort(all(b));
    int ans = 0;
    for (int i = n - 1, j = m - 1; i >= 0; i--)
    {
        while (j >= 0 and b[j] >= a[i])
            j--;
        if (j != -1)
        {
            ans++;
            j--;
        }
    }
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
} // 不带T
#include <bits/stdc++.h>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> PII;
using ll = long long;
using i64 = long long;
vector<vector<int>> g;
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    vector<int> b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    sort(all(a));
    sort(all(b));
    int ans = 0;
    for (int i = n - 1, j = m - 1; i >= 0; i--)
    {
        while (j >= 0 and b[j] >= a[i])
            j--;
        if (j != -1)
        {
            ans++;
            j--;
        }
    }
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

t3 S=√[p(p-a)(p-b)(p-c)]，其中p = (a + b + c) / 2

题解
正解是对于每根木棍有四种状态，放在第一条边，第二条边，第三条边，不使用。复杂度是 $4^n$
使用dfs，或者从0枚举到 $(1<<(n*2))$ 都是可以的

如果考虑动态规划的话，复杂度是 sum(a) * sum(a) * sum(a) * n，具体来说就是设dp[i][j][k]为三条边的长的情况是否存在显然在这道题时不可以的

当然有通过一些奇怪方法过的，显然是不对的。这里就不得不说牛客平台的一个问题，数据太弱了，经常让水做法混过去。如果是Codeforces 或者 Atcoder的精心构造数据绝对不会这样但是这其实是一个很常见的问题，特别是在一些比较水的比赛里，但是如果是XCPC比赛里比较负责的出题组，就几乎不会出现这样情况了，至少不会出现这么低级的情况

代码

#include <bits/stdc++.h>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> PII;
using ll = long long;
using i64 = long long;
vector<vector<int>> g;
int check(vector<int> &t)
{
    sort(t.begin(), t.begin() + 3);
    return t[0] + t[1] > t[2];
}
void solve()
{
    int n;
    cin >> n;
    // √[p(p-a)(p-b)(p-c)]，其中p = (a + b + c) / 2。
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    double ans = -1;
    for (int mask = 0; mask < (1 << (2 * n)); mask++)
    {
        vector<int> t(4);
        int mask1 = mask;
        for (int j = 0; j < n; j++)
        {
            t[mask1 % 4] += a[j];
            mask1 /= 4;
        }
        if (check(t))
        {
            double p = (double)(t[0] + t[1] + t[2]) / 2;
            ans = max(ans, sqrt(p * (p - t[0]) * (p - t[1]) * (p - t[2])));
        }
    }
    cout << fixed << setprecision(6);
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while (T--)
    {
        solve();
    }
}

t4

题解
首先可以观察到为有趣的区间等价于区间中有一个奇数（也就是二进制最后一位为1）于是我们可以将数组 $a[i]$ 转化为只有0,1 我们提供两种思路： 1.答案=区间总数 - 只含0的区间

从前向后枚举,设当前枚举到第 $i$ 位，每次加上以当前位结尾的区间的数量分两种情况 (1) $a[i] = 1$ $ans += i$ (2) $a[i] = 0$ $ans += 上一个为1的i$

代码

#include <bits/stdc++.h>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> PII;
using ll = long long;
using i64 = long long;
vector<vector<int>> g;
void solve()
{
    int n; 
    cin >> n;
    vector<int>a(n);
    for(int i =0 ;i < n;i++)
    {
        cin >> a[i];
        a[i] %= 2;
    }
    int ans = 0;
    int cnt = 0;
    for(int i = 0 ;i < n;i++)
    {
        if(i!=0 and a[i] != a[i - 1])
        {
            if(a[i - 1] == 0)
                ans += cnt * (cnt + 1) / 2;
            cnt = 0;
        }
        cnt++;
    }
    //cerr << cnt << '\n';
    if(a[n - 1] == 0 and cnt)
        ans += cnt * (cnt + 1) / 2;
    ans = n * (n + 1) / 2 - ans;
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    while (T--)
    {
        solve();
    }
}

t5 moon

题解

答案是David一定赢，但是我们关注的是做题的思路和证明。

做题之前，先复习一下SG函数，必败态的SG(x) = 0，必胜态的 SG(x) > 0 若一个状态有后继状态 x1,x2,x3 ，则该状态的 SG(x) = mex(SG(x1),SG(x2),SG(x3))

如果当前有几个独立的公平组合游戏y1,y2,y3，则总的SG(y) = SG(y1) ^ SG(y2) ^ SG(y3)

首先看题目，一棵树，状态有很多，那么就不能通过求直接求SG函数的方法来求解然后我们通过模拟或者猜测，就大概可以猜出先手的优势是很大的

然后证明：

设当前是一颗以S为根的字数，T1,T2,T3为其子树

若我们操作时选择其中一颗子树中的节点，此时操作后子节点为黑色，不能操作，所以这种情况下操作前的树的SG(x) = SG(T1) ^ SG(T2) ^ SG(T3)

若我们选择根节点进行操作，则此时的的后继状态为的 SG(x) = SG(T1) ^ SG(T2) ^ SG(T3) ，而操作前的状态为mex(SG(x))

这也就是说我们可以选择设定当前状态的SG函数值上面两个的SG中的一种，一定有一个为1，即先手必胜

代码

cout << "David\n";

t6 yyc?

题解

构造题，这个不太好讲。

先直接说一下做法，先写下一个足够长的只有字符 $y$ 的字符串( $1e4足够$ )，然后可以发现，在这个串中插入字符 $c$ 的话，每次增加的结果是： $x * (x - 1) / 2$ （ $x$ 为插入的 $c$ 前字符 $y$ 的数量）。于是我们可以通过从这个字符串的右侧开始遍历，然后判断如果在当前插入会不会导致yyc的数量超过n，不超过就可以放。

然后因为 $C(n,2)$ 的数据增长速度，我们可以简单判断出这样是一定可以的题目要求的范围内得到答案的，而且因为 $C(2,1) = 1$ 我们也不需要额外的特判来保证能不能恰好得到 $n$

这种题没什么好说的，就是自己手玩一下，或者手玩很多下慢慢试出来，还有就是套路的积累。也可以说所有的题都是套路，毕竟思考一个问题的角度就那么几种，一定是能有套路的，慢慢就积累就是了。

代码

#include <bits/stdc++.h>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> PII;
using ll = long long;
using i64 = long long;
vector<vector<int>> g;
void solve()
{
    int n;
    cin >> n;
    int N = 1e4;
    string s = "";
    for(int i = N ;i >= 1;i--){
        int num = i * (i - 1) / 2;
        while(n >= num and num !=0){
            n -= num;
            s += "c";
        }
        s += "y";
    }
    reverse(all(s));
    cout << s.size() << '\n';
    cout << s << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

t7

题解

首先有个众所周知的结论

一个数能被3整除当且仅当该数的各位和能够被3整除

不知道这个从小就知道的结论知不知道他的证明，这里我来额外说一下这是因为 $10 \% 3 = 1$ ，为什么呢，因为这也等式就是在说 10 和 1 在取模3下的贡献是一样的

接下来：

我们可以很显然地将所有数字根据数位和%3 的结果分为三类设一个数组 $dp[3]$ 表示这三类的数的数量 $dp[0] = 1$ 表示空集

之后我们从1到9地遍历显然地，对于每个种数字，我们可以放1个，放2个，放3个.....放 $cnt[i]$ 个可以发现，这 $cnt[i]$ 种状态也可以分为三类，用数组表示出来 $dp_1[3]$

之后我们可以将 $dp$ 和 $dp_1$ 进行合并(就是将各自代表的数进行拼接)得到新的 $ndp$ ,具体来说就是 $ndp[(i + j) \% 3] = dp[i] * dp[j] (mod\ 1e9+7)$

最后的 $dp[0]$ 就是我们需要的结果

代码

//不带T
#include <bits/stdc++.h>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> PII;
using ll = long long;
using i64 = long long;
vector<vector<int>> g;
const int mod = 1e9 + 7;
void solve()
{
    vector<int>cnt(10);
    for(int i = 1;i <= 9;i++)
        cin >> cnt[i];
    vector<int> dp(3);
    dp[0] = 1;
    for(int i = 1;i <= 9;i++){
        vector<int> dp1(3);
        if(i % 3 == 0){
            dp1[0] = cnt[i];
        }else if(i % 3 ==1){
            dp1.assign(3,cnt[i] / 3);
            for(int j = 0;j < cnt[i] % 3;j++){
                dp1[(1 + j) % 3]++;
            }
        }else{
            dp1.assign(3,cnt[i] / 3);
            for(int j = 0;j < cnt[i] % 3;j++){
                dp1[2 - j]++;
            }
        }
        vector<int>ndp = dp;
        for(int j = 0;j < 3;j++){
            for(int k = 0;k < 3;k++){
                (ndp[(j + k) % 3] += dp[j] * dp1[k] % mod)%=mod;
            }
        }
        dp = ndp;
    }
    cout << dp[0] << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

t8 压轴题

题解

首先看题目一棵树，有边权。

找到一条总长不超过S的路径，使得其他点到使这条路径的距离最大值最小。

首先要观察到一个结论，这条路径一定在直径上。尝试证明....。

先求出直径。

之后我们可以找到一个比较显然的做法，先二分到距离最大值，先二分直径的右端点，再二分左端点，这样就能够找到满足要求的最小路径长度。但是 $nlog^2n$ 考虑常数和数据范围不太可能

那我们继续观察，发现可以将点分为直径上的点和不在直径上的点，不在直径上的点对于答案的贡献是固定的(证明)。因此我们只用考虑直径上的点，通过双指针维护当前选择的是直径上哪段区间即可。

实现起来代码很长，非常考验你的代码能力。

代码

// 不带T
#include <bits/stdc++.h>
#ifdef LOCAL
#define cerr std::cerr
#else
#define cerr   \
    if (false) \
    std::cerr
#endif
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> PII;
using ll = long long;
using i64 = long long;
vector<vector<PII>> g;

void solve()
{
    int n, s;
    cin >> n >> s;
    g.assign(n, vector<PII>());
    for (int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<int> dis(n, -1), fa(n, -1);
    auto bfs = [&](int x)
    {
        queue<int> q;
        dis.assign(n, -1);
        q.push(x);
        dis[x] = 0;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto [y, d] : g[u])
            {
                if (dis[y] == -1)
                {
                    dis[y] = dis[u] + d;
                    fa[y] = u;
                    q.push(y);
                }
            }
        }
        return max_element(all(dis)) - dis.begin();
    };
    vector<int> st(n);
    // tmp -> tmp2
    auto get_dia = [&]()
    {
        int tmp = bfs(0);
        int tmp2 = bfs(tmp);
        cerr << tmp << ' ' << tmp2 << '\n';
        vector<int> dia;
        int now = tmp2;
        while (now != tmp)
        {
            dia.push_back(now);
            st[now] = 1;
            now = fa[now];
        }
        st[tmp] = 1;
        dia.push_back(tmp);
        return dia;
    };

    auto dia = get_dia();
    for (int i = 0; i < dia.size(); i++)
        cerr << dia[i] << ' ';
    cerr << '\n';
    vector<int> dp(n);
    vector<int> vis(n, 0);
    auto dfs = [&](auto self, int x, int fat) -> void
    {
        if (vis[x])
            return;
        vis[x] = true;
        for (auto [y, d] : g[x])
        {
            if (y == fat || st[y])
                continue;

            self(self, y, x);
            dp[x] = max(dp[x], dp[y] + d);
        }
    };
    for (int i = 0; i < n; i++)
        if (st[i])
            dfs(dfs, i, -1);

    // dis[m - 1] = 0
    int m = dia.size();
    int res = 0;
    for (int i = 0; i < n; i++)
        if (st[i])
            res = max(res, dp[i]);

    cerr << res << '\n';
    int ans = 1e18;
    for (int R = m - 1, L = m - 1; R >= 0; R--)
    {
        while (L >= 0 and dis[dia[L]] - dis[dia[R]] <= s)
        {
            L--;
        }
        ans = min(ans, max(dis[dia[R]], (L + 1 < m) ? dis[dia[0]] - dis[dia[L + 1]] : 0));
    }
    ans = max(ans, res);
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

题解 | #训练赛4#

训练赛4题解

t1

t2

t3 S=√[p(p-a)(p-b)(p-c)]，其中p = (a + b + c) / 2

t4

t5 moon

t6 yyc?

t7

t8 压轴题