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

AtCoder Beginner Contest 295

时间:2023-03-28 21:33:40浏览次数:44  
标签:AtCoder ch Beginner int getchar while && 295 mod

A - Probably English

#include <bits/stdc++.h>

using namespace std;

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;
}

int main() {
    set<string> st;
    st.insert("and");
    st.insert("not");
    st.insert("that");
    st.insert("the");
    st.insert("you");
    int n;
    cin >> n;
    string s;
    for( ; n ; n -- ){
        cin >> s;
        if( st.count(s) ) cout << "Yes" , exit(0);
    }
    cout << "No";
    return 0;
}

B - Bombs

#include <bits/stdc++.h>

using namespace std;

int f[25][25] ;

int main() {
    int n , m;
    cin >> n >> m;
    vector<int> x , y , b;
    for( int i = 1 ; i <= n ; i ++ ){
        string s;
        cin >> s;
        for( int j = 1 ; j <= m ; j ++ ){
            if( s[j-1] == '#' ) f[i][j] = 1;
            else if( s[j-1] >= '1' && s[j-1] <= '9' )
                x.push_back(i) , y.push_back(j) , b.push_back( s[j-1] - '0' );
        }
    }
    for( int i = 1 ; i <= n ; i ++ ){
        for( int j = 1 ; j <= m ; j ++ ){
            if( f[i][j] == 0 ) continue;
            for( int k = 0 ; k < x.size() ; k ++ ){
                if( abs( i - x[k] ) + abs( j - y[k] ) <= b[k] ){
                    f[i][j] = 0;
                    break;
                }
            }
        }
    }
    for( int i = 1 ; i <= n ; i ++ ){
        for( int j = 1 ; j <= m ; j ++ )
            cout << ".#"[ f[i][j] ];
        cout << "\n";
    }

    return 0;
}

C - Socks

#include <bits/stdc++.h>

using namespace std;

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;
}
int main() {
    int n = read();
    map<int,int> mp;
    for( int x ; n ; n -- )
        x = read() , mp[x] ++;
    int res = 0;
    for( auto [k,v] : mp )
        res += v/2;
    cout << res;

    return 0;
}

D - Three Days Ago

如果一个子区间内所有的数都只出现偶数次的话,就一定 happy 的。

我们用一个十位的二进制来表示前缀中每个字母出现了奇数次还是偶数次。这个实际上可以用前缀异或和来维护。

那么我们只需要统计这个十位二进数每种出现了多少次,然后对每一种求一个\(C_n^2\)即可

#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);
    string s;
    cin >> s;
    int t = 0;
    bitset<10> T;

    map<int,int> cnt;
    cnt[t] ++;
    for( auto i : s ){
        t ^=  1 << ( i - '0' );
        cnt[t] ++;
    }
    int res = 0;
    for( auto [ k , v ] : cnt )
        res += v * ( v - 1 ) / 2 ;
    cout << res;

    return 0;
}

E - Kth Number

设第\(k\)大的数字是\(x\)则题目要求的就是\(EX= \sum_{i=1}^n i\times P(x=i)\)

\[EX = 1P(x=1) + 2P(x=2) + \cdots nP(x=n)\\ = \sum_{i=1}^nP(x=i) + \sum_{i=2}^nP(x=i)+\cdots+\sum_{i=n}^{n}P(x=i)\\ = P(x\ge1) + P(x\ge 2) + \cdots+P(x\ge n) =\sum_{i=1}^n P(x>i) \]

这样转换的好处就是算的时候比较方便,我们直接枚举 \(i\)的值,然后统计数列中的值即可。

如果已经有大于等于\(n-k+1\)个数大于等于\(i\),则概率为\(1\),因为不用操作第\(k\)个数也大于\(i\)。

如果已经有大于\(k\)个数小于\(i\),则概率为 0。

如果都不满足的话,就可以通过操作是条件满足,设\(b\)表示当前大于\(i\)的个数,\(p=\frac{m-i+1}{m}\)表示把一个 0 变成大于\(i\)的概率,\(cnt_0\)表示\(0\)的个数,概率是\(\sum_{j=n-k+1 -b}^{cnt_0} C_{cnt_0}^j p^j(1-p)^{cnt_0-j}\)

把所有的概率求和就是答案

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;

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) % mod;
}

const int N = 2005;
int fact[N], invFact[N];

int A(int x, int y) { // x 中选 y 排序
    return fact[x] * invFact[x - y] % mod;
}

int C(int x, int y) { // x 中选 y 个
    return fact[x] * invFact[x - y] % mod * invFact[y] % mod;
}

void init() {
    fact[0] = 1, invFact[0] = inv(1);
    for (int i = 1; i < N; i++)
        fact[i] = fact[i - 1] * i % mod, invFact[i] = inv(fact[i]);
}

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() {
    init();
    int n = read(), m = read(), k = read(), res = 0;
    vector<int> cnt(m + 1), a(m + 1), b(m + 1);
    for (int x, i = 1; i <= n; i++) x = read(), cnt[x]++;
    b[m] = cnt[m];
    for (int i = 1; i <= m; i++) a[i] = a[i - 1] + cnt[i];
    for (int i = m - 1; i >= 1; i--) b[i] = b[i + 1] + cnt[i];

    for (int i = 1, p, q; i <= m; i++) {
        if (a[i - 1] > k) continue;
        if (b[i] >= n - k + 1) {
            res = (res + 1) % mod;
            continue;
        }
        p = (m - i + 1) * inv(m) % mod, q = ( 1 - p + mod ) % mod;
        for (int j = n - k + 1 - b[i]; j <= cnt[0]; j++)
            res = (res + C(cnt[0], j) * power(p, j) % mod * power(q, cnt[0] - j) % mod) % mod;
    }
    cout << res;
    return 0;
}

