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

AtCoder Beginner Contest 347 A-F 题解

时间：2024-03-31 16:33:55浏览次数：16  
标签：AtCoder ch int 题解 ll st 347 query now

A - Divisible

Quesiton

给你正整数 \(N\) 和 \(K\) ，以及长度为 \(N\) 的序列 \(A\)。

提取 \(A\) 中所有是 \(K\) 倍数的元素，除以 \(K\) ，并打印商。

Solution

判断 \(A_i \% K\) 的值是否为 \(0\)，如果非 \(0\) 则表示可以整除

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> ans;
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n;i++) {
        int x; cin >> x;
        if (x % k == 0) {
            ans.push_back(x / k);
        }
    }
    for (auto x : ans)
        cout << x << " ";
    return 0;
}

B - Substring

Question

给你一个由小写英文字母组成的字符串 \(S\) 。 \(S\) 有多少个不同的非空子串？

子串是连续的子序列。例如，xxx是yxxxy的子串，但不是xxyxx的子串。

Solution

使用 substr() 函数取字串

然后用 set<string> 去重即可

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s; cin >> s;
    set<string> st;
    for (int L = 1; L <= s.size(); L++) 
        for (int i = 0; i + L - 1 < s.size(); i++) {
            string t = s.substr(i, L);
            st.insert(t);
        }
    cout << st.size() << endl;
    return 0;
}

C - Ideal Holidays

Soluiton

考虑把一个 \(D_i\) 都压缩到一个周期中

\(D_i = (D_i-1)\%(A+B)\)

即 \(0\) 表示一周的第一天，\(A+B-1\) 表示一周的最后一天

我们需要找一个 \(i\) 使得 \([i,i+A)\) 天包括所有的 \(D_i\)

如果 \(i+A>A+B\) ，即 \(i>B\)，那么就可以转化成：

\([0,i-B)\cup[i,n)\)

具体实现是，转化为判断

排序后，是否存在一个 \(D_i\) 和 \(D_{i+1}\) 的中间能插入一个 \(B\)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n; cin >> n;
    ll A, B; cin >> A >> B;
    vector<ll> D(n);
    for (int i = 0; i < n; i++) {
        cin >> D[i];
        D[i] = (D[i] - 1) % (A + B);
    }
    sort(D.begin(), D.end());
    for (int i = 1; i < n; i++)
        if (D[i] - D[i - 1] >= B) {
            cout << "Yes" << '\n';
            return 0;
        }
    if (D.back() - D.front() < A) {
        cout <<  "Yes" << '\n';
        return 0;
    }
    cout << "No" << endl;
    return 0;
}

D - Popcount and XOR

Solution

由于异或的性质，每一位分开来看，如果为 \(1\)，说明两者肯定有一个为 \(0\)，一个为 \(1\)，如果为 \(0\)，有可能都为 \(0\)，或都为 \(1\)

我们设 \(C\) 的二进制位数 \(1\) 的个数为 \(cnt_c\)

所以 \(a+b<cnt_c\) 或者 \(a+b-cnt_c\) 是一个奇数的情况肯定是不合法的

然后模拟放 \(1\) 的过程

如果 \(C\) 的某一位为 \(1\)，选择 \(a\) 或 \(b\) 其中的一个放 \(1\)

在 \(C\) \(1\) 的位置都放完后，如果 \(a,b\) 还有剩余，就在 \(C\) 为 \(0\) 的位置同时在 \(a,b\) 的相同位置放上 \(1\)

使用 bitset 可以很好的模拟

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int a, b;
    ll C; 
    cin >> a >> b >> C;
    bitset<60> bit_C(C), bit_A, bit_B;
    if (a + b < bit_C.count() || (a + b - bit_C.count()) % 2 == 1) {cout << "-1" << '\n'; return 0;}
    int cnt = (a + b - bit_C.count()) / 2;
    a -= cnt; b -= cnt;
    for (int i = 0; i < 60; i++) {
        if (bit_C[i]) {
            if (a) {bit_A[i] = 1; a--;}
            else if (b) {bit_B[i] = 1; b--;}
        }
    }
    if (a != 0 || b != 0) {cout << "-1" << '\n'; return 0;}
    for (int i = 0; i < 60; i++) 
        if (bit_C[i] == 0)
            if (cnt) {
                bit_A[i] = 1; bit_B[i] = 1; cnt--;
            }
    if (cnt) {cout << "-1" << '\n'; return 0;}
    cout << bit_A.to_ullong() << ' ' << bit_B.to_ullong() << '\n';
    return 0;
}

