526互联

AtCoder Beginner Contest 245

发布时间 2023-03-29 22:37:13作者: PHarr

A - Good morning

#include <bits/stdc++.h>

using namespace std;


int32_t main() {
    int a , b , c , d;
    int ta , ao;
    cin >> a >> b >> c >> d;
    ta = a * 60 * 60 + b * 60;
    ao = c * 60 * 60 + d * 60 + 1 ;
    if( ta < ao ) printf("Takahashi\n");
    else printf("Aoki\n");
    return 0;
}

B - Mex

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

int32_t main() {
    int n = read();
    vector<int> a(2005);
    for( int x ; n ; n -- ) x = read() , a[x] ++;
    for( int i = 0 ; i <= 2001 ; i ++ )
        if( a[i] == 0 ) return cout << i , 0;
    return 0;
}

C - Choose Elements

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

int32_t main() {
    int n = read(), k = read();
    vector<int> a(n), b(n);
    for (int &i: a) i = read();
    for (int &i: b) i = read();
    vector<array<int, 2> > f(n);
    f[0][1] = f[0][0] = 1;
    for (int i = 1; i < n; i++) {
        if( f[i-1][1] + f[i-1][0] == 0 ) break;
        if (f[i - 1][0]) {
            if (abs(a[i] - a[i - 1]) <= k) f[i][0] = 1;
            if (abs(b[i] - a[i - 1]) <= k) f[i][1] = 1;
        }
        if (f[i - 1][1]) {
            if (abs(a[i] - b[i - 1]) <= k) f[i][0] = 1;
            if (abs(b[i] - b[i - 1]) <= k) f[i][1] = 1;
        }
    }
    if( f[n-1][0] || f[n-1][1] ) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

D - Polynomial division

多项式除法，列一个数式，手模一下就有了

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

#define mp make_pair

int32_t main() {
    int n = read(), m = read();
    vector<int> a(n + 1), b(m + 1), c(n + m + 1);
    for (auto &i: a) i = read();
    for (auto &i: c) i = read();
    for( int i = m ; i >= 0 ; i -- ){
        b[i] = c[i+n] / a[n];
        for( int j = 0 ; j < n ; j ++ )
            c[i+j] -= b[i] * a[j];
    }
    for( int i = 0 ; i <= m ; i ++ )
        printf("%d " , b[i] );
    return 0;
}

E - Wrapping Chocolate

把盒子和巧克力豆按照宽度从大到小排序，然后开始枚举巧克力，首先把所有宽度大于当前巧克力的盒子的长度都加入到set中，然后把大于等当前巧克力长度的最小盒子删掉，如果删不掉就输出No

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

int32_t main() {
    int n = read(), m = read();
    vector<pair<int, int>> a(n), b(m);
    for (int i = 0; i < n; i++) a[i].first = read();
    for (int i = 0; i < n; i++) a[i].second = read();
    for (int i = 0; i < m; i++) b[i].first = read();
    for (int i = 0; i < m; i++) b[i].second = read();
    sort(a.begin(), a.end(), greater<pair<int, int>>());
    sort(b.begin(), b.end(), greater<pair<int, int>>());
    multiset<int> st;
    for( int i = 0 , j = 0 ; i < n ; i ++ ){
        while( j < m && a[i].first <= b[j].first ) st.insert(b[j].second) , j ++;
        if( st.empty() ) return cout << "No" , 0;
        auto it = st.lower_bound(a[i].second);
        if( it == st.end() ) return cout << "No" , 0;
        st.erase(it);
    }
    cout << "Yes";
    return 0;
}

F - Endless Walk

实际上就是问有多少个点可以走到环上，首先出度为 0 的点，一定走不到环上，其次是只能走到这些出度为 0 的点也是不行的。这个过程和拓扑排序很接近，所以做法就是反向建边，然后跑一遍拓扑排序，没有删掉的点就是答案。

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

int32_t main() {
    int n = read(), m = read() , res = n;
    vector<vector<int> > e(n + 1);
    vector<int> deg(n+1);
    for( int u , v ; m ; m -- ){
        u = read() , v = read() , deg[u] ++ , e[v].push_back(u);
    }
    queue<int> q;
    for( int i = 1 ; i <= n ; i ++ )
        if( deg[i] == 0 ) q.push(i);

    while( !q.empty() ){
        auto u = q.front(); q.pop();
        res --;
        for( auto v : e[u] ){
            deg[v] --;
            if( deg[v] == 0 ) q.push(v);
        }
    }
    cout << res << "\n";
    return 0;
}

G - Foreign Friends

其实最简单的想法肯定是按照颜色分类，然后跑最短路，然后统计答案。

答案最短路次短路还是太难了，抄了抄 dls 的做法。

做法就是按照二进制位吧颜色进行分类，然后跑多远最短路，更新二进制位不同的点的答案。按照二进制位分类的话最多只有 30 多种情况，很快就跑完了。

#include<bits/stdc++.h>

using namespace std;

#define int long long

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(), m = read(), k = read(), l = read();
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) a[i] = read();
    vector<int> b(l + 1);
    for (int i = 1; i <= l; i++) b[i] = read();
    vector<vector<pair<int, int> > > e(n + 1);
    vector<int> res(n + 1, LLONG_MAX);
    for (int u, v, w; m; m--) {
        u = read(), v = read(), w = read();
        e[u].emplace_back(v, w), e[v].emplace_back(u, w);
    }
    for (int bit = 0; bit <= ceil(log2(k)); bit++) {
        for (int t = 0; t < 2; t++) {
            vector<int> dis(n + 1, LLONG_MAX);
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
            vector<bool> vis(n+1 , false);
            for (auto i: b)
                if (((a[i] >> bit) & 1) == t)
                    dis[i] = 0, q.emplace(0, i);
            while (!q.empty()) {
                auto [d, u] = q.top();
                q.pop();
                if( vis[u] ) continue;
                vis[u] = true;
                for( auto [ v , w ] : e[u] ){
                    if( dis[v] > d + w ) dis[v] = d + w , q.emplace( dis[v] , v );
                }
            }
            for( int i = 1 ; i <= n ; i ++ ){
                if( ((a[i]>>bit)&1) == 1-t)
                    res[i] = min( res[i] , dis[i] );
            }
        }
    }
    for( int i = 1 ; i <= n ; i ++ )
        printf("%lld " , (res[i] == LLONG_MAX ? -1 : res[i]) );
    return 0;
}