首页 > 其他分享 >AtCoder Beginner Contest 346 题解

AtCoder Beginner Contest 346 题解

时间：2024-03-24 21:35:02浏览次数：29  
标签：pre AtCoder int 题解 ll cin ++ 346 vector

A - Adjacent Product

Question

给你 \(N\) 个整数 \(A_1, A_2, \dots, A_N\) 。同时，定义 \(B_i = A_i \times A_{i+1}\ (1 \leq i \leq N-1)\)

按此顺序打印 \(B_1, B_2, \dots, B_{N-1}\)

Solution

按照题意模拟

Code

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
        cout << a[i] * a[i + 1] << " ";
    return 0;
}

B - Piano

Question

有一个无限长的钢琴键盘。在这个键盘中，是否存在一个由 \(W\) 个白键和 \(B\) 个黑键组成的连续部分？

假设 \(S\) 是由无限重复的字符串 wbwbwwbwbwbw 构成的字符串。

在 \(S\) 中，是否存在一个由 \(W\) 次出现的 w 和 \(B\) 次出现的 b 组成的子串？

Solution

暴力把 \(S\) 复制多次，然后 \(n^2\) 找子串验证

应该还有更优的解法，只是串长实在太短，怎么写都行

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int W, B; cin >> W >> B;
    string s, p = "wbwbwwbwbwbw";
    while (s.size() < 2000) s += p;
    int n = s.size(); s = " " + s; 
    vector<int> sumb(n + 1), sumw(n + 1);
    for (int i = 1; i <= n; i++) {
        sumb[i] = sumb[i - 1] + (s[i] == 'b');
        sumw[i] = sumw[i - 1] + (s[i] == 'w');
    }
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++) {
            int nw = sumw[j] - sumw[i - 1], nb = sumb[j] - sumb[i - 1];
            if (W == nw && B == nb) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    cout << "No" << endl;
    return 0;
}

C - Σ

Question

给你一个长度为 \(N\) 的正整数序列 \(A\) 和一个正整数 \(K\)

求在 \(1\) 与 \(K\) 之间，未出现在序列 \(A\) 中的整数之和

Solution

先算 \(1\sim K\) 中所有数的和，然后把在 \(A\) 中的减去

注意 \(A\) 中的 \(A_i\) 可能不在 \(1\sim K\) 这个范围内

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    int ans = k * (k + 1) / 2;
    for (int &x : a) {
        if (x <= k)
            ans -= x;
    }
    cout << ans << endl;
    return 0;
}

D - Gomamayo Sequence

Question

给你一个长度为 \(N\) 的字符串 \(S\) ，它由 0 和 1 组成

长度为 \(N\) 的字符串 \(T\) 由 0 和 1 组成，当且仅当它满足以下条件时，它是一个好字符串：

  • 恰好有一个整数 \(i\) 使得 \(1 \leq i \leq N - 1\) 和 \(T\) 的第 \(i\) 个字母 和第 \((i + 1)\) 个字符相同

对于每个 \(i = 1,2,\ldots, N\) ，您可以选择是否执行一次下面的操作：

  • 如果 \(S\) 的 \(i\) 个字符是 0，则将其替换为 1，反之亦然。如果执行此操作，代价是 \(Ci\)

求使 \(S\) 成为一个好字符串所需的最小总成本

Solution

考虑到有且仅有一个 \(i\) ，满足 \(T_i = T_{i+1}\)，不妨假设 \(T_i=T_{i+1}=1\)，那么可知 \(T_{i-1}=0,T_{i+2}=0\)

\(i\) 前面和 \(i+1\) 后面都是 0101 交替的，我们就可以记录一个交错的前缀和

定义 \(pre[i][0]\) 表示第 \(i\) 个字母，前面都是 0101 交替的，且第 \(i\) 个字母为 0 花费的最小代价，\(pre[i][1]\) 表示第 \(i\) 个字母，前面都是 0101 交替的，且第 \(i\) 个字母为 1 花费的最小代价

同理，\(suf[i][0]\) 表示第 \(i\) 个字母，后面都是 0101 交替的，且第 \(i\) 个字母为 0 花费的最小代价

如何计算 \(pre\) ？交错着刷前缀和就好了

for (int i = 1; i <= n; i++) {
    pre[i][0] = pre[i - 1][1] + c[i] * (s[i] != '0');
    pre[i][1] = pre[i - 1][0] + c[i] * (s[i] != '1');
}

