首页 > 其他分享 >AtCoder Beginner Contest 312

AtCoder Beginner Contest 312

时间：2023-07-31 19:56:39浏览次数：42  
标签：AtCoder Beginner int 312 nullptr cin back ++ tie

A - Chord

#include <bits/stdc++.h>

using namespace std;

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    string s;
    cin >> s;
    if( s == "ACE" ) cout << "Yes\n";
    else if( s == "BDF" ) cout << "Yes\n";
    else if( s == "CEG" ) cout << "Yes\n";
    else if( s == "DFA" ) cout << "Yes\n";
    else if( s == "EGB" ) cout << "Yes\n";
    else if( s == "FAC" ) cout << "Yes\n";
    else if( s == "GBD" ) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

B - TaK Code

枚举左上角

#include <bits/stdc++.h>

using namespace std;


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto &i: g)
        cin >> i;
    for (int i = 0; i + 8 < n; i++)
        for (int j = 0; j + 8 < m; j++) {
            int f = 1;
            for (int l = i; f && l <= i + 2; l++)
                for (int k = j; f && k <= j + 2; k++)
                    if (g[l][k] != '#') f = 0;
            for (int l = i + 6; f && l <= i + 8; l++)
                for (int k = j + 6; f && k <= j + 8; k++)
                    if (g[l][k] != '#') f = 0;

            for (int l = i; f && l <= i + 3; l++)
                if (g[l][j + 3] != '.') f = 0;
            for (int k = j; f && k <= j + 3; k++)
                if (g[i + 3][k] != '.') f = 0;
            for (int l = i + 5; f && l <= i + 8; l++)
                if (g[l][j + 5] != '.') f = 0;
            for (int k = j + 5; f && k <= j + 8; k++)
                if (g[i + 5][k] != '.') f = 0;


            if (f == 0) continue;
            cout << i + 1 << " " << j + 1 << "\n";
        }
    return 0;
}

C - Invisible Hand

枚举答案\(x\)，设\(a\)为\(A_i\)中小于等于\(x\)的数量，设\(b\)为\(B_i\)中大于等于\(x\)的数量，则随着\(x\)递增，\(a\)递增，\(b\)递减。所以\(b-a\)递减，所以可以二分找到最小的\(x\)满足\(b-a=0\)。在计算\(a,b\)的时候也可直接二分。

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (auto &i: a)
        cin >> i;
    for (auto &i: b)
        cin >> i;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    auto f = [a, b](int x) {
        int A = lower_bound(a.begin(), a.end(), x) - a.begin();
        while (a[A] == x) A++;
        int B = lower_bound(b.begin(), b.end(), x) - b.begin();
        B = b.size() - B;
        return B - A;
    };
    int l = 0, r = 2e9, res, mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (f(mid) <= 0) res = mid ,r = mid - 1;
        else l = mid + 1;
    }
    cout << res << "\n";
    return 0;
}

再来分析，可以发现答案一定是\(A_i,B_i+1\)，所以把\(A,B+1\)放到数组\(C\)中排序，当\(x=0\)时\(b-a=M\)，当\(x=C_1\)时，\(b-a=M-1\)以此类推当\(x=C_M\)时\(b-a=0\)。所以第\(M\)小就是答案。

这里只求第\(M\)小，可以只用nth_element就可以\(O(N)\)求解

#include<bits/stdc++.h>

using namespace std;

int32_t main() {
    int n , m;
    cin >> n >> m;
    vector<int> a(n+m);
    for( int i = 0 ; i < n ; i ++ ) cin >> a[i];
    for( int i = n ; i < n+m ; i ++ ) cin >> a[i] , a[i] ++;
    nth_element( a.begin() , a.begin() + m - 1 , a.end());
    cout << a[m-1];
    return 0;
}

D - Count Bracket Sequences

简单 dp，f[i][j]表示前\(i\)个字符，且\(j\)个左括号尚未匹配的方案数

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3005;
const int mod = 998244353;
int f[N][N];


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    f[0][0] = 1;
    for( int i = 1 ; i <= n ; i ++ ){
        if( s[i-1] == '(' ){
            for( int j = 1 ; j <= n ; j ++ )
                f[i][j] = f[i-1][j-1];
        }else if( s[i-1] == ')' ){
            for( int j = 0 ; j < n ; j ++ )
                f[i][j] = f[i-1][j+1];
        }else {
            for( int j = 0 ; j <= n ; j ++ ){
                if( j-1 >= 0 ) f[i][j] += f[i-1][j-1];
                if( j+1 <= n ) f[i][j] += f[i-1][j+1];
                f[i][j] %= mod;
            }
        }
    }
    cout << f[n][0] << "\n";
    return 0;
}

