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

AtCoder Beginner Contest 326

时间:2023-11-26 19:35:21浏览次数:33  
标签:AtCoder Beginner int res cin long flag 326 using

A - 2UP3DOWN

#include<bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int a, b;
    cin >> a >> b;
    if (a < b and b - a <= 2)
        cout << "Yes\n";
    else if (a > b and a - b <= 3)
        cout << "Yes\n";
    else
        cout << "No\n";

    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    solve();
    return 0;
}

B - 326-like Numbers

#include<bits/stdc++.h>

using namespace std;

#define int long long

void solve() {

}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    for( int a , b , c; n ; n ++ ){
        a = n % 10 , b = ( n / 10 ) % 10 , c =  n / 100;
        if( b * c == a ){
            cout << n << "\n";
            return 0;
        }
    }
    return 0;
}

C - Peak

#include<bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto &i: a) cin >> i;
    sort(a.begin(), a.end());
    int res = 0;
    for( int l = 0 , r = 0 ; l < n ; l ++ ){
        while( r+1 < n and a[r+1] - a[l] < m ) r ++;
        res = max( res , r - l + 1);
    }
    cout << res << "\n";
    return 0;
}

D - ABC Puzzle

因为n 的范围很小,所以可以直接暴搜过去,加一些剪枝就能跑的飞快

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i32 = int32_t;
using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e10, INF = 1e18;
const int mod = 998244353;

const int N = 1e6;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    string r, c;
    cin >> n >> r >> c;
    vector g(n, vector<char>(n, '.'));
    vi visR(n), visC(n);

    auto dfs = [&](auto &&self, int x, int y) -> void {
        if (y == n) {
            if (visR[x] < 7) return;
            self(self, x + 1, 0);
            return;
        }
        if (x == n) {
            bool flag = true;
            for (int i = 0; flag and i < n; i++)
                if (visR[i] != 7 or visC[i] != 7) flag = false;
            for (int i = 0; flag and i < n; i++) {
                for (int j = 0; flag and j < n; j++) {
                    if (g[i][j] == '.') continue;
                    if (g[i][j] != r[i]) flag = false;
                    break;
                }
                for (int j = 0; flag and j < n; j++) {
                    if (g[j][i] == '.') continue;
                    if (g[j][i] != c[i]) flag = false;
                    break;
                }
            }

            if (flag) {
                cout << "Yes\n";
                for (auto it: g) {
                    for (auto c: it) cout << c;
                    cout << "\n";
                }
                exit(0);
            }
            return;
        }

        self(self, x, y + 1);
        for (int i = 0; i < 3; i++) {
            if ((visR[x] & (1 << i)) or (visC[y] & (1 << i))) continue;
            visR[x] ^= (1 << i), visC[y] ^= (1 << i);
            g[x][y] = char(i + 'A');
            self(self, x, y + 1);
            visR[x] ^= (1 << i), visC[y] ^= (1 << i);
            g[x][y] = '.';
        }

    };

    dfs(dfs, 0, 0);
    cout << "No\n";
    return 0;
}

E - Revenge of "The Salary of AtCoder Inc."

当前状态是\(x\),\(f[x]\)表示当前掷出值\(x\)为,并继到游戏结束期望获得的钱数。

显然\(f[n]=0\)

对于当前状态\(x\),有两种情况

  1. \(\frac x n\)掷出$y\le x $,游戏结束,后继收入为\(0\)
  2. 对于\(i>x\),有$\frac 1 n \(掷出\)i\(,收入为\)a_i\(,后继收入为\)f[i]$

所以\(f[x]=\frac x n \times 0 + \sum_{i=x+1}^{n} \frac 1 n ( f[i] + a[i] )\)

所以倒序枚举状态,在后缀和统计一下可以\(O(1)\)的转移。

#include<bits/stdc++.h>

using namespace std;

#define int long long

using i32 = int32_t;
using vi = vector<int>;

const int inf = 1e18;
const int mod = 998244353;

