官方题解 | 挑战赛#25 题解

NoonMaple

2025-12-01 00:16:22

发布于：浙江

92阅读

0回复

0点赞

挑战赛25题解

本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目标题	难度
T1	小枫的大写字母	入门
T2	小枫的机器人	普及-
T3	小枫的平方数	普及-
T4	小枫的mex	普及/提高-
T5	道路修建	普及/提高-
T6	最小路径价值	普及+/提高

T1 小枫的大写字母

题目大意

输出字符串中唯一一个大写字母所在位置。

解题思路

遍历字符串，找到大写字母，输出对应位置即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

int main(){
    string s;cin>>s;
    s=' '+s;
    for(int i=1;i<s.size();i++){
        if(s[i]>='A' && s[i]<='Z'){
            cout<<i<<endl;
        }
    }
    return 0;
}

T2 小枫的机器人

题目大意

判断通过题目给出的行走路线，是否会经过重复的位置。

解题思路

考虑记录所有走过的位置，如果某个位置经历过两次及以上，则输出 Yes 。

但显然无法用二维数组直接记录，那么考虑使用 map<pair<int,int>,bool> ，其中 pair<int,int> 用于存放二维坐标 $(x,y)$ 。当移动到坐标 $(x,y)$ 发现 map 中已经记录过此位置，则输出 Yes 。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

int main(){
    int n;cin>>n;
    string s;cin>>s;
    int x=0,y=0;
    map<pair<int,int>,bool>mp;
    mp[{0,0}]=true;
    for(auto ch:s){
        if(ch=='R') y++;
        if(ch=='L') y--;
        if(ch=='U') x--;
        if(ch=='D') x++;

        if(mp.count({x,y})){
            cout<<"Yes"<<endl;
            return 0;
        }
        mp[{x,y}]=true;
    }
    cout<<"No"<<endl;
    return 0;
}

T3 小枫的平方数

题目大意

给定一个只包含数字的字符串，找出这个字符串重新排列组合后，能组成多少种不同的平方数。

解题思路

一个 $13$ 位数字，最大为 $9999999999999$ ，打表发现 $10^{14}$ 以内的平方数有 $3162278$ 个。

所以我们可以先预处理出 $10^{14}$ 以内所有的平方数，再对这些平方数逐一检查是否可以被给定字符串组成。

在检查时，我们只需要判断 $1$ ~ $9$ 的数字个数是否完全相等，并且给定字符串 $0$ 的个数要大于等于平方数的 $0$ 的个数。

参考答案

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 1e9+10;
const int N = 1000010;

vector<ll>st;

void init(){
    for(ll i=0;i*i<=10000000000000;i++){
        st.push_back(i*i);
    }
}

int cnt[10];
int cnt2[10];

int main(){
    init();
    int n;cin>>n;
    string s;cin>>s;
    for(auto c:s){
        ll x=c-'0';
        cnt[x]++;
    }

    ll res=0;
    for(auto c:st){
        for(int i=0;i<10;i++) cnt2[i]=0;

        ll x=c;
        if(x==0) cnt2[0]++;
        while(x){
            cnt2[x%10]++;
            x/=10;
        }
        
        if(cnt[0]<cnt2[0]) continue;

        int flag=0;
        for(int i=1;i<10;i++){
            if(cnt[i]!=cnt2[i]){
                flag=1;
                break;
            }
        }
        if(!flag) res++;
    }
    cout<<res<<endl;
    return 0;
}

T4 小枫的mex

题目大意

给定一个序列，进行 $q$ 次操作，每次操作后输出操作后的序列的 $mex$ 。

解题思路

首先，很显然的是，无论进行怎样的操作，一个序列的 $mex$ 一定不会超过 $n$ 。

所以只需要记录和处理小于等于 $n$ 的元素即可，这个过程可以通过桶数组 cnt 和 set 完成，其中桶数组用于记录当前序列中小于 $n$ 的各个元素的个数，set 记录当前这个序列还没有出现过的数，即满足 cnt[i]=0 的数字 $i$ 。最终答案即为 set 中第一个数，输出 *s.begin() 即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;

int n,q;
int a[N];
int cnt[N];
set<int>ust;

