AtCoder Beginner Contest 345

A - Leftrightarrow (abc345 A)

题目大意

给定一个字符串,问是不是形如<======...====>的字符串。

解题思路

根据长度构造出期望的字符串,再判断是否相等即可。

神奇的代码
s = input()
print("Yes" if s == "<" + "=" * (len(s) - 2) + ">" else "No")


B - Integer Division Returns (abc345 B)

题目大意

给定\(a\),输出 \(\lceil \frac{a}{10} \rceil\)

解题思路

上下取整的转换,\(\lceil \frac{a}{10} \rceil = \lfloor \frac{a + 9}{10} \rfloor\)。用下取整即可。

Python//是下取证,C++/是向\(0\)取整,即正数时是下取整,负数时是上取整

神奇的代码
a = int(input())
print((a + 9) // 10)


C - One Time Swap (abc345 C)

题目大意

给定一个字符串\(s\),长度为\(n\),问交换任意两个字符,可以得到的不同字符串个数。

解题思路

注意到交换的两个字符\(s_i \neq s_j\)不相同的话,得到的一定是个新的字符串,并且没有其他交换方式得到这个字符串。

\(s_i == s_j\)时,则字符串不变。

因此, 可以 总情况数-字符串不变数总情况数即为\(\frac{n(n-1)}{2}\)字符串不变数则是\((i,j)\)满足 \(s_i==s_j, i < j\)的个数,这是一个经典计数问题,维护\(s_i\)的出现次数即可\(O(n)\)求得。

最后特别注意一下原字符串\(s\)是否会出现,即有两个字母相同就会出现。

当然也可以正向统计。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    array<int, 26> cnt = {0};
    LL n = 1ll * s.size() * (s.size() - 1) / 2;
    for (auto c : s) {
        n -= cnt[c - 'a'];
        cnt[c - 'a']++;
    }
    if (ranges::max(cnt) > 1)
        ++n;
    cout << n << '\n';

    return 0;
}



D - Tiling (abc345 D)

题目大意

给定一个网格,有\(k\)块矩形板,问是否能选若干块板,恰好铺满网格,板可旋转。

解题思路

只有\(7\)块板,网格大小只有 \(10 \times 10\),范围比较小,可以直接搜索。

如何搜索呢?起初考虑每块板放在何处,这个复杂度比较大。

从左上考虑,没被覆盖的第一个格子一定是某块板的左上角,因此从左到右,从上到下,找到没被覆盖的第一个格子,枚举其被哪块板覆盖即可。

复杂度感性理解下不会很大

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, h, w;
    cin >> n >> h >> w;
    vector<array<int, 2>> a(n);
    for (auto& i : a) {
        cin >> i[0] >> i[1];
    }
    vector<vector<int>> full(h, vector<int>(w, 0));
    auto set_full = [&](int i, int j, int k, int v) {
        for (int x = 0; x < a[k][0]; x++) {
            for (int y = 0; y < a[k][1]; y++) {
                full[i + x][j + y] = v;
            }
        }
    };
    auto ok = [&](int i, int j, int k) -> bool {
        if (i + a[k][0] > h || j + a[k][1] > w)
            return false;
        for (int x = 0; x < a[k][0]; x++) {
            for (int y = 0; y < a[k][1]; y++) {
                if (full[i + x][j + y])
                    return false;
            }
        }
        return true;
    };
    auto find_unfull = [&]() -> pair<int, int> {
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if (!full[i][j])
                    return {i, j};
            }
        }
        return {-1, -1};
    };
    vector<int> used(n, 0);
    auto dfs = [&](auto self, int x, int y) -> bool {
        if (x == -1 && y == -1)
            return true;
        for (int i = 0; i < n; ++i) {
            if (used[i])
                continue;
            if (ok(x, y, i)) {
                set_full(x, y, i, 1);
                auto [nx, ny] = find_unfull();
                used[i] = 1;
                if (self(self, nx, ny))
                    return true;
                used[i] = 0;
                set_full(x, y, i, 0);
            }
            swap(a[i][0], a[i][1]);
            if (ok(x, y, i)) {
                set_full(x, y, i, 1);
                auto [nx, ny] = find_unfull();
                used[i] = 1;
                if (self(self, nx, ny))
                    return true;
                used[i] = 0;
                set_full(x, y, i, 0);
            }
            swap(a[i][0], a[i][1]);
        }
        return false;
    };
    if (dfs(dfs, 0, 0))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}