G - Minimum Reachable City

当加边(u,v)的时候保证了(v,u)已经联通了,此时有两种情况如果(u,v)已经联通了,此时加边对结果实际上是没有影响的,可以忽略。另一种情况是不联通,那么此时等价于将(v,u)之间的路径全部建一遍反向边。

所以这个问题就可以用并查集来维护联通性,同时保证根节点是该联通块中最小的一个,所以要注意加边和并两个集合的方向。

在一开始,我们就只是存一下反向边,当需要加(u,v)就从u开始一路加反向边直到u,v联通,回答的时候直接回答该点所在联通快递根节点即可。

#include<bits/stdc++.h>

using namespace std;

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;
}

class dsu{
private:
    vector<int> fa;
public:
    dsu( int n = 1 ){
        fa = vector<int>( n+1 , -1 ) , fa[0] = 0;
    }
    int getfa( int x ){
        if( fa[x] < 0 ) return x;
        return fa[x] = getfa( fa[x] );
    }
    void merge( int x , int y ){
        x = getfa(x) , y = getfa(y);
        if( x == y ) return ;
        fa[x] = y;
    }
    bool check( int x , int y ){
        x = getfa(x) , y = getfa(y);
        return ( x == y );
    }
};

int32_t main() {
    int n = read();
    vector<int> p(n+1);
    p[1] = 1;
    for( int i = 2 ; i <= n ; i ++ ) p[i] = read();
    dsu d(n);
    for( int q = read() , op , x , y ; q ; q -- ){
        op = read();
        if( op == 1 ){
            x = read() , y = read();
            while( !d.check( x , y ) ){
                x = d.getfa(x);
                d.merge( x , p[x] );
            }
        }else x = read() , printf("%d\n" , d.getfa(x) );
    }
    return 0;
}


标签:AtCoder,ch,Beginner,int,getchar,while,&&,295,mod
From: https://www.cnblogs.com/PHarr/p/17266778.html

相关文章

  • Coinc1dens's lessons for cryptography beginner
    Coinc1dens'slessonsforcryptographybeginner10分题懒得写,赛后浅写一下(有些还真写不出来)太屑了古典懒得写,相信都写的出来1.childexgcdi即为m在模p情况下的乘法逆......
  • AtCoder Beginner Contest 145
    AtCoderBeginnerContest145https://atcoder.jp/contests/abc145D-Knight乍一看以为是dp,但是数据范围不允许。仔细一看发现,两种操作的次数是固定的,可以枚举出来每......
  • AtCoder Beginner Contest 148
    AtCoderBeginnerContest148https://atcoder.jp/contests/abc148这场比较简单D-BrickBreak二分orLIS#include<bits/stdc++.h>#definelllonglongusingn......
  • 【题解】Atcoder ABC295 A-G
    A.ProbablyEnglish题目分析:直接每一个单词判一下就好了。代码:点击查看代码#include<bits/stdc++.h>usingnamespacestd;intmain(){ intn;scanf("%d",&n); bo......
  • [ABC295Ex] E or m 题解
    状压dp,2hd4me/ng。题意开始你有一个全\(0\)矩阵,你可以随意执行如下操作:选择任意一行,将其从最左端开始的连续一段染成\(1\)。选择任意一列,将其从最上端开始的连......
  • AT_abc295_d 题解
    一、题目描述:给你一个由数字0~9组成的字符串,长度为N(1<=N<=500000)。求出满足1<=l<=r<=N且在l~r区间内所有数字都出现了偶数次的整数对l,r有多少对。......
  • ABC295 D题 题解
    题意简述给定一个长度不超过\(5\times10^5\)的,仅有数字构成的字符串,问存在多少段子串,使得子串内字符重新排序后,前半段与后半段相同?做法分析重组后前后两部分相同,其实也......
  • AtCoder Beginner Contest 248 F(连通性状压dp)
    F连通性状压dp思路看了dls的讲解后才明白一点点。状态\(dp[i][j][k]\)表示到表示到i列,删除了j条边,点i和n-1+i是否联通,对于下一列点,若当前i和n-1+i连通,则多出来的三条......
  • ABC295 A~C题解
    A-ProbablyEnglish共有\(n\)个单词,如果出现过and,not,that,the,you其中一个单词至少一次,输出\(Yes\),否则,输出\(No\)。(输入的单词均为小写)按题意模拟即可:#include<......
  • AtCoder Educational DP Contest
    1.A没什么难度,直接算就可以了。点击查看代码#include<bits/stdc++.h>#defineintlonglong#defineYesprintf("Yes\n")#defineNoprintf("No\n")#defineYESpr......