int power(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod, y /= 2;
    }
    return res;
}

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

i32 main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vi a(n);
    for (auto &i: a) cin >> i;
    vi f(n + 1);
    int res = 0, invN = inv(n);
    for (int i = n - 1; i >= 0; i--)
        res = (res + res * invN % mod + a[i]) % mod;
    cout << res * invN % mod << "\n";
    return 0;
}

标签:AtCoder,Beginner,int,res,cin,long,flag,326,using
From: https://www.cnblogs.com/PHarr/p/17857752.html

相关文章

  • AtCoder Beginner Contest 322
    A-FirstABC2#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definempmake_pairusingvi=vector<int>;usingpii=pair<int,int>;voidsolve(){intn;strings;cin>>n>>s;......
  • AtCoder 329. E - Stamp (搜索 + 思维
    importjava.util.Scanner;classMain{staticintn,m;staticStrings,t;staticStringBuilderox;/***思路:*思路的大门:题目要要求把x变成s,我们可以反过来,把s变成只有#的x,所以我们就有了思路*1.从前......
  • TOYOTA SYSTEMS Programming Contest 2023(AtCoder Beginner Contest 330)
    TOYOTASYSTEMSProgrammingContest2023(AtCoderBeginnerContest330)A-CountingPassesintmain(){IOS;cin>>n>>m;intans=0;rep(i,1,n)cin>>k,ans+=k>=m;cout<<ans;return0;}B-......
  • AtCoder Beginner Contest 330
    A-CountingPasses(abc330A)题目大意给定\(n\)个学生的分数,以及及格分\(x\),问多少人及格了。解题思路依次判断即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);cin.ti......
  • AtCoder Beginner Contest 329 F
    AtCoderBeginnerContest329FF-ColoredBall(atcoder.jp)(启发式合并)问题陈述有\(N\)个编号为\(1,2,\ldots,N\)的盒子。最初,盒子\(i\)中有一个颜色为\(C_i\)的小球。给你\(Q\)个查询,你要按顺序处理。每个查询都由一对整数\((a,b)\)给出,并要求您执行以下......
  • AtCoder Regular Contest 144 E GCD of Path Weights
    洛谷传送门AtCoder传送门喵喵题。考虑若所有点权都已确定,如何求\(1\)到\(n\)所有路径权值和的\(\gcd\)。考虑如何check一个\(x\)是否合法。\(x\)合法的充要条件是,把不能从\(1\)到达的点和不能到达\(n\)的点扔掉后,存在一组\(\{f_n\}\),使得对于每条\(u\tov\)......
  • [AtCoder Toyota2023 Spring Final] Git Gud
    拜谢MagicDuck大神。其次我很喜欢洛谷逆天翻译把大翻译成小……首先考虑算一下贡献,考虑每个点的深度,一开始都是1,进行合并以后相当于首先把两个端点的深度累计到答案里,然后再选择一边给它的联通块内每个点深度增加1。那么容易发现我们可以算贡献转化为每个联通块权值为它向外......
  • AtCoder Beginner Contest 329
    劳累一天不该写题,启发式合并都写错了A-Spread(abc329A)题目大意给定一个字符串,将每个字符输出出来,中间留个空格。解题思路遍历输出即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_std......
  • AtCoder Beginner Contest(abc) 326
    B-326-likeNumbers难度:⭐题目大意如果一个三位数的百位和十位的乘积等于个位,那么这个数就是合法的;问大于等于n的最小的合法的数是多少;解题思路因为数据范围很小,所以可以直接暴力;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios......
  • AtCoder Beginner Contest 329
    C-Countxxx题意是:给你一个字符串,求出字符串里面相同字母的子串数量思路:用map映射即可,取每个字母的最大长度,然后加起来usingnamespacestd;intmain(){ intn; strings; cin>>n>>s; map<char,int>mp; intct=1; for(inti=1;i<n;i++){ if(s[i]!=s[i-1]){ mp[s[......