首页 > 其他分享 >AtCoder Beginner Contest 345 A-F 题解

AtCoder Beginner Contest 345 A-F 题解

时间：2024-03-19 13:25:00浏览次数：20  
标签：AtCoder pq 345 int 题解 leq vector dp 10

A - Leftrightarrow

Question

给你一个由 <、= 和 > 组成的字符串 \(S\) 。
请判断 \(S\) 是否是双向箭头字符串。
字符串 \(S\) 是双向箭头字符串，当且仅当存在一个正整数 \(k\) ，使得 \(S\) 是一个 <、 \(k\) 个 = 和一个 >的连接，且顺序如此，长度为 \((k+2)\) 。

Solution

按照题意模拟

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    if (s[0] != '<') {printf("No\n"); return 0;}
    if (s.back() != '>') {printf("No\n"); return 0;}
    for (int i = 1; i < s.size() - 1; i++) {
        if (s[i] != '=') {printf("No\n"); return 0;}
    }
    printf("Yes\n");
}

B - Integer Division Returns

Quesiton

给定一个介于 \(-10^{18}\) 和 \(10^{18}\) 之间的整数 \(X\) ，打印 \(\left\lceil \dfrac{X}{10} \right\rceil\) 。
这里， \(\left\lceil a \right\rceil\) 表示不小于 \(a\) 的最小整数。

Solution

分类讨论，如果 \(a\) 能整除 \(10\)，那么答案就是 \(\frac{a}{10}\)

  • 如果 \(a\) 是正数，输出 \(\lfloor \frac{a}{10}\rfloor + 1\)

  • 如果 \(a\) 是负数，输出 \(\lfloor \frac{a}{10}\rfloor\)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll n; cin >> n;
    if (n % 10 == 0) {
        cout << n / 10 << '\n';
    }
    else {
        if (n > 0) {
            cout << n / 10 + 1 << '\n';
        }
        else {
            cout << n / 10 << '\n';
        }
    }
}

C - One Time Swap

Question

给你一个字符串 \(S\) 。请找出以下操作 \(1\) 次的字符串数。

  • 设 \(N\) 是 \(S\) 的长度。选择一对整数 \((i,j)\) 使得 \(1\leq i\lt j\leq N\) 和 \(S\) 的 \(i\) -th 和 \(j\) -th 字符互换。

Solution

考虑交换的对数是 \(\frac{n(n+1)}{2}\)

如果一个字母，和之前相同的字母交换，得到的还是原串，否则得到的串是一个新串

所以我们只需要统计每个字符与之前的多少个字母不同就可以得到答案

注意要判断是否能得到原串

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    string s; cin >> s;
    ll n = s.size(); s = " " + s;
    vector<ll> num(26,0);
    ll ans = 0, flg = 0;
    for (int i = 1; i <= n; i++) {
        if (num[s[i] - 'a'] > 0) flg = 1;
        num[s[i] - 'a']++;
        ans += i - num[s[i] - 'a'];
    }
    cout << ans + flg << '\n';
}

D - Tiling

Quesiton

有一个由 \(H\) 行和 \(W\) 列组成的网格，每个单元格的边长为 \(1\) ，我们有 \(N\) 块瓷砖。
其中的 \(i\) 瓷砖（ \(1\leq i\leq N\) ）是一个大小为 \(A_i\times B_i\) 的矩形。
请判断是否有可能将这些瓷砖放置在网格上，从而满足以下所有条件：

  • 每个单元格都正好被一个图块覆盖。
  • 有未使用的瓦片也没关系。
  • 瓷砖在放置时可以旋转或翻转。但是，每块瓦片必须与单元格的边缘对齐，不得超出网格。

\(N\le7,H,W\le 10\)

Solution

考虑到 \(N,H,W\) 都特别小，直接暴力

直接枚举放瓷砖的顺序以及每块砖是否旋转，最后暴力放砖即可

我在放砖的时候使用了优先队列，所以时间复杂度为 \(O(HW\log HW)\)

实际上判断放砖可以优化到 \(O(HW)\)

总时间复杂度就为 \(O(N!\cdot 2^N\cdot HW)\)

Code

#include <bits/stdc++.h>
using namespace std;

typedef vector<vector<int> > vvi;
typedef pair<int, int> pii;


