526互联

Codeforces Round 874 (Div. 3)

发布时间 2023-05-29 18:00:13作者: PHarr

A. Musical Puzzle

#include <bits/stdc++.h>

using namespace std;

void solve(){
    int n;
    string s;
    cin >> n >> s;
    set<string> cnt;
    for( int i = 0 ; i + 1 < n ; i ++ )
        cnt.insert( s.substr( i , 2 ) );
    cout << cnt.size() << "\n";
    return ;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while( t -- )
        solve();
    return 0;
}

B. Restore the Weather

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


void solve() {
    int n = read(), k = read();
    vector<pair<int, int>> a(n);
    vector<int> b(n), c(n);
    for (int i = 0; i < n; i++)
        a[i].first = read(), a[i].second = i;
    for (auto &i: b) i = read();



    sort(a.begin(), a.end()), sort(b.begin(), b.end());
    for( int i = 0 ; i < n ; i ++ ) c[ a[i].second ] = b[i];
    for( auto i : c )
        printf("%d " , i );
    printf("\n");
    return;
}

int32_t main() {
    for (int t = read(); t; t--)
        solve();
    return 0;
}

C. Vlad Building Beautiful Array

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


void solve() {
    int n = read();
    vector<int> a(n);
    int b = INT_MAX , c = INT_MAX;
    for( auto & i : a ) {
        i = read();
        if( i & 1 ) b = min( b , i );
        else c = min( c , i );
    }
    if( b == INT_MAX || c == INT_MAX ){
        cout << "YES\n";
        return ;
    }
    int f = 1;
    for( const auto & i : a ){
        if( i&1 ) continue;
        if( b < i ) continue;
        f = 0;
        break;
    }
    if( f ) cout << "YES\n";
    else cout << "NO\n";
        return;
}

int32_t main() {
    for (int t = read(); t; t--)
        solve();
    return 0;
}

D. Flipper

因为要必须翻转一次，所以为了字典序最大，所以一定要把最大值翻到前面，所以右端点一定是\(n\)，但是当\(n\)在第一个位置上是，因为必须翻转，所以有段点的值就是\(n-1\)

当确定右端点后，可以直接枚举左端点的位置，然后暴力翻转，因为\(n\)很小所以复杂度可以接受。

这里学到的一个新的函数std::rotate环移函数，

std::rotate(iterator begin, iterator middle, iterator end);

作用是把序列中begin和end连起来，然后再从middle处断开，middle作为新的begin

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


void solve() {
    int n = read();
    vector<int> a(n);
    for( auto & i : a ) i = read();
    vector res( a.rbegin(), a.rend());
    int r = find( a.begin(), a.end() , n ) - a.begin();
    if( r == 0 && n > 1 ) r = find( a.begin(),a.end() , n-1 ) - a.begin();
    for( int i = 0 ; i < n ; i ++ ){
        auto b = a;
        reverse(b.begin()+i , b.end() );
        rotate( b.begin() , b.begin()+i ,b.end() );
        res = max( res , b );
    }
    for( int i = 0 ; i < r ; i ++ ){
        auto b = a ;
        reverse( b.begin()+i , b.begin() + r );
        rotate( b.begin() , b.begin()+i , b.end() );
        rotate( b.begin() , b.begin()+r-i , b.end() - i );
        res = max( res , b) ;
    }
    for( auto i : res )
        printf("%d " , i );
    printf("\n");

    return;
}

int32_t main() {
    for (int t = read(); t; t--)
        solve();
    return 0;
}
 

E. Round Dance

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


vector<vector<int>> e;
vector<int> vis;

void dfs(int u, int fa) {
    if (vis[u] == 1) {
        vis[u] = 2;
        return;
    }
    vis[u] = 1;
    for (auto v: e[u]) {
        if (v == fa) continue;
        dfs(v, u);
    }
    return;
}

void solve() {
    int n = read();
    e = vector<vector<int>>(n + 1);
    vis = vector<int>(n + 1, 0);
    int a = 0, b = 0;
    for (int i = 1, x; i <= n; i++)
        x = read(), e[i].push_back(x), e[x].push_back(i);
    for (auto &i: e)
        sort(i.begin(), i.end()), i.resize(unique(i.begin(), i.end()) - i.begin());
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        dfs(i, -1);
        if (vis[i] == 1) a++;
        else b++;
    }
    printf("%d %d\n", (b + (a > 0)), a + b);
    return;
}

int32_t main() {
    for (int t = read(); t; t--)
        solve();
    return 0;
}

F. Ira and Flamenco

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

const int mod = 1e9 + 7;

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

void solve() {
//    printf("\n\n\n");
    int n = read(), m = read();
    map<int, int> cnt;
    vector<int> a, b;
    for (int i = 1, x; i <= n; i++) x = read(), cnt[x]++;
    for (auto [k, v]: cnt) a.push_back(k), b.push_back(v);
    int res = 0, ans = 1;
    for (int i = 0; i < m-1 && i < a.size(); i++)
        ans = ans * b[i] % mod;
    for (int i = m - 1; i < a.size(); i++) {
        ans = ans * b[i] % mod;
        if (a[i] - a[i - m + 1] == m-1) res = (res + ans) % mod;
        ans = ans * inv(b[i - m+1]) % mod;
    }
    printf("%lld\n", res);
    return;
}

int32_t main() {
    for (int t = read(); t; t--)
        solve();
    return 0;
}

G. Ksyusha and Chinchilla

在 dfs的过程中，每次发现子树大小等于3 时就把与这条子树相连的边删掉。

#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef pair<int, int> edge;

vector<vector<edge>> e;
vector<int> sz , res;

bool dfs( int x , int fa ){
    sz[x] = 1;
    for( auto [y,i] : e[x] ){
        if( y == fa ) continue;
        if( !dfs( y , x ) ) return false;
        if( sz[y] == 3 ) res.push_back(i);
        else sz[x] += sz[y];
    }
    return sz[x] <= 3;
}

void solve() {
    int n;
    cin >> n;
    e = vector<vector<edge>>(n + 1);
    sz = vector<int>(n + 1 , 0);
    res = vector<int>();
    for (int i = 1, x, y; i < n; i++)
        cin >> x >> y, e[x].emplace_back(y, i), e[y].emplace_back(x, i);

    if( n % 3 || !dfs( 1 , -1 ) || sz[1] != 3 ) {
        cout << "-1\n";
        return;
    }
    cout << res.size() << "\n";
    for( auto i : res ) cout << i << " ";
    cout << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    for (; t; t--)
        solve();
    return 0;
}