E - Set Add Query

Solution

提前用 set<int> 模拟出第 \(i\) 个询问后的 \(S\) 的大小，设为 \(siz[i]\)

对于每个数，答案就是，奇数次出现 \(\sim\) 偶数次出现的 \(siz\) 的和

直接用树状数组或前缀和就可以快速得到

如果最后一个是奇数次，那么就加上个点到最后所有的 \(siz\)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    freopen ("E.in","r",stdin);
    int n, Q; cin >> n >> Q;
    vector<int> q(Q + 1, 0);
    for (int i = 1; i <= Q; i ++)
        cin >> q[i];
    set<int> st;
    vector<ll> cnt(Q + 1, 0);
    for (int i = 1; i <= Q; i++) {
        int x = q[i];
        if (st.count(x)) 
            st.erase(x);
        else
            st.insert(x);
        cnt[i] = st.size();
    }
    
    vector<vector<int> > pos(n + 1, vector<int>());
    for (int i = 1; i <= Q; i++)
        pos[q[i]].push_back(i);
    
    vector<ll> c(Q + 1, 0);
    auto add = [&](int x, int v) {
        for (; x <= Q; x += x & -x)
            c[x] += v;
    };
    auto query = [&](int x) {
        ll res = 0;
        for (; x; x -= x & -x)
            res += c[x];
        return res;
    };

    for (int i = 1; i <= Q; i++) 
        add(i, cnt[i]);
    
    for (int i = 1; i <= n; i++) {
        ll ans = 0;
        if (pos[i].size() & 1)
            pos[i].push_back(Q + 1);
        
        for (int j = 0; j < pos[i].size(); j += 2) {
            ans += query(pos[i][j + 1] - 1) - query(pos[i][j] - 1);
        }
        cout << ans << ' ';
    }
    return 0;
}

F - Non-overlapping Squares

Solution

先考虑两个 \(M\times M\) 正方形的情况

显然，存在一条线，把 \(N\times N\) 的正方形切成两个矩形，\(M\times M\) 的正方形分别在一个矩形中

所以推广到三个 \(M\times M\) 的正方形，就会出现 \(6\) 种情况：

image.png

每个 \(M\times M\) 的正方形必然分别在一个矩形中

我们先求出每个点为右下角作的点的 \(M\times M\) 的区间和

然后对于每个单独的矩形块，只需要找矩形内的最大值即可

可以使用线段树套线段树解决，时间复杂度为 \(O(n^2\log ^2 n)\)

我在具体实现时只写了三个，然后通过旋图去求另外三个

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e17;
const int maxn = 1e3 + 1;

ll maxv[maxn << 2][maxn << 2];

struct Segment_Tree {
    int n;

    void build_y (int u, int rt, int l, int r) {
        maxv[rt][u] = -inf;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build_y(u << 1, rt, l, mid);
        build_y(u << 1 | 1, rt, mid + 1, r);
    }

    void build_x (int u, int l, int r) {
        build_y (1, u, 1, n);
        if (l == r) return;
        int mid = (l + r) >> 1;
        build_x(u << 1, l, mid);
        build_x(u << 1 | 1, mid + 1, r);
    }

    void init(int _n) {
        n = _n;
        build_x(1, 1, n);
    }