int main() {
    int n; cin >> n;
    int H, W; cin >> H >> W;
    vector<pii> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
    }

    auto check = [&]  (vector<int> &id, int S) {
        vector<vector<int> > v(H + 1, vector<int>(W + 1,0));
        priority_queue<pii, vector<pii>, greater<pii> > pq;
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                pq.push({i,j});
            }
        }
        for (int i = 1; i <= n; i++) {
            auto &[dx, dy] = a[id[i]];
            if (S >> (i - 1) & 1) 
                swap(dx, dy);
            while (!pq.empty() && v[pq.top().first][pq.top().second]) pq.pop();
            if (pq.empty()) {return 1;}
            auto [x, y] = pq.top(); pq.pop();
            for (int i_ = x; i_ < x + dx; i_++) {
                for (int j_ = y; j_ < y + dy; j_++) {
                    if (i_ > H || j_ > W || v[i_][j_] == 1) return 0;
                    v[i_][j_] = 1;
                }
            }
        }
        while (!pq.empty() && v[pq.top().first][pq.top().second]) pq.pop();
        if (pq.empty()) return 1;
        return 0;
    };

    vector<int> id (n + 1);
    iota(id.begin(), id.end(), 0);
    do {
        for (int S = 0; S < (1<<n); S++) 
            if (check(id, S)) {cout << "Yes\n"; return 0;}  
    } while (next_permutation(id.begin() + 1, id.end()));
    cout << "No\n";
    return 0;
}

E - Colorful Subsequence

Question

有 \(N\) 个球排成一排。
左边的 \(i\) 个球的颜色是 \(C_i\) ，数值是 \(V_i\) 。

高桥希望在不改变顺序的情况下，将这一行中的 \(K\) 个球移除，这样在排列剩余的球时，就不会有相邻的两个球颜色相同。此外，在此条件下，他希望最大化这一行中剩余球的总价值。

请计算高桥是否能移除 \(K\) 个球，使剩下的一行中没有相邻的两个球颜色相同。如果可以，求剩余球的最大总值。

  • \(1\leq K\lt N\leq 2\times 10^5\)
  • \(K\leq 500\)
  • \(1\leq C_i\leq N\)
  • \(1\leq V_i\leq 10^9\)

Solution

先考虑一种朴素的 DP，定义 \(dp[i][j][col]\) 表示前 \(i\) 个球，以及移走了 \(j\) 个，末尾的最后一个球的颜色为 \(col\) 的最大值

