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

AtCoder Beginner Contest 310

时间:2023-07-18 19:44:18浏览次数:80  
标签:AtCoder cout Beginner int 310 nullptr cin long tie

A - Order Something Else

#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 , p , q;
    cin >> n >> p >> q;
    int res = p;
    for( int x ; n ; n -- ){
        cin >> x , res = min( res , q + x );
    }
    cout << res << "\n";
    return 0;
}

B - Strictly Superior

#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> p(n + 1);
    vector<vector<int>> f(n + 1, vector<int>(m + 1));
    for (int i = 1, c; i <= n; i++) {
        cin >> p[i] >> c;
        for (int x; c; c--)
            cin >> x, f[i][x] = 1;
    }
    for( int i = 1 ; i <= n ; i ++ ){
        for( int j = 1 ; j <= n ; j ++ ){
            if( p[i] < p[j] ) continue;
            int q = 1 , t = 0 ;
            for( int l = 1 ; q && l <= m ; l ++ ){
                if( f[j][l] > f[i][l] ) t ++;
                else if( f[j][l] < f[i][l] ) q = 0;
            }
            if( q == 0 ) continue;
            if( p[i] > p[j] || t > 0 ){
                cout << "Yes\n";
                return 0;
            }
        }
    }
    cout << "No\n";
    return 0;
}

C - Reversible

只存字典序较小的

#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;
    cin >> n;
    set<string> cnt;
    for (string s, t; n; n--) {
        cin >> s, t = s;
        reverse(s.begin(),s.end());
        s = min( s , t );
        cnt.insert(s);
    }
    cout << cnt.size() << "\n";
    return 0;
}

D - Peaceful Teams

直接暴搜,注意在搜索的过程中要及时盼到不合法的情况

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n, T, m, res;
vector<vector<int>> g;
vector<set<int>> s;

void dfs(int x) {
    if (x > n) {
        if( s.size() == T ) res ++;
        return;
    }
    if( s.size() + n - x + 1 < T ) return;
    if (s.size() < T) {
        s.push_back(set<int>());
        s.back().insert(x);
        dfs(x + 1);
        s.pop_back();
    }
    for (auto &i: s) {
        int f = 1;
        for (auto j: g[x])
            if (i.count(j)) {
                f = 0;
                break;
            }
        if( f == 0 ) continue;
        i.insert(x);
        dfs( x + 1 );
        i.erase(x);
    }
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> T >> m;
    g = vector<vector<int>>(n + 1);
    for (int x, y; m; m--) {
        cin >> x >> y;
        if (x < y) swap(x, y);
        g[x].push_back(y);
    }
    dfs(1);
    cout << res << "\n";
    return 0;
}

E - NAND repeatedly

简单的做一个 dp 就好了。

#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 , res = 0 ;
    string s;
    cin >> n >> s;
    vector<array<int,2>> f(n+1);
    for( int i = 1 , x ; i <= n ; i ++ ){
        x = s[i-1] - '0';
        if( x == 1 ) {
            f[i][1] = 1 + f[i-1][0];
            f[i][0] = f[i-1][1];
        }else{
            f[i][1] = f[i-1][0] + f[i-1][1];
            f[i][0] = 1;
        }
        res += f[i][1];
    }
    cout << res << '\n';
    return 0;
}

F - Make 10 Again

状压 dp,\(f[i][s]\)表示前\(i\)个数选部分数可以构成集合的概率。

对于枚举除了的\(s\)以及当前骰子掷出的数字\(j\),有三种情况

  1. s表示当前不要
  2. 1<<(j-1)表示之前的都不要
  3. s<<j表示之前的加上当前的

把上述三种情况与到一起就是当前的数字全部可以构成的集合,注意要与\((1<<10)-1\)与一下防止溢出。

最后枚举所有包含10的集合把概率求和即为答案

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;
const int N = 1 << 10;

int power(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod, y >>= 1;
    }
    return ans;
}

int inv(int x) {
    return power(x, mod - 2);
}

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

int32_t main() {
    int n = read();
    vector<int> f(N);
    f[0] = 1;
    for (int x, y, invs; n; n--) {
        x = read(), y = min(10ll, x), invs = inv(x);
        vector<int> g(N);
        for (int s = 0; s < N; s++) {
            for (int i = 1; i <= y; i++)
                (g[(s | s << i | 1 << (i - 1)) & (N - 1)] += f[s] * invs % mod) %= mod;
            (g[s] += f[s] * (x - y) % mod * invs % mod) %= mod;
        }
        swap(f, g);
    }
    int res = 0;
    for (int i = (1 << 9); i < N; i++)
        (res += f[i]) %= mod;
    cout << res << "\n";
    return 0;
}