    void update_y(int u, int rt, int l, int r, int y, ll val) {
        if (l == r) {
            maxv[rt][u] = max(maxv[rt][u], val);
            return;
        }
        int mid = (l + r) >> 1;
        if (y <= mid) update_y(u << 1, rt, l, mid, y, val);
        else update_y(u << 1 | 1, rt, mid + 1, r, y, val);
        maxv[rt][u] = max(maxv[rt][u << 1], maxv[rt][u << 1 | 1]);
    }
    void update_x(int u, int l, int r, int x, int y, ll val) {
        update_y(1, u, 1, n, y, val);
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (x <= mid) update_x(u << 1, l, mid, x, y, val);
        else update_x(u << 1 | 1, mid + 1, r, x, y, val);
    }
    ll query_y (int u, int rt, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr)
            return maxv[rt][u];
        int mid = (l + r) >> 1;
        ll res = -inf;
        if (ql <= mid)
            res = max(res, query_y(u << 1, rt, l, mid, ql, qr));
        if (qr > mid)
            res = max(res, query_y(u << 1 | 1, rt, mid + 1, r, ql, qr));
        return res;
    }
    ll query_x (int u, int l, int r, int qlx, int qrx, int qly, int qry) {
        if (qlx <= l && r <= qrx)
            return query_y (1, u, 1, n, qly, qry);
        int mid = (l + r) >> 1;
        ll res = -inf;
        if (qlx <= mid)
            res = max(res, query_x(u << 1, l, mid, qlx, qrx, qly, qry));
        if (qrx > mid)
            res = max(res, query_x(u << 1 | 1, mid + 1, r, qlx, qrx, qly, qry));
        return res;
    }
}st;

ll sum[maxn][maxn], a[maxn][maxn];

ll solve (int n, int m, vector<vector<ll> >& mp) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + mp[i][j]; // 2维前缀和
        
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i < m || j < m) { a[i][j] = -inf; continue; }
            a[i][j] = sum[i][j] - sum[i - m][j] - sum[i][j - m] + sum[i - m][j - m]; // 2维区间和
        }
    
    st.init(n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            st.update_x(1, 1, n, i, j, a[i][j]);
    
    ll ans = -inf, now_1, now_2, now_3;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i >= m && j - i >= m && n - j >= m) {
                now_1 = st.query_x (1, 1, n, 1, n, 1, i);
                now_2 = st.query_x (1, 1, n, 1, n, i + m, j);
                now_3 = st.query_x (1, 1, n, 1, n, j + m, n);
                ans = max(ans, now_1 + now_2 + now_3);
            }

            if (i >= m && j >= m && n - j >= m && n - i >= m) {
                now_1 = st.query_x (1, 1, n, 1, i, 1, n);
                now_2 = st.query_x (1, 1, n, i + m, n, 1, j);
                now_3 = st.query_x (1, 1, n, i + m, n, j + m, n);
                ans = max(ans, now_1 + now_2 + now_3);
            }

            if (i >= m && n - i >= m && j >= m && n - j >= m) {
                now_1 = st.query_x (1, 1, n, i + m, n, 1, n);
                now_2 = st.query_x (1, 1, n, 1, i, 1, j);
                now_3 = st.query_x (1, 1, n, 1, i, j + m, n);
                ans = max(ans, now_1 + now_2 + now_3);
            }
        }
    return ans;
}

inline ll read_ll() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