最后，关于 \(T_i=T_{i+1}\) 只有 \(0\)，\(1\) 两种情况，分别枚举一次即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    string s; cin >> s; s = " " + s;
    vector<ll> c(n + 1, 0);
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    
    vector<vector<ll> > pre(n + 2 , vector<ll>(2, 0)); auto lst = pre;
    for (int i = 1; i <= n; i++) {
        pre[i][0] = pre[i - 1][1] + c[i] * (s[i] != '0');
        pre[i][1] = pre[i - 1][0] + c[i] * (s[i] != '1');
    }
    for (int i = n; i > 0; i--) {
        lst[i][0] = lst[i + 1][1] + c[i] * (s[i] != '0');
        lst[i][1] = lst[i + 1][0] + c[i] * (s[i] != '1');
    }

    ll ans = INF;

    //00
    for (int i = 1; i < n; i++) {
        ll now = c[i] * (s[i] != '0') + c[i + 1] * (s[i + 1] != '0');
        now += pre[i - 1][1] + lst[i + 2][1];
        ans = min(ans, now);
    }
    //11
    for (int i = 1; i < n; i++) {
        ll now = c[i] * (s[i] != '1') + c[i + 1] * (s[i + 1] != '1');
        now += pre[i - 1][0] + lst[i + 2][0];
        ans = min(ans, now);
    }
    cout << ans << '\n';
    return 0;
}

E - Paint

Question

有一个行数为 \(H\) 列数为 \(W\) 的网格。初始时，所有单元格都涂有颜色 \(0\)

您将按照 \(i = 1, 2, \ldots, M\) 的顺序执行以下操作。

  • 如果是 \(T_i = 1\) ，则使用颜色 \(X_i\) 重新绘制 \(A_i\) 行中的所有单元格。

  • 如果是 \(T_i = 2\) ，则使用颜色 \(X_i\) 重新绘制 \(A_i\) 列中的所有单元格

完成所有操作后，针对网格中存在的每种颜色 \(i\) ，找出被涂上颜色 \(i\) 的单元格数量

Solution

显然，最后一次刷在墙上的颜色肯定存在，第二次如果和第一次方向不同，那么中间会有一个格子是第一次刷的颜色

按照这个想法，我们用 map 记录有多少行被刷了颜色，以及有多少列刷了颜色

倒叙处理，这一行/列 在这一次刷中保留了多少颜色，取决与有多少 列/行 还没有刷过

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
signed main() {
    freopen ("E.in","r",stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    int H, W, N; cin >> H >> W >> N;
    vector<int> A(N + H), X(N + H), T(N + H); 
    N = N + H;
    for (int i = 0; i < H; i++) {
        T[i] = 1; A[i] = i + 1; X[i] = 0;
    }
    for (int i = H; i < N; i++)
        cin >> T[i] >> A[i] >> X[i];
    map<int,pii> col, row;
    for (int i = N - 1; i>= 0; i--) {
        if (T[i] == 1) {
            if (row.count(A[i])) continue;
            row[A[i]] = {W - col.size(), X[i]};
        }
        else {
            if (col.count(A[i])) continue;
            col[A[i]] = {H - row.size(), X[i]};
        }
    }
    map<int,int> mp;
    for (auto &r : row) {
        int num = r.second.first, c = r.second.second;
        if (!mp.count(c))
            mp[c] = 0;
        mp[c] += num; 
    }
    for (auto &r : col) {
        int num = r.second.first, c = r.second.second;
        if (!mp.count(c))
            mp[c] = 0;
        mp[c] += num; 
    }

    int ans = 0;
    for (auto &x : mp) 
        ans += x.second != 0;
    cout << ans << '\n';
    for (auto &x : mp) {
        if (x.second == 0) continue;
        cout << x.first << " " << x.second << '\n';
    }
    return 0;
}

F - SSttrriinngg in StringString

Question

对于长度为 \(n\) 的字符串 \(X\)

  • 让 \(f(X,k)\) 表示重复 \(k\) 次字符串 \(X\) 得到的字符串
  • \(g(X,k)\) 表示依次重复 \(k\) 次第一个字符、第二个字符、 \(\dots\) 、 \(X\) 的 \(n\) 个字符得到的字符串

给你一个正整数 \(N\) 和字符串 \(S\) 和 \(T\) 。求最大的非负整数 \(k\) ，使得 \(g(T,k)\) 是 \(f(S,N)\) 的子序列

注意，根据定义， \(g(T,0)\) 总是 \(f(S,N)\) 的子序列

Solution

答案满足单调性，也就是说，如果 \(g(T,k)\) 是 \(f(S,N)\) 的子序列的话，对于所有的 \(k'\le k\) ，\(g(T,k')\) 也是 \(f(S,N)\) 的子序列

所以我们二分最后的答案 \(k\)，考虑如何 check

提前预处理出 \(S\) 字符出现的次数 以及 每个字符的第 \(i\) 次出现的位置

记录此时枚举 \(g(S,N)\) 的第 \(iter\) 个字母

对于 \(T\) 上的每个字母，都需要重复 \(k\) 次，那么看需要多少整块的 \(S\) 以及最后一块 \(S\) 上的几个字母

