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

AtCoder Beginner Contest 278题解

时间：2022-11-19 22:36:15浏览次数：49  
标签：Case AtCoder 层次 val int 题解 cin 278 define

A - Shift

题意

给一个长度为\(n\)的数组，有\(k\)次操作，每次操作会将数组最前面的元素删掉，再在数组最后面加上一个0元素，问\(k\)次操作后的数组中的数字。

思路

看\(n\)与\(k\)的大小关系

  • 如果\(k \geq n\)，则全为0
  • 否则，先输出最后面\(n - k + 1\)个元素，再输出\(k\)个0。

Code

#include <bits/stdc++.h>
using namespace std;
#define _u_u_ ios::sync_with_stdio(false), cin.tie(nullptr)
#define cf int _o_o_;cin>>_o_o_;for (int Case = 1; Case <= _o_o_;Case++)
#define SZ(x) (int)(x.size())
inline void _A_A_();
signed main() {_A_A_();return 0;}

using ll = long long;
// #define int long long
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 210, M = 5010;
const int inf = 0x3f3f3f3f;

inline void _A_A_() {
    #ifdef LOCAL
    freopen("in.in", "r", stdin);
    #endif
    _u_u_;
    int n, m;
    cin >> n >>m;
    vector<int>v (n);
    for (int i = 0;i < n;i++) cin >> v[i];
    if (m >= n) {
        for (int i = 0;i < n;i++) {
            cout<< 0 << " ";
        }
    }
    else {
        for (int i = m ;i < n;i++) {
            cout << v[i] << " ";
        }
        for (int i = 0;i < m;i++) {
            cout << 0 << " ";
        }
    }
    cout << "\n";

}

B - Misjudge the Time

题意

定义 a confusing time 为：

将24小时制下的ab:cd变成ac:bd，如果ac:bd也是合法的时间，则说明ab:cd是a confusing time。

给一个24小时制的时间ab:cd，如果ab:cd是a confusing time，输出ab:cd，否则输出下一个a confusing time。

思路

先从当前时间开始到23:59判断是否有 a confusing time ，再从\(00:00\)到当前时间判断是否存在 a confusing time 。

Code

#include <bits/stdc++.h>
using namespace std;
#define _u_u_ ios::sync_with_stdio(false), cin.tie(nullptr)
#define cf int _o_o_;cin>>_o_o_;for (int Case = 1; Case <= _o_o_;Case++)
#define SZ(x) (int)(x.size())
inline void _A_A_();
signed main() {_A_A_();return 0;}

using ll = long long;
// #define int long long
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 210, M = 5010;
const int inf = 0x3f3f3f3f;

bool check(int n, int m) {
    if (n < 0 || n >= 24) return 0;
    if (m < 0 || m >= 60) return 0;
    return 1;
}

inline void _A_A_() {
    #ifdef LOCAL
    freopen("in.in", "r", stdin);
    #endif
    _u_u_;
    int n, m;
    cin >> n >> m;
                    // int newi = i / 10 + j /10;
                    // int newj = (i % 10) * 10 + j % 10;
                    // if (check(newi, newj)) {
                    //     cout << i << " " << j << "\n";
                    //     return;
                    // }
    for (int i = n;i <= 23;i++) {
        if (i == n) {
            for (int j= m;j <= 59;j++) {
                int newi = (i / 10) * 10 + j /10;
                int newj = (i % 10) * 10 + j % 10;
                if (check(newi, newj)) {
                    cout << i << " " << j << "\n";
                    return;
                }
            }
        }
        else {
            for (int j= 0;j <= 59;j++) {
                int newi = i / 10 + j /10;
                int newj = (i % 10) * 10 + j % 10;
                if (check(newi, newj)) {
                    cout << i << " " << j << "\n";
                    return;
                }
            }

        }
    }
    for (int i = 0;i <= n;i++) {
        if (i == n) {
            for (int j= 0;j < m;j++) {
                int newi = i / 10 + j /10;
                int newj = (i % 10) * 10 + j % 10;
                if (check(newi, newj)) {
                    cout << i << " " << j << "\n";
                    return;
                }
            }
        }
        else {
            for (int j= 0;j <= 59;j++) {
                int newi = i / 10 + j /10;
                int newj = (i % 10) * 10 + j % 10;
                if (check(newi, newj)) {
                    cout << i << " " << j << "\n";
                    return;
                }
            }
        }
    }
}

C - FF

题意