E - Tangency of Cuboids

因为长方体不会相交，所以我们暴力的标记每个立方体属于哪一个长方体，我们用每个立方体左上角的坐标表示该立方体。

如果两个长方体相邻，这会有两个相邻的立方体属于两个不同长方体。所以可以直接枚举立方体。

#include<bits/stdc++.h>

using namespace std;

const int N = 115;

int g[N][N][N];

int32_t main() {
    int n;
    cin >> n;
    for (int t = 1, a, b, c, x, y, z; t <= n; t++) {
        cin >> a >> b >> c >> x >> y >> z;
        for ( int i = a ; i < x; i++)
            for ( int j = b ; j < y; j++)
                for ( int k = c ; k < z; k++)
                    g[i][j][k] = t;
    }
    
    vector ans( n+1 , set<int>() );
    for (int i = 0; i < 100; i++)
        for (int j = 0; j < 100; j++)
            for (int k = 0; k < 100; k++) {
                if (g[i][j][k] == 0) continue;
                if (g[i + 1][j][k] != 0 && g[i][j][k] != g[i + 1][j][k])
                    ans[g[i][j][k]].emplace(g[i + 1][j][k]), ans[g[i + 1][j][k]].emplace(g[i][j][k]);
                if (g[i][j + 1][k] != 0 && g[i][j][k] != g[i][j + 1][k])
                    ans[g[i][j][k]].emplace(g[i][j + 1][k]), ans[g[i][j + 1][k]].emplace(g[i][j][k]);
                if (g[i][j][k + 1] != 0 && g[i][j][k] != g[i][j][k + 1])
                    ans[g[i][j][k]].emplace(g[i][j][k + 1]), ans[g[i][j][k + 1]].emplace(g[i][j][k]);

            }
    for (int i = 1; i <= n; i++)
        cout << ans[i].size() << "\n";
    return 0;
}

F - Cans and Openers

我们可以枚举选择多少个易拉罐，然后可以用二分的方式求出最多可以获得多少个普通罐。

对于易拉罐、普通罐、开罐器我们都可以贪心的选择，所以可以排序求前缀和。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3005;
const int mod = 998244353;
int f[N][N];


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, res = 0;
    cin >> n >> m;
    vector<int> a, b, c;
    a.push_back(0), b.push_back(0), c.push_back(0);
    for (int i = 1, t, x; i <= n; i++) {
        cin >> t >> x;
        if (t == 0) a.push_back(x);
        else if (t == 1) b.push_back(x);
        else c.push_back(x);
    }
    int A = a.size() - 1, B = b.size() - 1, C = c.size() - 1;

    sort(a.begin() + 1, a.end(), greater<int>());
    for (int i = 1; i <= A; i++) a[i] += a[i - 1];
    sort(b.begin() + 1, b.end(), greater<int>());
    for (int i = 1; i <= B; i++) b[i] += b[i - 1];
    sort(c.begin() + 1, c.end(), greater<int>());
    for (int i = 1; i <= C; i++) c[i] += c[i - 1];
    
    for (int i = 0, l, r, cnt, mid; i <= min(m, A); i++) {
        l = 0, r = min(B, m - i), cnt = 0;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (c[min(C, m - i - mid)] >= mid) cnt = mid, l = mid + 1;
            else r = mid - 1;
        }
        res = max(res, a[i] + b[cnt]);
    }
    cout << res << "\n";
    return 0;
}

G - Avoid Straight Line

首先不管题目要求，任意选三个\(C_n^2\)，然后减去三个点在一条链上的情况。

我们枚举中间点，考虑两个端点只有两种情况

  1. 一个点子树中的节点，另一个不是
  2. 两个点都是子树中的，且属于不同的子树

这样简单的分类讨论一下就可以了。

#include <bits/stdc++.h>

using namespace std;

#define int long long

vector<vector<int>> e, g;
vector<int> f;