E - Colorful Subsequence (abc345 E)

题目大意

\(n\)个球排成一排,球有颜色\(c_i\),有价值\(v_i\)

现需恰好移除 \(l\)个球,使得俩俩球颜色不同,且剩下的球的价值和最大。问最大值。

解题思路

按顺序考虑每个球,我们的决策就是是否移除这个球。考虑我们需要哪些状态。

首先肯定是前\(i\)个球这个基本状态。由于要恰好移除 \(l\)个球,因此当前已经移除的球数也必须知道。

除此之外,对于当前球移除或不移除,还取决于上一个球的颜色,因为不能有相邻两个相同的颜色的球。

据此可以有两种 \(dp\)方式,一种朴素的是 \(dp[i][j][k]\)表示前 \(i\)个球,已经移除了 \(j\)个,且最后一个球的颜色是 \(k\)时的剩余球最大价值和。这样对于当前球移除与否都能转移。初见这个\(dp\)感觉时间复杂度是\(O(n^3k)\),但细想转移的话可见是 \(O(n^2k)\)

还有一种方式为 \(dp[i][j]\) 表示前\(i\)个球,且我保留第 \(i\)个球,并且已经移除了 \(j\)个球的最大价值和,转移就枚举上一个保留的球的下标,其时间复杂度是 \(O(nk^2)\)

由于 \(n\)\(10^5\), \(k\)\(500\),两者的时间复杂度都太高了。思考如何优化,事实上最后这两种方式都可以优化到 \(O(nk)\)

先考虑第一种 \(dp\)方式的转移式子:

\[dp[i][j][k] = \max ( dp[i - 1][j][k_1] + v_i, dp[i - 1][j - 1][k]) \]

其中\(1 \leq k_1, k \leq n\)表示颜色,且 \(k_1 \neq k\)。虽然这里是\(O(n^3k)\),但考虑到,如果保留球,实际上只有一个\(dp[i][j][k]\)会改动,需要遍历\(dp[i-1][j][k_1]\),如果不保留球,则直接 \(dp[i][j][k] = dp[i - 1][j - 1][k]\) ,转移是\(O(1)\),只有一个状态转移是 \(O(n)\)。所以总的是\(O(n^2k)\)

两大项的最大值分别对应着保留球移除球这两种决策。其中保留球的决策中,需额外条件\(k_1 \neq k\),即上一个球颜色不与当前球颜色相同。而 移除球的决策中,就一个值而已。

考虑如何优化转移,初看其实感觉很难优化,因为状态数就已经是\(O(n^2k)\),优化转移的同时刚好可以把状态数优化到\(O(nk)\)

对于后者转移,其就一项,转移就\(O(1)\),无需过多考虑。

对于前者转移,如果没有\(k \neq k_1\)的条件,我维护\(dp[i-1][j][...]\)的最值,那转移就不需要遍历 \(k_1\),通过维护的最值可以\(O(1)\)转移,就是在求 \(dp[i-1][j][...]\)的每一项时,就可以维护 \(mx[i-1][j] = \max(dp[i-1][j][...])\)

棘手的就是\(k_1 \neq k\)这个条件,就是要求\(dp[i-1][j][...]\)\(dp[i-1][j][k]\)这一项的最值。

如何处理这个条件呢?事实上我们除了维护最大值,再维护一个次大值,这两个的颜色一定是不同的,那转移时,一定就是从这两个选一个出来转移。

即维护\(mx[i-1][j] = [[MAX1, color], [MAX2, color]]\),这样,我每个\(dp[i][j][k]\)从可以从 \(mx[i-1][j]\)\(O(1)\)找到原转移式里的 \(\max(dp[i-1][j][k_1])\)这一项 ,得以转移。

转移式变为\(dp[i][j][k] = \max(mx[i - 1][j][0] + v_i, mx[i - 1][j][1] + v_i, dp[i - 1][j - 1][k])\) ,其中\(mx\)那部分要判断颜色是否不同\((c_i \neq color)\)。最后的答案即为\(\max(dp[n][l][...])\),或者说是 \(mx[n][l][0]\)

但至此,只是将一个转移从\(O(n)\)降到了 \(O(1)\),但状态数还是\(O(n^2k)\),降不下来 ,怎么办呢?