标签:AtCoder,cout,Beginner,int,310,nullptr,cin,long,tie
From: https://www.cnblogs.com/PHarr/p/17563959.html

相关文章

  • [ABC310D] Peaceful Teams 题解
    PeacefulTeams题目大意将\(n\)个人分成\(T\)组,要求每组不能包含敌对的人,问有多少种分法。思路分析注意到\(n,T\)均很小,考虑爆搜。注意到直接枚举会枚举到分组顺序的全排列,所以可以强行嵌定大小关系去重。voiddfs(ints){if(s==n+1){for(inti=1;i<=t;......
  • 【2023.07.14】Atcoder:past201912 - 第一回 アルゴリズム実技検定(div4+区域赛难度)过题
    G-Division解法一:位运算+状压枚举(赛时思路)范围显然,可以跑\(2^n\)的算法,考虑位运算状态压缩。以\(\mathcalO(2^n\cdot2^n)\)的复杂度分别枚举位于第一组、第二组中的人,随后计算每一种分组的快乐值,代码较长,赛时敲了半个小时,不过好在一发过了。总结:其实代码里面的剪枝完......
  • beginnersbook C 语言教程·翻译完成 | ApacheCN
    译者:飞龙协议:CCBY-NC-SA4.0首先学习C基础知识如何安装TurboC++:编译并运行C程序C程序结构-第一个C程序C关键词-保留字C中的决策控制语句C编程中的if语句C-if..else,嵌套if..else和else..if语句C编程的switch-case语句C中的循环C编程中for的循环C编程中的wh......
  • beginnersbook C++ 教程·翻译完成 | ApacheCN
    译者:飞龙协议:CCBY-NC-SA4.0基础HelloWorld-第一个C++程序C++中的变量C++中的数据类型C++中的运算符控制语句C++中的if语句C++中的switch-case语句C++中的for循环C++中的while循环C++中的do-while循环C++中的continue语句C++中的break语句C++中的goto语句函数C++......
  • beginnersbook C 语言示例·翻译完成 | ApacheCN
    译者:飞龙协议:CCBY-NC-SA4.0简单的C程序C语言中的HelloWorld程序C程序:检查给定的整数是正还是负C程序:使用递归函数反转给定的数字C程序:查找最大的三个数字C程序:显示Fibonacci序列C程序:使用递归查找数字的阶乘C程序:查找给定范围内的素数C程序:检查阿姆斯特朗数C程序......
  • freee Programming Contest 2023(AtCoder Beginner Contest 310)
    Preface打的就是依托答辩,当时看一眼D感觉是个爆搜不想写就先跳了去想F,结果傻逼了没想出来最后30min了赶紧溜回去把D爆搜写了,但是已经罚时爆炸了,其实如果正常正序做的话排名会挺稳的后面一问包大爷发现F是个傻逼题,只能说计数水平实在是低下A-OrderSomethingElse签到题#i......
  • abc310e <公式递推(dp?)>
    题目E-NANDrepeatedly思路总结公式递推,找到相邻两项间的关系;代码Code#include<iostream>#include<algorithm>#include<vector>#include<cstring>usingnamespacestd;usingLL=longlong;usingPII=pair<int,int>;constintN=1e......
  • abc310d <dfs暴搜-分组方案数 / bitmask表示集合+dp>
    题目D-PeacefulTeams参考:https://www.cnblogs.com/legendstane/p/freee-programming-contest-2023-atcoder-beginner-contest-abc-310-solution.htmlhttps://blog.csdn.net/Muelsyse_/article/details/131747083思路方法1dfs暴搜由于数据范围极小,所以直接暴力即可......
  • AtCoder Beginner Contest 310
    PeacefulTeams\(n\)个运动员,要分成\(t\)个队伍,一共有\(m\)对人不能放在一支队伍里,求方案数,每支队伍至少需要有一个人\(1\leqt\leqn\leq10\)题解:DFS搜索通过数据范围考虑爆搜我们考虑枚举的顺序\(O(n!)\)我们对每个人\(c\)枚举将其加到当前的\(d\)支队伍中新开一......
  • AtCoder Regular Contest 092 E Both Sides Merger
    洛谷传送门AtCoder传送门Keyobservation:每个元素的下标奇偶性不改变。于是讨论最后一个数是下标为奇数还是偶数加起来的数。将下标奇偶性相同的元素分开考虑。对于下标奇偶性相同的元素,不难发现答案的上界是所有\(>0\)的元素之和(没有\(>0\)的元素时选一个最大的),并且一......