Codeforces Round925 div3 (A - G)

· · 个人记录

A. Recovering a Small String

#include <iostream>

using namespace std ;

int main()
{
    ios::sync_with_stdio(false) ; 
    cin.tie(0) ;
    cout.tie(0) ;

    int t = 1 ;
    cin >> t ;
    while ( t-- ) {
        int n ;
        cin >> n ;
        n -= 3 ; 
        string s = "aaa" ;
        for(int i = 2 ; i >= 0 ; i--) {
            if ( !n ) break ;
            if ( n >= 25 ) n -= 25 , s[i] = 'z' ;
            else s[i] += n , n = 0 ;
        }
        cout << s << '\n' ;
    }

    return 0 ;
}

B. Make Equal

显然有解情况下最终都分配成平均数模拟走一遍即可

#include <iostream>

using namespace std ;

const int N = 2e5 + 10 ; 

using i64 = long long ; 

int a[N] ;

int main()
{
    ios::sync_with_stdio(false) ;
    cin.tie(0) ;
    cout.tie(0) ;

    int t = 1 ;
    cin >> t ;
    while (t--) {
        int n ;
        cin >> n;
        i64 sum = 0 ; 
        for(int i = 1 ; i <= n ; i++) {
            cin >> a[i] ;
            sum += a[i] ;
        }
        i64 veg = sum / n , pre = 0 ;
        bool flag = true ; 
        for(int i = 1 ; i <= n && flag ; i++) {
            if ( a[i] + pre <  veg ) flag = false ;
            if ( a[i] >= veg ) {
                pre += a[i] - veg ;
            }
            else {
                pre -= veg - a[i] ;
            }
        }
        cout << (flag ? "YES\n" : "NO\n") ;
    }
    return 0 ; 
}

C. Make Equal Again

显然操作次数小于等于1次情况下可知要么保留左端点的元素要么保留右端点模拟走俩次取min即可

#include <iostream>

using namespace std ;

const int N = 2e5 + 10 ;

int a[N] ; 

int main()
{
    ios::sync_with_stdio(false) ;
    cin.tie(0) ;
    cout.tie(0) ;

    int t = 1 ; 
    cin >> t ;
    while ( t-- ) 
    {
        int n ;
        cin >> n  ;
        for(int i = 1 ; i <= n ; i++ )
        {
            cin >> a[i] ; 
        }
        int l , r ; 
        for(l = 1 , r = n ; r >= l ; ) {
            if ( a[l] == a[1] ) ++ l ;
            if ( a[r] == a[1] ) -- r ;
            if ( a[l] != a[1] && a[r] != a[1] ) break ; 
        }
        int ret = max(0 , r - l + 1) ;
        for(l = 1 , r = n ; r >= l ; ) {
            if ( a[l] == a[n] ) ++ l ;
            if ( a[r] == a[n] ) -- r ;
            if ( a[l] != a[n] && a[r] != a[n] ) break ; 
        }
        cout << min(ret , max(0 , r - l + 1)) << '\n' ;
    } 
    return 0 ; 
}

D. Divisible Pairs

\because (a_i + a_j) | x \therefore (a_i \mod x + a_j \mod x) | x \because (a_i - a_j) | y \therefore a_i \equiv a_j \pmod y

用map<pair<int , int> , int> mp维护a\mod x ,a\mod y即可

#include <iostream>
#include <map>
#define int long long
using namespace std ;

typedef pair<int , int> PII ; 
const int N = 2e5 + 10 ;
int a[N] ; 

signed main()
{
    ios::sync_with_stdio(false) ; 
    cin.tie(0) ;
    cout.tie(0) ;

    int t = 1 ;
    cin >> t ;
    while (t--) {
        int n , x , y ;
        cin >> n >> x >> y ;
        map< PII , int > mp ; 
        for(int i = 1 ; i <= n ; i++) {
            cin >> a[i] ; 
            ++ mp[{a[i] % x , a[i] % y}] ;
        }
        int ret = 0 ;
        for(int i = 1 ; i <= n ; i++) {
            -- mp[{a[i] % x , a[i] % y}] ; 
            ret += mp[{ ((x - a[i] % x) % x + x) % x , (a[i] % y + y ) % y }] ;
        }
        cout << ret << '\n' ;
    }
    return 0 ; 
}

E. Anna and the Valentine's Day Gift

贪心考虑用priority_queue维护即可

/*
anna 最优选择是将目前的序列中数字尾0个数最多的数字翻转这样能在一次操作中消除的位数最优化
sasha 最优选择是阻止anna消除尽可能多的数位随便用一个数字与之拼接在一起目的是封住 0 这样能够尽可能保留位数
*/
#include <iostream>
#include <queue> 

using namespace std ;

const int N = 2e5 + 10 ; 