注意到状态里的\(k\),当初之所以定义\(k\)这个状态,是因为转移时要避免出现相邻球颜色相同(即能够转移),事实上这个状态非常冗余,它的用途只是为了转移,最后求解答案时不需要该状态(即对该状态的所有取值取个最值,而不关心具体是什么),观察上述的转移式,会发现这个\(k\)已经没有用了, 保留球的话转移从\(mx\)来就可以了,移除球的话,最终能成为\(mx[i][j]\)里的情况,也必定是 \(mx[i-1][j-1]\)里的最大值或次大值。

换句话说,这个 \(k\)的状态其实可以砍掉(就变成了 \(mx\)了),即 \(mx[i][j]\)表示前 \(i\)个球,移除 \(j\)个球后的两个两元组,分别表示(最大价值和,最后一个球的颜色)(次大价值和,最后一个球的颜色)。转移时同样考虑当前球保留或移除,保留的话,则从\(mx[i-1][j][0] + v \to mx[i][j]\)\(mx[i-1][j][1] + v \to mx[i][j]\) (看哪个颜色不同),移除的话就\(mx[i-1][j-1][0] \to mx[i][j]\)\(mx[i-1][j-1][1] \to mx[i][j]\),这样就维护出 \(mx[i][j]\)的最大值和次大值,可以转移了。

由于每个\(mx[i][j]\)的转移都是依赖上一个\(mx[i-1]\),这里也可以滚动数组优化下。

最后的时间复杂度是 \(O(nk)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL inf = 1e18;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<array<pair<LL, int>, 2>> dp(k + 1, {{{-inf, -1}, {-inf, -1}}});
    dp[0][0] = {0, 0};
    auto update = [&](array<pair<LL, int>, 2>& a, pair<LL, int> b) {
        if (b.first > a[0].first) {
            swap(a[0], b);
        }
        if (b.second != a[0].second && b.first > a[1].first) {
            swap(a[1], b);
        }
    };
    for (int i = 0; i < n; ++i) {
        int c, v;
        cin >> c >> v;
        vector<array<pair<LL, int>, 2>> dp2(k + 1, {{{-inf, -1}, {-inf, -1}}});
        for (int j = 0; j <= k; ++j) {
            if (dp[j][0].second != c) {
                update(dp2[j], {dp[j][0].first + v, c});
            }
            if (dp[j][1].second != c) {
                update(dp2[j], {dp[j][1].first + v, c});
            }
            if (j > 0) {
                update(dp2[j], dp[j - 1][0]);
                update(dp2[j], dp[j - 1][1]);
            }
        }
        dp.swap(dp2);
    }
    cout << max(-1ll, dp[k][0].first) << '\n';

    return 0;
}



还有另一种方式为 \(dp[i][j]\) 表示前\(i\)个球,且我保留第 \(i\)个球,并且已经移除了 \(j\)个球的最大价值和,转移就枚举上一个保留的球的下标,期间的球就被移除掉。其时间复杂度是 \(O(nk^2)\),其中状态数\(O(nk)\),转移耗时 \(O(k)\)

即转移式\(dp[i][j] = \max(dp[i - k - 1][j - k]) + v_i, c_i \neq c_{i - k - 1}\)

考虑如何优化转移。观察转移式,转移枚举的是\(0 \leq k \leq l\),将 \(dp[i][j]\)看作是一个二元函数的话,那一系列 \((i-k-1, j - k)\)点构成的是一条斜线,注意到这条斜线的特征是\(i-k-1-(j-k)=i-j-1\)是个定值。也就是说转移实际上就是在一条斜线取最值,但仍有 \(c_i \neq c_{i-k-1}\)这一棘手的条件。

对于这一棘手条件,处理的方法同上述一样,我们维护一条斜线的最大值和次大值。即\(mx[o]\)表示当前状态下, 满足\(i-j-1=o\)的这条斜线的\(dp[i][j]\)的最大值和次大值及其颜色,每个 \(dp[i][j]\)都从 \(mx[i-j-1]\)中得到颜色不相同的最值即可。这样转移就变为 \(O(1)\)了。

