Atcoder ABC 397

compaq · 2025-03-16 09:03:41 · 题解

C - Variety Split Easy

找一个断点，使得断点之前(含断点)的不同数字个数 + 断点之后(不含断点)不同数字个数 加起来最大。

set判重预处理处前缀不同个数和后缀不同个数，再枚举断点。时间复杂度O(n).

#include<bits/stdc++.h>
using namespace std;
const int N=300005;
int a[N], pre[N], suf[N];
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    set<int> st;
    for(int i = 1; i <= n; i++){
        st.insert(a[i]);
        pre[i] = st.size();
    }
    st.clear();
    for(int i = n; i >= 1; i--){
        st.insert(a[i]);
        suf[i] = st.size();
    }
    int res = 0;
    for(int i = 1;i <= n; i++)
        res=max(res, pre[i] + suf[i+1]);
    printf("%d\n", res);
    return 0;
}

D - Cubes

枚举第一个数i, 二分枚举增量mid，另外一个数即为i+mid, 比较(i+mid) ^ 3 - i^3与n的关系。

• 若比n大，则i太大，则右端点左移；
• 若比n小，则i太小，则左端点右移；

注意数据范围。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ll n;
    scanf("%lld", &n);
    for(ll i = 1; i <= 1000000; i++){
        ll l = 1, r = 1e12;
        while(l <= r){
            ll X = (l + r) >> 1;
            __int128 A = (__int128)X, B = A + i, P = B * B * B - A * A * A;
            if(P == n){
                printf("%lld %lld\n",X + i, X);
                return 0;
            }
            if(P < n) l = X + 1; 
            else r = X - 1;
        }
        //(x+i)^3-x^3=i(x^2+i^2+xi)
    }
    puts("-1");
    return 0;
}

E - Path Decomposition of a Tree

题意是求能否把整个树分成n个长度为k的链状结构。

维护一下当前节点为根的子树大小sz，

• 如果sz值为k的话可以分成一个链，相当于这个链被移除了,sz[u]设置为0，
• 但是要注意如果sz正好为k，儿子的数量不能超过2，如果超过2就不符合题意了（一定是链型的 不能是树形的）。
• 另外如果节点数量超过了k也没有分离的话说明也是不能符合要求的.

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,k,sz[N],cnt,son[N];
vector<int> e[N];
void dfs(int u, int fa){
    sz[u] = 1;
    for(int v: e[u]){
        if(v == fa)continue;
        dfs(v, u);
        sz[u] += sz[v];// u为跟的子树大小 
        if(sz[v]) son[u]++; // 子树v存在几个 
    }
    if(sz[u] == k) sz[u] = 0, cnt++;
    if(sz[u] > k || son[u] > 2 || son[u] == 2 && sz[u]){
        cout << "No" << endl;
        exit(0);
    }
}
int main(){
    cin >> n >> k;
    for(int i = 1; i < n * k; i++){
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, -1);
    if(cnt == n)cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}