有\(n\)个人，三种操作。

  • 操作一：A follow B
  • 操作二：A unfollow B
  • 操作三：问A与B是否相互follow

思路

使用map<pair<int,int>,bool>判断A是否follow B，依次操作即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define _u_u_ ios::sync_with_stdio(false), cin.tie(nullptr)
#define cf int _o_o_;cin>>_o_o_;for (int Case = 1; Case <= _o_o_;Case++)
#define SZ(x) (int)(x.size())
inline void _A_A_();
signed main() {_A_A_();return 0;}

using ll = long long;
// #define int long long
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 210, M = 5010;
const int inf = 0x3f3f3f3f;

map<pair<int,int>,bool> mp;

inline void _A_A_() {
    #ifdef LOCAL
    freopen("in.in", "r", stdin);
    #endif
    _u_u_;
    int n, q;
    cin >> n >> q;
    while (q -- ) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1) {
            mp[{b,c}] = 1;
        }
        else if (a == 2) {
            mp[{b,c}] = 0;
        }
        else {
            if (mp[{b,c}] && mp[{c,b}]) {
                cout << "Yes\n";
            }
            else {
                cout << "No\n";
            }
        }
    }
}

D - All Assign Point Add

题意

有长度为\(n\)的数组a，三种操作

  • 操作一：1 val，将数组a中所有值设置为val
  • 操作二：2 id val， a[id] += val
  • 操作三：3 id， 输出a[id]

思路

设置层次的概念，初始时层次为0，每次操作一后层次加一。

并且在a中每一个元素都带着一个层次，初始为0。

当操作二或三时，判断a[id]的层次是否和现在的层次相符，不相等时将a[id]的层次改为现在的层次，并将a[id]的值改为当前层次的初始值val，再进行相应操作。

Code

#include <bits/stdc++.h>
using namespace std;
#define _u_u_ ios::sync_with_stdio(false), cin.tie(nullptr)
#define cf int _o_o_;cin>>_o_o_;for (int Case = 1; Case <= _o_o_;Case++)
#define SZ(x) (int)(x.size())
inline void _A_A_();
signed main() {_A_A_();return 0;}

using ll = long long;
#define int long long
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 210, M = 5010;
const int inf = 0x3f3f3f3f;

inline void _A_A_() {
    #ifdef LOCAL
    freopen("in.in", "r", stdin);
    #endif
    _u_u_;
    int n;
    cin >> n;
    vector<pair<int,int>>v(n, {0,0});
    pair<int,int> now;
    now.first = 0;  // 当前的层次初始化为0
    now.second = -1;    // 当前的val初始化为-1
    for (int i= 0;i < n;i++) {
        cin >> v[i].first;
    }
    int q;
    cin >> q;
    int op;
    while (q --) {
        cin >> op;
        if (op == 1) {  // 操作一
            now.first++;    // 层次加一
            cin >> now.second;  // 输入当前层次的值val
        }
        else if (op == 2) {
            int t, val;
            cin >> t >> val;
            t--;
            if (v[t].second == now.first) { // 层次相符
                v[t].first += val;
            }
            else {  // 层次不相符
                v[t].second = now.first;    // 改为现在的层次
                v[t].first = now.second + val;
            }
        }
        else {
            int t;
            cin >> t;
            t--;
            if (v[t].second == now.first)   // 层次相符
                cout <<  v[t].first << "\n";
            else { // 层次不相符 
                v[t].second = now.first;    // 该为现在的层次
                v[t].first = now.second;
                cout <<  v[t].first << "\n";
            }
        }
    }
}

E - Grid Filling

题意

给定\(n * m\)个点，每个点上都有一个大于等于1，小于等于\(N\)的值。

依次将大小为\(dx * dy\)的区域覆盖，覆盖后对应的答案就为没被覆盖的所有的点上的不同的值的个数。

思路

由于\(N \leq 300\)，可以设置\(N\)个二维前缀和数组，\(O(1)\)得到\(dx * dy\)区域内\(N\)个值的个数，再分别与所有的个数进行比较，对于\(1 \dots N\)中的每一个\(x\)，如果不是所有的\(x\)都在被覆盖的范围内，则答案加一。

Code

#include <bits/stdc++.h>
using namespace std;
#define _u_u_ ios::sync_with_stdio(false), cin.tie(nullptr)
#define cf int _o_o_;cin>>_o_o_;for (int Case = 1; Case <= _o_o_;Case++)
#define SZ(x) (int)(x.size())
inline void _A_A_();
signed main() {_A_A_();return 0;}

