牛客周赛Round 67 个人题解(A~F)

牛客周赛 Round 67

A-排序危机

题目分析

• 相对位置不会改变，用三个·字符串模拟即可

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void solve(){
	int n;cin>>n;
	string s;cin>>s;
	s=" "+s;
	string s1,s2,s3;
	for(int i=1;i<=n;i++){
		if(s[i]>='a' && s[i]<='z') s1+=s[i];
		if(s[i]>='0' && s[i]<='9') s2+=s[i];
		if(s[i]>='A' && s[i]<='Z') s3+=s[i];
	}
	cout<<s1<<s2<<s3<<endl;
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T=1;
	while(T--) solve();
	return 0;
}

B-小歪商店故事：卷

题目分析

• 式子变化一下a<b*c/d,注意处理一下整数和小数的区别

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int ans[N];
void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		int a,b,c,d;cin>>a>>b>>c>>d;
		int t=(b*c)/d;
		if(t*d<b*c) ans[i]=a-t;
		else ans[i]=a-t+1;
  	 }
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T=1;
	while(T--) solve();
	return 0;
}

C-小苯的计算式_牛客周赛 Round 67

题目分析

• 暴力，因为A+B=C,len(A)+len(B)+len(C)+2=n,枚举A即可算B，然后判断满不满足题目条件即可
• 一个小trick,计算一个数字的位数可以用log₁₀(x)+1快速求出

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
void solve(){
	int n,c;cin>>n>>c;
	int len=log10(c)+1;
	n=n-len-2;
	int ans=0;
	for(int a=0;a<=c;a++){
		int b=c-a;
		int lena=a?log10(a)+1:1;
		int lenb=b?log10(b)+1:1;
		if(lena+lenb!=n) continue;
		ans++;
	}
	cout<<ans<<endl;
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T=1;
	while(T--) solve();
	return 0;
}

D-K_牛客周赛 Round 67

题目分析

• 构造题目，首先容易发现当k的最大值只能为n，即所有数都相同，所以当k>n时无解
• 考虑构造k<n,可以用交替的01串构造，如k=5,n=8,只需01010111

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=2e5+10;
int a[N];
void solve(){
	int n,k;cin>>n>>k;
	if(k>n){
		cout<<"NO"<<endl;
		return;
	}
	cout<<"YES"<<endl;
	if(k==n){
		for(int i=1;i<=n;i++) cout<<0<<" ";
		cout<<endl;
		return;
	}
	for(int i=1;i<=k+1;i++){
		if(i&1) a[i]=0;
		else a[i]=1;
	}
	for(int i=k+2;i<=n;i++) a[i]=a[i-1];
	for(int i=1;i<=n;i++) cout<<a[i]<<" ";
	cout<<endl;
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T=1;
	while(T--) solve();
	return 0;
}

E-小苯的区间选数_牛客周赛 Round 67

题目分析

• 首先题目可以转化为求[l,r]区间取一个数的最大数位和，一道很经典的问题
• 考虑性质，将l和r每一位都分解开，若两数数字个数相同，则有当a[i]<b[i]时，若对于b来说i之后的位置不全为9，则可以让b[i]-1.后面全都取9，这样一定能满足该数属于[l,r]且数位和不劣于原数(思考一下，因为这一位-1，后面的所有数不全为9的话一定能补上这个减掉的1)
• 知道这个性质后就可以枚举数位了，为了防止特判，我们可以将两数数字个数不同转化成相同情况，即給l赋值00000

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
void solve(){
	int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;
	int l=l1+l2,r=r1+r2;
	string sl=to_string(l);
	string sr=to_string(r);
	int lenl=sl.size(),lenr=sr.size();
	int ans=0,res=0;
	if(lenl!=lenr){
		sl.assign(lenr,'0');
	} 
	for(int i=0;i<lenr;i++){
		if(sl[i]<sr[i]){
			int tmp=(lenr-i-1)*9+(sr[i]-'0'-1)+res;
			ans=max(ans,tmp);
		}
		res+=sr[i]-'0';
	}
	ans=max(ans,res);
	cout<<ans<<endl;
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}

F-小Z的树迁移_牛客周赛 Round 67

解题思路

• 树上k-son问题，这里给出dfs序的做法
• 其实我们需要维护的是对于点u如何快速找到指定层数的点，并求出最大的权值和，首先目标点的层数应该为dep[u]+d
• 考虑怎么维护子树信息，这里运用到dfs序的方法，我们记录访问一个点的时间为st[i],离开的时间为ed[i]，容易发现一个性质，若v在u的子树中那么一定有st[u]<=st[v]<=ed[v]<=ed[u],那么我们可以去预处理每一个点的dfs序，接下来对每一层的点存下对应点的dfs序并排序
• 然后对于给定点u，我们找到需要到的对应层数，我们要找这一层上在u子树中的点，怎么做呢？我们可以对这一层记录的点的dfs序二分，二分边界即为上一点的条件，这样既可以log时间内找到区间
• 找到区间之后，我们要做的就是在这个区间内选一个点，使得点u到该点的权值和最大，假设选择的点为v,u的父亲为fa,则权值和为sum[v]-sum[fa],由于u是固定点，所以等价于我们在该区间内选择一个点x,使得sum[x]最大，典型的RMQ问题，这里可以用st表快速维护
• 具体细节可以看代码的实现

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
struct node{
	int to,w;
};
vector<node> g[N];
int st[N],ed[N],dep[N],sum[N],f[N][20];
int p[N],cnt[N],t[N];//cnt存每一层点个数的前缀和
int n,tot=0;
bool cmp(int x,int y){
	if(dep[x]==dep[y]) return st[x]<st[y];
	return dep[x]<dep[y];
}
//求dfs序，并维护sum与dep数组
void dfs(int u,int fa){
	st[u]=++tot;
	for(auto [v,w]:g[u]){
		if(v==fa) continue;
		dep[v]=dep[u]+1;
		sum[v]=sum[u]+w;
		dfs(v,u);
	}
	ed[u]=tot;
}
void init(){
	for(int j=1;j<19;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1], f[i+(1<<(j-1))][j-1]);
        }
    }
}
int query(int l,int r){
	int k=log2(r-l+1);
	return max(f[l][k],f[r-(1<<k)+1][k]);
}
void test(){
	for(int i=1;i<=n;i++) cout<<p[i]<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++) cout<<cnt[i]<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++) cout<<st[i]<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++) cout<<t[i]<<" ";
	cout<<endl;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int u,v,w;cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	dfs(1,0);
	for(int i=1;i<=n;i++) p[i]=i;
	sort(p+1,p+n+1,cmp);
	
	for(int i=1;i<=n;i++){
		int t=dep[p[i]];
		cnt[t]=i;
		f[i][0]=sum[p[i]];
	}
	init();
	for(int i=1;i<=n;i++) t[i]=st[p[i]];
//	test();	
	int q;cin>>q;
	while(q--){
		int u,d;cin>>u>>d;
		int tmp=dep[u]+d;
		int l=lower_bound(t+cnt[tmp-1]+1,t+cnt[tmp]+1,st[u])-t;
        int r=upper_bound(t+cnt[tmp-1]+1,t+cnt[tmp]+1,ed[u])-t;
        if(!cnt[tmp] || r<=l){
        	cout<<-1<<endl;
        }
        else{
        	int ans=query(l,r-1)-sum[u];
        	cout<<ans<<endl;
        }
	}
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T=1;
	while(T--) solve();
	return 0;
}