Atcoder ABC 397

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

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

CPP

#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$ 太小，则左端点右移；

注意数据范围。

CPP

#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也没有分离的话说明也是不能符合要求的.

CPP

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

文章操作

相关推荐

评论

Atcoder ABC 397