按照题意模拟即可

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;

int main() {
    ll n;
    string S, T;
    cin >> n >> S >> T;
    int s = S.size(), t = T.size();
    vector<vector<int> > pos(26);
    for (int i = 0; i < s * 2; i++) 
        pos[S[i % s] - 'a'].push_back(i);
    vector<vector<int> >  pre(s + 1, vector<int>(26));
    for (int i = 0; i < s; i++) {
        pre[i + 1] = pre[i];
        pre[i + 1][S[i] - 'a']++;
    }
    vector<int> cnt(26, 0);
    for (int i = 0; i < s; i++)
        cnt[S[i] - 'a']++;
    ll le = 0, ri = INF;
    auto check = [&] (ll x) -> bool {
        ll iter = 0; // 表示s的长度
        for (int i = 0; i < t; i++) {
            int c = T[i] - 'a';
            if (cnt[c] == 0) return false;
            ll r = (x - 1) % cnt[c] + 1;
            ll q = (x - r) / cnt[c];
            if (q > INF / s) return false;
            iter += q * s;
            int nx = pos[c][pre[iter % s][c] + r - 1]; // 从iter % s开始的第r个c 的位置
            iter += nx - iter % s + 1;
            if (iter > n * s) return false;
        }
        return true;
    };

    while (le + 1 < ri) {
        ll mid = (le + ri) >> 1;
        if (check(mid)) le = mid;
        else ri = mid;
    }
    cout << le << endl;
    return 0;
}

G - Alone

Question

给你一个整数序列 \(A\) 。

求满足以下条件的整数对 \((L, R)\) 的个数：

  • \(1 \leq L \leq R \leq N\)
  • 有一个数字在 \(A_L, A_{L + 1}, \ldots, A_R\) 中恰好出现一次。更确切地说，有一个整数 \(x\) 恰好有一个整数 \(i\) 满足 \(A_i = x\) 和 \(L \leq i \leq R\)

Solution

对于一个 \(i\)，提前预处理出 \(pre[i]\) 和 \(nxt[i]\)，分别表示与 \(a[i]\) 相同的前一个和后一个出现的位置

显然，一个区间的左端点可以在 \((pre[i],i]\) ，一个区间的右端点可以是 \([i,nxt[i])\)

例如 2 2 1 2 1 ，当 \(i = 3,a[i]=1\)

那么此时的 \(pre[i]=0,nxt[i]=5\)

\((1,3),(1,4),(2,3),(2,4),(3,3),(3,4)\) 都是合法的区间

对于一个 \(i\) 可以生成这么多区间，显然最后的答案是对每个 \(i\) 找区间，然后去重

关键是如何去重？ 我们发现一个 \(i\) 生成的区间都是连续的，也就是说，如果把二元组看成二维平面上的一个坐标，那么一个 \(i\) 生成的区间对应的是二维平面上的一个矩形

而矩形的左下角是 \((pre[i]+1,i)\) 右上角是 \((i,nxt[i]-1)\)

显然，这个问题就转化为二维平面上 \(n\) 个矩形的交集面积

利用扫描线算法就可以解决

Code

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

struct Segment_Tree {
    int n;
    vector<int> sum, tag;
    Segment_Tree (int n) {
        this->n = n;
        tag.assign(n << 4, 0);
        sum.assign(n << 4, 0);
    }


    void update (int x, int l, int r, int ql, int qr, int val) {
        if (ql <= l && r <= qr) {
            tag[x] += val;
            if (tag[x]) sum[x] = r - l + 1;
            else sum[x] = sum[x << 1] + sum[x << 1 | 1];
            return ;
        }
        int mid = (l + r) >> 1;
        if (ql <= mid) update(x << 1, l, mid, ql, qr, val);
        if (qr > mid) update(x << 1 | 1, mid + 1, r, ql, qr, val);
        if (!tag[x]) sum[x] = sum[x << 1] + sum[x << 1 | 1];
    }

};

struct Line {
    int l, r, x, op;
    Line (int l, int r, int x, int op) : l(l), r(r), x(x), op(op) {}
    bool operator < (const Line &rhs) {
        if (x == rhs.x) return op < rhs.op;
        return x < rhs.x;
    }
};

int main() {
    freopen ("G.in", "r", stdin);
    int n; cin >> n;
    vector<int> a(n + 1);

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    vector<int> pre(n + 1, 0), nxt(n + 1, n + 1), pos(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        pre[i] = pos[a[i]];
        pos[a[i]] = i;
    }
    pos.assign(n + 1, n + 1);
    for (int i = n; i; i--) {
        nxt[i] = pos[a[i]];
        pos[a[i]] = i;
    }
    
    vector<Line> lines;
    for (int i = 1; i <= n; i++) {
        lines.emplace_back(i, nxt[i] - 1, pre[i], 1);
        lines.emplace_back(i, nxt[i] - 1, i, -1);
    }
    
    Segment_Tree T(n);
    ll ans = 0;
    sort(lines.begin(), lines.end());
    for (int i = 0; i < lines.size() - 1; i++) {
        T.update(1, 1, n, lines[i].l, lines[i].r, lines[i].op);
        ans += 1ll * T.sum[1] * (lines[i + 1].x - lines[i].x);
    }
    cout << ans << endl;
    return 0;
}