using ll = long long;
// #define int long long
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
// const int N = 210, M = 5010;
const int inf = 0x3f3f3f3f;

unordered_map<int,int> mp; // 有点多余，应该设置一个数组。

inline void _A_A_() {
    #ifdef LOCAL
    freopen("in.in", "r", stdin);
    #endif
    _u_u_;
    int n, m, N, dx,dy;
    cin >> n >> m >> N >> dx >> dy;
    vector<vector<int>> v(n + 1, vector<int> (m + 1, 0));
    vector<vector<vector<int>>> sum(N + 1, vector<vector<int>> (n + 1, vector<int> (m + 1, 0)));    // N个二维前缀和
    for (int i= 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> v[i][j];
            mp[v[i][j]]++;
            sum[v[i][j]][i][j]++;
        }
    }
    for (int val = 1;val <=N;val++) {
        for (int i = 1;i <= n;++i) {
            for (int j = 1;j <= m;j++) {
                sum[val][i][j] += sum[val][i - 1][j] + sum[val][i][j - 1] - sum[val][i - 1][j - 1]; // 求二维前缀和
            }
        }
    }
    for (int i = 1;i + dx - 1 <= n;i++)  {
        for (int j = 1;j + dy - 1 <= m;j++) {   // 对每一个dx * dy的区域
            int ans = 0;
            for (int val = 1;val <= N;val++) {
                int t_sum = sum[val][i + dx -1][j + dy - 1] + sum[val][i - 1][j - 1] - sum[val][i - 1][j + dy -1] - sum[val][i + dx -1][j - 1]; // 求出在被覆盖的区域中val的个数
                if (mp[val] - t_sum ) ans++;    // 如果不是所有的val都被覆盖，答案加一
            }
            cout << ans << " ";
        }
        cout << "\n";
    }
}

标签：Case,AtCoder,层次,val,int,题解,cin,278,define
From： https://www.cnblogs.com/FanWQ/p/16907368.html

相关文章

  • AtCoder Beginner Contest 277 A~C
    本文同步发表于洛谷A.https://www.luogu.com.cn/blog/Alex-ZJY/solution-at-abc277-aB.https://www.luogu.com.cn/blog/Alex-ZJY/solution-at-abc277-bC.https://www......
  • Codeforces 704 B Antman 题解 (dp，贪心，结论)
    题目链接这题两种不同做法，普通的\(O(n^2)\)和奇怪的\(O(nlogn)\)。如果用\(O(nlogn)\)的话可以加强到1e6。做法1时间复杂度\(O(n^2)\)先把最终的排列随便画一个出来观......
  • C. Sum of Substrings题解
    C.SumofSubstrings题目大概意思，给你一个01串，求和最小，其中和是该串所有相邻字符所组成的十进制数的和。如：0110，sum=01+11+10=22。通过观察我们可以发现，除了第......
  • cf796部分题解
    C.ManipulatingHistory题意：给出一些字符串，有原始串（只含一个字符的串）、被替换的串、替换串、最终串（最后一行），求原始串。2aabbcdacdInitiallysis"a".Inthe......
  • B - Bracket Sequence题解
    B-BracketSequence思路：用一个flag来标记括号的数目，如果括号数目是个偶数的话，就代表当前要执行'+'操作，反之就是'*'操作。对于最外层的数，是没有计算的。所以最后要单独......
  • Auxiliary Set题解
    FAuxiliarySet树上LCA+DFS注意一下输出格式！#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;intt,n,q,ans;intfa[N];//存储点i的......
  • 广东工业大学第十六届程序设计竞赛题解（部分）
    E爬塔方法一：二分做法预处理每个点所能到达的最远距离，存到vector里边，然后二分处理结果#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;intn,......
  • F - Subarrays题解
    F-Subarrays题意：给你一个序列，问这个序列里有多少个子串的和能被k整除。思路：求前缀和，然后每个位置对k取模，模数相等的位置之间，是一个满足条件的字串。因为求的是前缀和，......
  • G water testing题解
    Gwatertesting题意：给你一个多边形（可能是凸多边形，也可能是凹多边形），问该多边形内有多少个整数点（不包含边界）。思路：皮克定理+叉乘计算三角形面积：皮克定理是指一个计算点......
  • Frogger题解
    Frogger法一：floyd#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<cmath>#include<iomanip>#defineintlonglongintusingn......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99