考虑两种情况：

  • 移走第 \(i\) 个球，那么转移方程为 \(dp[i][j][col']=\max\{dp[i-1][j-1][col']\}\)，其中 \(col'\) 为上一次球的颜色
  • 不移走第 \(i\) 个球，那么转移方程为 \(dp[i][j][col]=\max\{dp[i-1][j][col']+v[i]\},c[i]\ne col'\)

这样的时间复杂度为 \(O(N^2K)\) 会超时

观察发现 \(dp[i][j-1][col]\) 的很多值都是空的，所以考虑值维护其最大值以及和最大值颜色不同的次大值，这样子每次转移肯定能从最大值和次大值里面挑一个转移，后面的小值就不需要去考虑了

所以我们修改一下定义

\(dp[i][j][p]\) 记录前 \(i\) 个球，移走了 \(j\) 个，的最大值，次大值的 \(v[i]\) 总值和颜色

转移过程和朴素情况一样，只是当最大值和当前的 \(c[i]\) 相同时，改用次大值转移

这样的空间复杂度为 \(O(NK)\) 会超内存

发现 \(dp[i]\) 的状态只与 \(dp[i-1]\) 有关，所以考虑使用滚动数组把空间优化到了 \(O(K)\)

Code

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf = 1e15;

int main() {
    freopen ("E.in", "r", stdin);
    int k ,n; cin >> n >> k;
    vector<int> c(n + 1), v(n + 1);
    for (int i = 1; i <= n; i++) 
        cin >> c[i] >> v[i];
    
    const vector<pll> infv = {{-inf, -1}, {-inf, -2}};
    vector<vector<vector<pll>>> dp(2);  // 三维数组 dp[i][j][col] 表示前 i 个物品中选了 j 个，且最后一个物品的颜色是 col 的最大价值
    dp[0].resize(k + 1, infv); dp[1].resize(k + 1, infv);
    dp[0][0][0].first = dp[0][0][1].first = 0;

    for (int i = 1; i <= n; i++) {
        const int col = c[i], val = v[i];
        auto &cur = dp[i & 1], &pre = dp[(i - 1) & 1];
        for (int j = 0; j <= k; j++)
            cur[j] = infv;
        
        //选了当前物品
        for (int j = 0; j <= k; j++) {
            for (auto &x : pre[j]) {
                const ll preval = x.first, precol = x.second;
                if (precol == col) continue;
                cur[j].push_back({preval + val, col});
                break;
            }
        }
        //没选当前物品
        for (int j = 1; j <= k; j++) {
            for (auto &x : pre[j - 1]) {
                const ll preval = x.first, precol = x.second;
                cur[j].push_back({preval, precol});
            }
        }

        //去重
        for (int j = 0; j <= k; j++) {
            auto &a = cur[j];
            sort(a.begin(), a.end()); reverse(a.begin(), a.end());
            if (a[0].second == a[1].second) {
                ll secval = -inf, seccol = -2;
                for (auto x : a) {
                    if (x.second != a[0].second) {
                        secval = x.first;
                        seccol = x.second;
                        break;
                    }
                }
                a[1] = {secval, seccol};
            }
            a.resize(2);
        }
    }

    ll ans = dp[n & 1][k][0].first;
    cout << (ans < 0 ? -1 : ans) << endl;
    return 0;
}

F - Many Lamps

Question

有一个简单的图，图中有 \(N\) 个顶点，编号为 \(1\) 至 \(N\) ，有 \(M\) 条边，编号为 \(1\) 至 \(M\) 。边 \(i\) 连接顶点 \(u_i\) 和 \(v_i\) 。

每个顶点上都有一盏灯。初始时，所有的灯都是熄灭的。

请在 \(0\) 和 \(M\) 之间（包括首尾两次）执行以下操作，以确定是否可以恰好打开 \(K\) 盏灯。

  • 选择一条边。假设 \(u\) 和 \(v\) 是边的端点。切换 \(u\) 和 \(v\) 上的灯的状态。也就是说，如果灯亮着，则将其关闭，反之亦然。

如果可以恰好打开 \(K\) 盏灯，请打印实现该状态的操作序列。

Solution

简化问题，整个图是连通的

有一个性质：开的灯的数量肯定是偶数，证明如下

每次对一条边进行操作：

  • 初始两个灯都是亮的，那么总亮灯数 \(-2\)
  • 初始一亮一暗，那么总亮灯数不变
  • 初始两个灯都是灭的，那么总亮灯数 \(+2\)

奇偶性不变，初始是 \(0\) 为偶数，所以亮的灯的数量总是偶数

考虑连通图的总数为 \(N\) ，设 \(X\) 为小于等于 \(N\) 的最大偶数，有一种构造方法能让 \(X\) 盏灯都点亮

  • 先建立连通图的生成树 \(G\)
  • 取 \(G\) 的一个叶节点 \(u\)，考虑与叶节点连接的其父亲节点 \(v\)
  • 如果 \(u\) 是灭灯状态的话，那么对 \(u-v\) 进行一次转换操作，如果 \(u\) 是亮灯的话则不操作
  • 删除 \(u-v\) 这条边

为什么这样是有效的，因为如果 \(u\) 是灭灯

  • \(v\) 也是灭灯，那么同时点亮了两盏灯，能使亮灯数增加
  • \(v\) 是亮灯，虽然亮灯数没有变大，但是能把 \(u-v\) 的亮灯状态进行调换，由于叶节点只连接父节点一盏灯，但父节点能连接很多其他灯，把亮的灯放到叶子节点，让父节点更有机会和别的节点进行亮两盏灯的操作

如果 \(K<X\) ，亮灯的过程是从 \(0\sim X\) 的连续偶数，当亮灯数 \(=X\) 时，中止过程即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int main() {
    freopen ("F.in", "r", stdin);
    int n, m, k; cin >> n >> m >> k;
    vector<vector<pii> > g(n + 1);
    for (int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }

    int Y = 0;
    vector<int> ans, vis(n + 1, 0), cur(n + 1, 0);
    function<void(int)> dfs = [&](int u) {
        vis[u] = 1;
        for (auto [v, id] : g[u]) {
            if (vis[v]) continue;
            dfs (v);
            if (cur[v] == 0 && Y < k) { 
                Y -= cur[u] + cur[v];
                cur[u] ^= 1; cur[v] ^= 1;
                Y += cur[u] + cur[v];
                ans.push_back(id);
            }
        }
    };

    for (int i = 1; i <= n; i++) 
        if (!vis[i]) dfs(i);
    
    if (Y != k) cout << "No" << endl;
    else {
        cout << "Yes" << endl;
        cout << ans.size() << endl;
        for (auto x : ans) cout << x << " ";
        cout << endl;
    }
    return 0;
}

G - Sugoroku 5

Question

有一个棋盘游戏，其中有 \(N+1\) 个方格：方格 \(0\) 、方格 \(1\) 、方格 \(\dots\) 和方格 \(N\) 。
你有一个骰子，它能掷出一个介于 \(1\) 和 \(K\) 之间的整数，每种结果的概率相等。
您从 \(0\) 开始掷骰子。重复下面的操作，直到到达 \(N\) 格：

  • 掷骰子。假设 \(x\) 是当前方格， \(y\) 是掷出的数字，然后移动到方格 \(\min(N, x + y)\) 。

假设 \(P_i\) 是经过恰好 \(i\) 次操作后到达 \(N\) 个方格的概率。计算 \(P_1, P_2, \dots, P_N\) % \(998244353\)

\(1 \leq K \leq N \leq 2 \times 10^5\)

Solution

不会

标签：AtCoder,pq,345,int,题解,leq,vector,dp,10
From： https://www.cnblogs.com/martian148/p/18082547

相关文章

  • 分月饼【华为OD机试JAVA&Python&C++&JS题解】
    一.题目-分月饼中秋节，公司分月饼，m个员工，买了n个月饼，m<=n，每个员工至少分1个月饼，但可以分多个，单人分到最多月饼的个数是Max1，单人分到第二多月饼个数是Max2，Max1-Max2<=3，单人分到第n-1多月饼个数是Max(n-1)，单人分到第n多月饼个数是Max(n)，Max(n-1)–Max(n)<=3,问有多少......
  • ARC174C 题解
    blog。官解似乎很难想到，这里是容易想到的方法。显然是DP。介于轮数可能趋近于无穷，所以类似P4550做即可。设\(f_i,g_i\)表示已经抽了\(i\)个数，当前是Alice或Bob抽的，期望罚款。倒推处理，\(f_n=g_n=0\)。下文中\(p=\dfracin\)表示抽到已经有的概率。\[\large\begin......
  • [极客大挑战 2019]web部分题解（sql部分已完结，其他部分正在更新）
    SQL部分：[极客大挑战2019]BabySQL打开环境后有登录界面◕‿◕一眼注入，后先试试万能密码：username：admin'or'1'='1password：1 GG，出大问题，我就会这一招啊O.o？？完结撒花（不是꒰ঌ(⌯''⌯)໒꒱开玩笑的，着看着像是过滤了or后来尝试了一下oorr双写发现也不行，那咱继续注入哈：尝试......
  • 题解：CF1941G Rudolf and Subway
    原题链接简化题意一个无向连通图中将边分成了不同颜色（保证同种颜色联通），问从\(b\)到\(e\)最短需要经过几种颜色思路考虑因为同种颜色联通，可直接在读入的时候开两个vector分别存每个点属于的颜色及每种颜色有哪些点，又因为颜色数字可能跨度比较大，最好另开一个存颜色的种......
  • P9077 [PA2018] Poddrzewo 题解
    思考感觉题目有点迷惑的意思，要最小化操作\(1\)使用的次数，也就是要节约修改操作，让我们认为操作\(1\)是最有用的，其实只要稍微动动脑子想一想，删除操作才是最有用的，而交换操作根本没用。当将序列删除到只剩两个点时，就把两个点连上，度都为\(1\)。所以如果序列中\(1\)的数量超......
  • Atcoder ARC165D Xor Sum 5
    考虑到这个最终的答案是\(\oplus\)，所以只需要考虑每种排列出现的次数的奇偶，如果为奇再计算贡献即可。考虑什么情况下出现次数为奇。令每个数出现的个数为\(c_{1\simn}\)，方案数即为\(\dbinom{k}{c_1,c_2,\cdots,c_n}=\prod_{i=1}^n\dbinom{k-\sum\limits_{j=1}^{......
  • 亲子游戏【华为OD机试JAVA&Python&C++&JS题解】
    题目描述宝宝和妈妈参加亲子游戏，在一个二维矩阵（NN）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下......
  • SGU171 Sarov zones 题解
    题意：有\(K\)个城市，第\(i\)城市至多有\(N[i]\)个人，每个城市有一个属性\(Q[i]\)。对于\(N=\sumN[i]\)个人，每个人有一个属性\(P[i]\)和价值\(W[i]\)，把第\(i\)个人放进第\(j\)个城市中，当且仅当\(P[i]>Q[j]\)时，可以获得\(W[i]\)的价值，否则不获得价值。求出满......
  • [极客大挑战 2019]web部分题解（sql部分已完结，其他部分正在更新）
    SQL部分：[极客大挑战2019]BabySQL打开环境后有登录界面◕‿◕一眼注入，后先试试万能密码：username：admin'or'1'='1password：1 GG，出大问题，我就会这一招啊O.o？？完结撒花（不是꒰ঌ(⌯''⌯)໒꒱开玩笑的，着看着像是过滤了or后来尝试了一下oorr双写发现也不行，那咱继续注入哈：尝试......
  • kodbox读取alist文件失败，问题解决过程
    让我先把相关的报错信息通过文字贴到下方，方便被检索出来出错了!(warning!)curlerrorcode=403;系统错误(explorer.editor.fileGet)explorer/editor.class.php[64]IO::fileSubstr(0,1,2)bin/data.bin[2][Linux6.2.0-35-generic/8.2.11/mysqli/1.49.10]在使用kodbbox......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99