inline int read_int() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main() {
    freopen ("F.in", "r", stdin);
    freopen ("F.out", "w", stdout);
    int n, m; n = read_int(); m = read_int();
    vector<vector<ll> > mp(n + 1, vector<ll>(n + 1, 0)), sum(n + 1, vector<ll>(n + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            mp[i][j] = read_ll();
    
    ll ans = solve(n, m, mp);
    for (int k = 0; k < 1; k++) {
        // rotate 90 degree
        vector<vector<ll> > tmp(n + 1, vector<ll>(n + 1, 0));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                tmp[i][j] = mp[j][n - i + 1];
        mp = tmp;
        ans = max(ans, solve(n, m, mp));
    }
    cout << ans << endl;
    return 0;
}

标签：AtCoder,ch,int,题解,ll,st,347,query,now
From： https://www.cnblogs.com/martian148/p/18106881

相关文章

  • AtCoder Beginner Contest 347 (A~E)
    #AtCoderBeginnerContest347(A~E)这场C>E>D不好评价...(DE赛后一发过，被C卡死了)A模拟即可。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllN=2e5+5;lln,k,a[N];intmain(){ ios::sync_with_stdio(false); cin>>......
  • CCF-CSP真题《202309-3 梯度求解》题解
    题目string转longlong忘记处理负数卡了半天，服了#include<iostream>#include<cstdio>#include<cstring>#include<sstream>typedeflonglongll;usingnamespacestd;intn,m,temp;lla[302];stringf,x,b;llmod=1e9+7;structnode{ stringcon; n......
  • 矩阵匹配【华为OD机试JAVA&Python&C++&JS题解】
    一.题目-矩阵匹配从一个NM（N<=M)的矩阵中选出N个数，任意两个数字不能在同一行或同一列，求选出来的N个数中第K大的数字的最小值是多少。输入描述：输入矩阵要求：1<=K<=N<=M<=150输入格式：NMKNM矩阵输出描述：N*M的矩阵中可以选出M!/N!种组合数组，每个组合数组中第K大的数中的......
  • 文本统计分析【华为OD机试JAVA&Python&C++&JS题解】
    一.题目-文本统计分析有一个文件,包含以一定规则写作的文本,请统计文件中包含的文本数量规则如下文本以";“分隔，最后一条可以没有”;"，但空文本不能算语句，比如"COMMANDA;;"只能算一条语句.注意,无字符/空白字符/制表符都算作"空"文本文本可以跨行,比如下面,......
  • [ABC347C] Ideal Holidays题解
    [ABC347C]IdealHolidays题解原题传送门原题传送门（洛谷）​ 题意翻译：​ 在\(AtCoder\)王国中，一个周有\(A+B\)天。其中在一周中，\([1,A]\)天是假日，\([A+1,B]\)天是工作日。​ 高桥有\(N\)个计划，第\(i\)个计划安排在\(i\)天后。他不知道今天是周几，但他想知道是否......
  • AT_abc347_d 的题解
    （一）数学题。根据\(C\)的值，可以得出\(x\)和\(y\)有\(s1+s\)个相同的数位和\(s2\)个不同的数位。\(s1\)是\(C\)的二进制中\(0\)的数量，\(s2\)是\(C\)的二进制中\(1\)的数量。\(x\)和\(y\)可以通过在开头放\(s\)个\(1\)的方式既不改变异或大小，又能凑到......
  • AT_abc347_e的题解
    （一）可能因为我太菜了，感觉D>E。用\(vis_i\)表示\(i\)是否出现，\(sum_i\)表示当前集合大小。用vector维护出现的区间的端点。将\(sum\)数组前缀和即可。（二）AC代码。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,q,x,siz,sum[200010];......
  • AtCoder Beginner Contest 347
    ATlinkProblemAandB略。ProblemC按照模\(a+b\)分类，记录最大值和最小值，如果差值小于等于假期时间即可，否则还需要判断按照\(d_i=D_i\bmod(a+b)\)排序后相邻的两个是否满足条件。ProblemD分离出\(C\)的二进制位，然后对于每一位\(c_i>0\)尝试在\(A,B\)......
  • ABC 347
    C题意：给定\(n\)个数\(d_1\simd_n\)，求是否存在一个数\(s\)使得\(1\le(d_i+s)\bmod(a+b)\lea\)。显然可以每个数先模\(a+b\)，然后排序。结论：存在当且仅当存在一个数\(i\)使得\((d_{i+1}-d_i)\bmod(a+b)>b\)，\(d_{n+1}=d_1\)。F题意：在\(n\timesn\)的矩阵中找......
  • BZOJ4977 跳伞求生题解
    传送门题意：有\(n\)个队友和\(m\)个敌人，每个队友\(i\)有\(a_i\)颗子弹。敌人\(j\)有\(b_j\)颗子弹。队友击杀敌人，必须\(a_i>b_j\)，然后会获得\(a_i-b_j+w_j\)的收益。（\(w_j\):每个敌人都有一个参数）每个队友只能打一个敌人，可以不打。求最大收益。【费用流模型......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99