void dfs(int x) {
    f[x] = 1;
    for (auto y: e[x]) {
        if (f[y]) continue;
         g[x].push_back(y);
        dfs(y);
        f[x] += f[y];
    }
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    e.resize(n + 1), g.resize(n + 1);
    for (int i = 1, x, y; i < n; i++)
        cin >> x >> y, e[x].push_back(y), e[y].push_back(x);
    f.resize(n + 1);
    dfs(1);
    int res = n * (n - 1) * (n - 2) / 6;
    // f[i]i i的子树大小， cnt 中间包含 i的链的数量
    for (int i = 1 , cnt ; i <= n; i++){
        cnt = 0;
        for( auto j : g[i] ) // 两个点在不同的子树中
            cnt +=  f[j] * ( f[i] - 1 - f[j] );
        cnt /= 2;
        cnt += ( f[i] - 1 ) * ( n - f[i] );
        res -= cnt;
    }

    cout << res;
    return 0;
}

标签：AtCoder,Beginner,int,312,nullptr,cin,back,++,tie
From： https://www.cnblogs.com/PHarr/p/17594330.html

相关文章

  • [UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312) - A
    UNIQUEVISIONProgrammingContest2023Summer(AtCoderBeginnerContest312)-AtCoderA-Chord(atcoder.jp)#include<bits/stdc++.h>#defineendl'\n'usingnamespacestd;intmain(){vector<string>str{"ACE",&qu......
  • 【题解】[ABC312E] Tangency of Cuboids（adhoc）
    【题解】[ABC312E]TangencyofCuboids少见的at评分\(2000+\)的ABCE题，非常巧妙的一道题。特别鸣谢：@dbxxx给我讲解了他的完整思路。题目链接ABC312E-TangencyofCuboids题意概述给定三维空间中的\(n\)个长方体，每个长方体以其一条体对角线的两个端点的坐标形式......
  • [ABC312] 题解 [D~Ex]
    [ABC312]题解[D~Ex]D-CountBracketSequences一个括号序列\(s\)包含(,),?，?可以填任意括号，问你填完后有多少种合法序列方式。这是一个Classical的括号序列DP，使用这个状态表示可以解决很多括号序列问题：\(dp[i][j]\)表示已经摆好了前\(i\)个字符，有\(j\)个没......
  • 【题解】[ABC312G] Avoid Straight Line（容斥，树上统计，dfs）
    【题解】[ABC312G]AvoidStraightLine题目链接[ABC312G]AvoidStraightLine题意概述给定一棵\(n\)个节点的树，第\(i\)条边连接节点\(a_i\)和\(b_i\)，要求找到满足以下条件的三元整数组\((i,j,k)\)的数量：\(1\lei<j<k\len\)；对于树上任意一条简单路径，都不同时经......
  • Atcoder-Beginner-Contest-312 A~Ex
    \(Atcoder-Beginner-Contest-312\)AB过于简单，在此略去。\(C-Invisible\)\(Hand\)题意：给定长为\(n\)的数组\(a\)，长为\(m\)的数组\(b\)，找到最小的非负整数\(x\)，使得\(\sum_{i=1}^n[a_i\lex]\ge\sum_{i=1}^m[b_i\gex]\)题解：容易发现，随着\(x\)的增大，右式单调不升，左......
  • abc312e <暴力>
    题目E-TangencyofCuboids思路意识到本题的数据规模可以暴力去做！\(N=100\)，\(N^3\)直接遍历整个空间可做；立方体间不相交，也就是可以直接遍历立方体中的所有点进行标记，不会超过整体空间体积；立方体不相交，也就是说同一个位置尽可能被标记一次；将空间中每个立方体所占点进行标......
  • abc312d <dp, 括号匹配方案数>
    题目D-CountBracketSequences思路dp[i][j]为考虑前\(i\)个位置，待匹配的(有\(j\)个的方案数；代码点击查看代码#include<iostream>#include<algorithm>#include<vector>#include<cstring>usingnamespacestd;usingLL=longlong;usingPII=pair<......
  • HDU 1312 Red and Black 题解
    //注意边界判断，调了好久#include<iostream>#include<queue>usingnamespacestd;#definecheck(x,y)(x<wx&&x>=0&&y<hy&&y>=0)structnode{intx,y;};charroom[23][23];intn,m,wx,hy,num;intdir[4][2]={......
  • abc312c <二分答案>
    题目C-InvisibleHand思路二分X，同时二分得到buyer和seller的人数（很精巧的二分~）；当然，从复杂度角度，\(O(N\logN)\)也是可以的；实际上可以写成\(O(N)\)的形式？感觉线性扫描也可？代码点击查看代码#include<iostream>#include<algorithm>#include<vector>#include<cst......
  • ABC312
    T1：Chord模拟代码实现s=input()ifsin'ACE,BDF,CEG,DFA,EGB,FAC,GBD':print('Yes')else:print('No')T2：TaKCode模拟代码实现#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<(n);++i)using......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99