标签：pre,AtCoder,int,题解,ll,cin,++,346,vector
From： https://www.cnblogs.com/martian148/p/18093094

相关文章

  • AT_abc344_D-String Bags 题解
    明显是DP。然后就开始分析：状态：\(dp_{ij}=\)有\(i\)个袋子且匹配\(T\)的前缀的长度为\(j\)时所需的最少钱数。匹配\(T\)的前缀的长度为\(j\)就是前\(j\)个字符与\(T\)的前\(j\)个字符相同。相对简单。然后看转移。为了方便，咱不妨令\(|S|\)为字符串\(S......
  • P10111 [GESP202312 七级] 纸牌游戏 题解
    看标签知道要用DP。于是开始分析。状态：$dp(i,j,k)=$前\(i\)轮中，第\(i\)轮出\(j\)，一共换了\(k\)次牌的最大钱数。很好理解。转移也不难，不就是不换和换两种吗！所以，转移就是：\[dp(i,j,k)=\max\begin{cases}dp(i-1,j,k)+\operatorname{pk}(j,c_i)\times......
  • [暴力题解系列]2023年蓝桥杯-整数删除（30分）
    这题暴力最多30分，但是30分也是分，做暴力的人不能贪心，拿到分就是赚了。​ 这题核心烦人点在于他数据分层断崖，就只有前3个点能做到稳过。用的思路就是链表，但不是用指针存的，而是用数组下标为标记存的，只是我觉得因为这样好写一些。链表方便修改左右连接位置，所以越到后面就越能省下查询......
  • 0318-0324题解
    成信大天梯赛L1-6二进制因为二进制是逢二进一，所以我们只要用cnt记录一下每一位上的数并给它加起来，然后cnt%2便是其和这一位上的数，注意要从右往左开始点击查看代码#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>pii;voidsolve(){stringa,b......
  • 广州大学第十八届ACM大学生程序设计竞赛（同步赛）——题解
    这套题我答的很失败。没有按照题目的难度去答题，前期浪费了不少时间。题目：A-字符画题解：思维、模拟。这道题我的通过率为62.5，没有过的原因是因为对细节的处理和把控不到位，对一些点忽视，我也记录了搜索的过程，但没有把搜索过的点消掉，而且没有找到最好的顺序去解答这道题，我是按照横的......
  • 字母迷宫题解
    思路：看到这题一眼跑广搜，但是转眼天堂之门，欸为什么要加2？好像没法广搜（不满足广搜特性），咋办？凉拌。该怎么让它满足广搜特性（先搜到的是最优的）。欸，我们是不是可以将队列换成优先队列让先搜到的最优。好像是的欸，优先队列启动！代码：#include<bits/stdc++.h>usingnamespacestd;inta......
  • cfEduRound163div2--D题解
    D-TandemRepeats?题意:做法：因为字符串长度较少，可以考虑枚举。or--动态规划voidsolve(){//D枚举//枚举！！！！！！！！！！stringstr;cin>>str;intn=str.size(),ans=0;for(inti=1;i<=n/2;i++){//枚举一半!!!intcnt=0;for(intj=0;......
  • 题解 CF1948G【MST with Matching】
    非常精彩的转化！显然，树是二分图。由König定理，我们知道：二分图最小点覆盖等于最大匹配。因此枚举点覆盖\(S\)，则一条边\((u,v)\)可以被选择，当且仅当\(u\inS\lorv\inS\)，在所有可以选择的边上跑最小生成树即可。我采用的是Kruskal算法，时间复杂度为\(O(2^nn^2\logn)\)，可......
  • 20240324每日一题题解
    20240324每日一题题解Problem给两个按照非递减顺序排列的整数数组num1和num2，另外有两个整数m和n，分别表示num1和num2中的元素数目。请合并num2到num1中，使得合并后的数组还是按照非递减顺序排列。注意，需要将合并之后的数组还是存储在数组num1中。示例1:输入:nums1=[1,2,3,0,......
  • Programming Abstractions in C阅读笔记：p338-p346
    《ProgrammingAbstractionsinC》学习第80天，p338-p346，总计9页。一、技术总结栈的实现包括入栈、出栈、判断栈是否为满，判断栈是否为空等。作者结合RPN计算器来实现，稍显无聊。/**File:rpncalc.c*---------------*Thisprogramsimulatesanelectroniccalculatorth......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99