int main(){
    ios::sync_with_stdio(false) ; 
    cin.tie(0) ;
    cout.tie(0) ;

    int t = 1  ;
    cin >> t ;
    while (t--) {
        int n , m , a ;
        a = 0 ;
        cin >> n >> m ;
        priority_queue<int> que ; 
        for(int i = 1 ; i <= n ; i++) {
            int x ;
            cin >> x ;
            int num = 0 ; 
            bool flag = true ;
            while ( x ) 
            {
                int c = x % 10 ;
                x /= 10 ;
                if ( c ) flag = false ;
                if ( flag && !c ) ++num ; 
                else ++a; //一定能保留下来的位数
            }
            que.push(num) ; 
        }

        int step = 1 ;
        while ( !que.empty() ) {
            int s = que.top() ; que.pop() ;
            if ( !(step & 1) ) {
                a += s ; 
            }
            ++step ; 
        }

        cout << (a > m ? "Sasha\n" : "Anna\n") ;
    }   
    return 0 ;
}

F. Chat Screenshots

建图拓扑排序判环

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring> 

using namespace std ;

const int N = 2e5 + 10  ;

int e[N << 1] , ne[N << 1] , h[N] , idx , n , k ; 
int indegree[N] ; 

void init() {
    for(int i = 0 ; i <= n ; i++) h[i] = -1 , indegree[i] = 0 ; 
    idx = 0 ;
}
void add(int a,int b) {
    e[idx] = b , ne[idx] = h[a] , h[a] = idx++ ; 
}

bool topsort() {
    int tot = n ;

    queue<int> que ;
    for(int i = 1 ; i <= n ; i++) if ( !indegree[i] ) que.push(i)  ; 

    while ( !que.empty() ) {
        int x = que.front() ; que.pop() ; 
        -- tot ; 
        for( int i = h[x] ; i != -1 ; i = ne[i] ){
            int v = e[i] ;
            indegree[v]-- ;
            if ( !indegree[v] ) que.push(v) ; 
        }

    }
    return tot == 0 ; 
}

int main()
{
    ios::sync_with_stdio(false)  ;
    cin.tie(0) ;
    cout.tie(0) ;

    memset(h , -1 , sizeof h) ; 
    int t = 1  ;
    cin >> t ;
    while ( t-- ) {
        cin >> n >> k ;
        while (k--) {
            int pre ;
            cin >> pre ;
            if ( n > 1 ) cin >>  pre ;
            for(int i = 2 ; i < n ; i++) {
                int x ;
                cin >> x ;
                add(pre , x) ;
                indegree[x] ++ ; 
                pre = x ;
            }
        }

        cout << (topsort() ? "YES\n" : "NO\n") ;
        init() ; 
    }
    return 0 ; 
}

G. One-Dimensional Puzzle

#include <iostream>
#include <vector>
#define int long long

using namespace std ;

const int p = 998244353 ;

using i64 = long long ; 

const int N = 2e6 + 10 ;

int fact[N] , infact[N] ; 

int qpow(int a,int b) {
    int ret = 1 ;
    while ( b ) {
        if ( b & 1 ) ret = (i64) ret * a % p ;
        a = (i64) a * a % p ; 
        b >>= 1 ;
    }
    return ret;
}

int inv(int x) {
    return qpow(x , p - 2) ;
}

i64 C(int n,int m) {
    return (i64)fact[n] * infact[m] % p * infact[n - m] % p ;
}

signed main()
{
    ios::sync_with_stdio(false) ;
    cin.tie(0) ;
    cout.tie(0) ;

    fact[0] = infact[0] = 1 ;
    for(int i = 1 ; i < N ; i++) {
        fact[i] = (i64) fact[i - 1] * i % p ;
        infact[i] = (i64) infact[i - 1] * inv(i) % p ; 
    }

    int t = 1 ;
    cin >> t ;
    while (t--) {
        int a , b , c ,d ;
        cin >> a >> b >> c >> d ;
        int sum = a + b + c + d ;

        if ( c == sum || d == sum ) {
            cout << 1 << '\n' ;
        }
        else if ( a == sum || b == sum ) {
            cout << ( a == 1 || b == 1  ? 1 : 0) << '\n' ;
        } 
        else if ( abs(a - b) > 1 ) {
            cout << 0 << '\n' ;
        }
        else if ( a == b ){
            if (!a) cout << (c && d ? "0\n" : "1\n"); 
            else cout << (C(c + a, a) * C(d + a - 1, a - 1) + C(c + a - 1, a - 1) * C(d + a, a)) % p << '\n' ; 

        }else if (a == b + 1) cout << C(c + a - 1, a - 1) * C(d + a - 1, a - 1) % p << '\n' ; 
        else  cout << C(c + a, a) * C(d + a, a) % p << '\n' ;
    }
    return 0 ; 
}