代码里是将\(mx[o]\)压成一个数,即我们的枚举顺序不是朴素的\(dp[i][0],dp[i][1],dp[i][2]...\),而是一条条斜线,即 \(dp[i][0],dp[i+1][1],dp[i+2][2],...,dp[i+1][0],dp[i+2][1]...\),当求完一条斜线的所有值时,再求下一条斜线。这样的话就不用保留其他斜线的最值信息,当需要的时候才算。朴素枚举顺序实际上是依次求每条斜线的每个点,所以需要保留历史信息,而当依次求完每条斜线时,就不需要保留其他斜线的信息了。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL inf = 1e18 + 7;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> c(n + 2), v(n + 2);
    for (int i = 1; i <= n; ++i) {
        cin >> c[i] >> v[i];
    }
    c[n + 1] = n + 1;
    n += 2;
    vector<vector<LL>> dp(n, vector<LL>(k + 1, -1));
    dp[0][0] = 0;
    for (int i = 1; i < n - k; i++) {
        array<pair<LL, int>, 2> mx{{{-inf, -1}, {-inf, -1}}};
        for (int j = 0; j <= k; ++j) {
            pair<LL, int> la = {dp[i + j - 1][j], c[i + j - 1]};
            if (la.first > mx[0].first)
                swap(la, mx[0]);
            if (la.second != mx[0].second && la.first > mx[1].first)
                swap(la, mx[1]);

            dp[i + j][j] = mx[c[i + j] == mx[0].second].first + v[i + j];
        }
    }
    cout << max(-1ll, dp.back().back()) << '\n';
    return 0;
}


F - Many Lamps (abc345 F)

题目大意

给定一张图,点上有灯,初始灯灭。

选择一条边,边上的两点的灯的状态会反转。

给出一种边的选择方案,使得恰好有\(k\)盏灯亮。

解题思路

是个构造题。初看这张图感觉无从下手,因为构造题一般要按照某种顺序执行,但图基本没有什么顺序可言。

可以在更简化的图考虑,比如图的\(DFS\)树,或者是生成树。

考虑在图的一棵生成树上,会发现有一种构造方法,可以使得根之外,其他点上的灯都能控制亮或灭。

从下往上,叶子到根考虑每个点,如果该点灯灭,则可以选择其父亲边,使其灯亮,或者灯亮变灯灭。

即每个点,都可以通过其父亲边使得它亮或灭,除了根节点之外,这个灯能亮能灭,全凭其点的度数是奇是偶。即一个连通块,除了个点之外,我能保证让其余点都灯亮。

注意到每选择一条边,要么两灯亮,要么两灯灭,要么一亮一灭,即亮灯数量始终是偶数。因此\(k\)是奇数的情况无解。

否则,注意原图不一定连通,则对于每个连通块,通过\(DFS\)从叶子考虑,尽量开满所有的灯,直到达到\(k\)盏灯为止,多开了就灭。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<array<int, 2>>> edge(n);
    vector<int> du(n, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edge[u].push_back({v, i + 1});
        edge[v].push_back({u, i + 1});
    }
    if (k & 1) {
        cout << "No" << endl;
        return 0;
    }

    int up = 0;
    vector<int> vis(n, 0);
    vector<int> ans;
    function<void(int, int, int)> dfs = [&](int u, int fa, int fa_id) {
        debug(u, fa, fa_id);
        int cnt = 0;
        vis[u] = 1;
        for (auto& [v, id] : edge[u]) {
            if (vis[v] == 0) {
                dfs(v, u, id);
            }
        }
        if (du[u] & 1) {
            --k;
        }
        if (u != fa) {
            if (k > 0 && (~du[u] & 1)) {
                ans.push_back(fa_id);
                --k;
                du[u]++;
                du[fa]++;
            } else if (k < 0 && (du[u] & 1)) {
                ans.push_back(fa_id);
                ++k;
                du[u]++;
                du[fa]++;
            }
        }
    };
    for (int i = 0; i < n; i++) {
        if (k != 0 && vis[i] == 0) {
            dfs(i, i, -1);
        }
    }
    if (k != 0)
        cout << "No" << '\n';
    else {
        cout << "Yes" << '\n';
        cout << ans.size() << '\n';
        for (auto& i : ans)
            cout << i << ' ';
        cout << '\n';
    }

    return 0;
}



G - Sugoroku 5 (abc345 G)

题目大意

扔骰子,\([1,k]\)等概率出现。

对于每个 \(i \in [1,n]\),问扔\(i\)次骰子后,其和 \(\geq n\)的概率。

解题思路

<++>

神奇的代码



热门相关:重生全能悍妻:张狂大小姐   不负荣光,不负你   隐婚99天:首长,请矜持   盖世双谐   校花之贴身高手