int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
		if(a[i]<=n) cnt[a[i]]++;
    }
    for(int i=0;i<=n;i++){
        if(!cnt[i]){
            ust.insert(i);
        }
    }
    while(q--){ 
        int pos,x;cin>>pos>>x;
        if(a[pos]<=n) {
            cnt[a[pos]]--;
            if(cnt[a[pos]]==0) ust.insert(a[pos]);
        }
        a[pos]=x;
        if(a[pos]<=n) {
            if(cnt[a[pos]]==0) ust.erase(a[pos]);
            cnt[a[pos]]++;
        }
        cout<<*ust.begin()<<endl;
    }
    return 0;
}

T5 道路修建

题目大意

有 $n$ 个点， $m$ 条边的无向图，如果点 $a$ 和点 $b$ 有一条边，点 $a$ 和点 $c$ 有一条边，而点 $b$ 和点 $c$ 之间没有边，则可以在点 $b$ 和点 $c$ 之间添加一条边，求最多可以添加多少条边。

解题思路

不难发现，在一个连通块内的所有点都可以通过若干次操作使得每两个点之间连上一条边。于是，我们求出每个连通块的大小 $sz$ 和已有边数 $edgs$ ，就可以求出连通块内没有连接的边数 $\frac{sz\times(sz-1)}{2} - edgs$ ，也就是答案。

可以用并查集维护 $sz$ 以及 $edgs$ 。

时间复杂度 $O(nlogn)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define all(x) x.begin(),x.end()
#define SUM(x) accumulate(all(x),0ll)
const int INF = 1e18+10;
const int N = 200010, M = 1000010;
const int mod = 998244353;
bool rcmp(int a,int b){return a>b;}

struct DSU{
	vector<int>p,sz,edg;
	DSU(){}
	DSU(int n){
		init(n);
	}
	void init(int n){
		p.resize(n+1);
		sz.resize(n+1);
		edg.resize(n+1);
		for(int i=1;i<=n;i++){
			p[i]=i;
			sz[i]=1;
		}
	}

	int find(int x){
		if(p[x]!=x) p[x]=find(p[x]);
		return p[x];
	}

	void merge(int x,int y){
		x=find(x);
		y=find(y);
		if(x>y) swap(x,y);
		edg[x]++;
		if(x==y) return;
		
		p[y]=x;
		sz[x]+=sz[y];
		edg[x]+=edg[y];
	}

	bool same(int x,int y){
		return find(x)==find(y);
	}
};

void solve(){
	int n,m;cin>>n>>m;
	DSU dsu(n);
	for(int i=1;i<=m;i++){
		int a,b;cin>>a>>b;
		dsu.merge(a,b);
	}

	int res=0;
	for(int i=1;i<=n;i++){
		if(dsu.p[i]==i){
			int num=dsu.sz[i];
			int e=dsu.edg[i];
			res+=num*(num-1)/2-e;
		}
	}
	cout<<res<<endl;
}

signed main(){
	//init();//Prime();
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T=1;//cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
//9223372036854775808

T6 最小路径价值

题目大意

有一颗 $n$ 个结点的树，定义一个结点的路径价值为 $f(x) = \sum_{i=1}^{n} (w_i \times d(x, i))$ ，求整棵树的最小路径价值。

解题思路

考虑计算所有结点的路径价值，取最小值即可得到答案。

以上实现方法很容易想到换根DP，设 $sum_i$ 表示子树 $i$ 的权值和，即

$sum_i = \sum_{j=subtree_i} (w_j)$

并记录以 $1$ 为根节点的路径价值 $f(1)$ 。

接下来考虑换根，假设当前结点为 $u$ ，父结点为 $fa$ ，那么 $f(u)=f(fa)+sum_1-2\times sum_u$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 200010;

ll n;
vector<ll>v[N];
ll c[N];
ll sum[N];
ll tot;
ll ans;

ll dfs(ll u,ll fa,ll dep){
    sum[u]=c[u];
    tot+=c[u]*dep;
    for(auto x:v[u]){
        if(x==fa) continue;
        sum[u]+=dfs(x,u,dep+1);
    }
    return sum[u];
}

void dfs1(ll u,ll fa,ll now){
    ans=min(ans,now);
    for(auto x:v[u]){
        if(x==fa) continue;

        ll res=now+sum[1]-2*sum[x];
        dfs1(x,u,res);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=n;i++) cin>>c[i];

    dfs(1,-1,0);

    ans=tot;
    dfs1(1,-1,tot);
    cout<<ans<<endl;
    return 0;
}