牛客周赛67文字版题解
写在前面
又写篇题解吧~
这场的题整体来说非常友好，也非常适合相关算法的练习，很适合补完。
如果哪题遇到解决不了的问题，或者有什么好的建议给到牛牛，欢迎留言评论区，我们会尽快给出答复。
A.排序危机
知识点: 基础语法
只需要按顺序遍历给定的字符串，然后分别把小写字母，大写字母，数字存储在三个不同的字符串，按照顺序输出即可。
void solve(){
int n;
cin>>n;
string s;
cin>>s;
string a,A,num;
for(auto t:s){
if(t>='a'&&t<='z') a+=t;
else if(t>='A'&&t<='Z') A+=t;
else num+=t;
}
cout<<a<<num<<A;
}
B.小歪商店故事：卷
知识点: 数学思维
直接比较每个物品的价格 和
的大小。
直接除可能产生精度误差，所以我们采用交叉相乘，然后找到 使得
，即
，然后初始时若两个价格相等，则算完还是相同，故需要
。
void solve(){
int _;
cin>>_;
for(int __=1;__<=_;__++){
i64 a,b,c,d;
cin>>a>>b>>c>>d;
i64 newa=c*b/d;
if(newa*d>=b*c) newa--;
cout<<a-newa<<" ";
}
}
C.小苯的计算式
知识点: 数学思维
由于两个非负数 相加要等与
，必然满足
且
，枚举其实中
，然后通过减法求
，看总的数位之和是否相等
，满足时答案
。
其中数位计算可以采用 ，特判
，防止产生数学上的错误。
void solve(){
int n,C;
cin>>n>>C;
int n1=2+(int)log10(C)+1;
i64 ans=0;
for(int a=0;a<=C;a++){
int wa;
if(a==0) wa=1;
else wa=(int)log10(a)+1;
int b=C-a;
int wb;
if(b==0) wb=1;
else wb=(int)log10(b)+1;
if(wa+wb+n1==n) ans++;
}
cout<<ans<<"\n";
}
D.K
知识点: 构造 数学思维
我们可以考虑 相间的构造法。
这样满足极大不同区间长度为 ，最多可构造
个区间。
当所有数都为相同时，可构造 个区间。
所以可得 时都有解，否则无解。
故我们先构造 个极大不同区间，可以先考虑
，
那么即满足
，这样便是
个，故需要
个数。为防止增长极大不同区间长度，后
个数与
这个位置相同的即可。
void solve(){
int n,k;
cin>>n>>k;
if(k>n){
cout<<"NO";
return ;
}
cout<<"YES\n";
if(k==n){
for(int i=1;i<=n;i++) cout<<1<<" ";
return ;
}
for(int i=1;i<=k+1;i++){
cout<<(i&1)<<" ";
}
for(int i=k+2;i<=n;i++){
cout<<((k+1)&1)<<" ";
}
}
E.小苯的区间选数
知识点: 数位dp 数学思维(如果采用直接枚举，而不是题解中的做法)
验题的时候写了全错的然后
了，两天后的一个早晨突然悟到，也就有了现在的数据。
又是数位
，但是也可以不用，
选手写题已经习惯火箭式起飞。
跟周赛
的做法完全一样，可以发现代码细节都没啥变，就是多了个上下界。
题目等价于求 的最大数位和。
:表示枚举到第
位，前面数字总和为
可得的数位最大和。
由于两个数字长度可能不一，所以将 加上前导
即可。
int dp[20][200];
int cul(string l,string r,int w,bool u,bool d,bool ld0,int sum){
if(w==l.size()) return sum;
if(!u&&!d&&!ld0&&dp[w][sum]!=-1) return dp[w][sum];
int up=u?r[w]-'0':9;
int down=d?l[w]-'0':0;
int ans=0;
for(int i=down;i<=up;i++){
int temp=cul(l,r,w+1,u&&(i==r[w]-'0'),d&&(i==l[w]-'0'),ld0&&(i==0),(ld0&&i==0)?0:(sum+i));
ans=max(ans,temp);
}
if(!u&&!d&&!ld0){
dp[w][sum]=ans;
}
return ans;
}
int get(i64 l,i64 r){
string sl=to_string(l);
string sr=to_string(r);
string t="";
while(t.size()+sl.size()<sr.size()) t+='0';
t+=sl;
sl=t;
memset(dp,-1,sizeof dp);
return cul(sl,sr,0,1,1,1,0);
}
void solve(){
int t;
cin>>t;
while(t--){
i64 l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
cout<<get(l1+l2,r1+r2)<<"\n";
}
}
F.小Z的树迁移
知识点: 前缀和 dfs序 RMQ
刚写的时候多枚举了跳的步数的
，导致被卡的
叫。
如果所示，当我们考虑这样的一棵树
当我们查询 时应该如何做?
第一步:不难想到 向下走
步必然位于
的结点上。
当
或者没有结点存在于
必然是无解。
第二步，对于 如果存在点，那么必然也是其子树下的点才是可以到达的点，例如:
，那么
，其结点集合为
，根据图可以观察到其实只有
才是满足条件的点，那这些点是如何算出来的，我们考虑树的遍历顺序，即
序，如图所示(红色字迹)为每个结点的
序。
不难观察到对于结点 可到达的点的
序为
。那么我们就可以把每个点存在对应的深度容器里，然后根据
序从小到大排序，这样对于一个点可到达的点便是一一段连续的区间，如果不存在其
序范围内的也是无解。
第三步: 如果维护这些结点的最大值呢？ 我们预处理每个点到达根节点路径的最大值，然后这样在每个对应深度的容器里维护这些的最大值。
当然，当询问的点不是根节点时，必然存在多余的路径，例如 ，我们查询到了
这三个结点到达根节点路径的最大值，但是显然多了结点
~ 结点
这段路径的权值，所以还要扣掉这段的权值。
由于空间不定，所以数组不能开，考虑动态容器 。
时间复杂度 。
#include<bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include<bits/Bingbong.h>
#endif
using namespace std;
#define i64 long long
#define pII pair<int,int>
const int N=1e5+1;
int dep[N],dfn[N],ls[N],rs[N];
i64 val[N];
void solve(){
int n;
cin>>n;
vector<vector<pII>>e(n+1);
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
vector<vector<int>>dpo(n+1);// 存位于第i层的结点
int cnt=0;
dep[1]=1;
auto dfs1=[&](auto &&self,int u,int fa)->void {
dfn[u]=++cnt;
ls[u]=cnt;
for(auto v:e[u]){
if(v.first==fa) continue;
dep[v.first]=dep[u]+1;
dpo[dep[v.first]].push_back(v.first);
val[v.first]=val[u]+v.second;
self(self,v.first,u);
}
rs[u]=cnt;
return ;
};
auto camp=[&](int i,int j)->bool {
return dfn[i]<dfn[j];
};
dfs1(dfs1,1,-1);
for(int i=1;i<=n;i++){
sort(dpo[i].begin(),dpo[i].end(),camp);
}
vector<vector<vector<i64>>>dp(n+1);
// 深度为i，从x开始，长度为 (1<<y) 的最大值
for(int i=1;i<=n;i++){
if(dpo[i].size()==0) continue;
dp[i].resize(dpo[i].size()+1);
int sz=log2((int)dpo[i].size())+1;
for(int x=0;x<dpo[i].size();x++){
dp[i][x].resize(sz);
dp[i][x][0]=val[dpo[i][x]];
}
for(int y=1;y<sz;y++){
for(int x=0;x<dpo[i].size()&&(x+(1<<y)-1)<dpo[i].size();x++){
dp[i][x][y]=max(dp[i][x][y-1],dp[i][x+(1<<(y-1))][y-1]);
}
}
}
auto ask=[&](int depth,int l,int r)->i64 {
i64 ans=0;
int len=log2(r-l+1);
ans=max(ans,dp[depth][l][len]);
ans=max(ans,dp[depth][r-(1<<len)+1][len]);
return ans;
};
int q;
cin>>q;
while(q--){
int u,d;
cin>>u>>d;
int nd=dep[u]+d;
if(nd>n||dpo[nd].size()==0){
cout<<"-1\n";
continue;
}
// 先找出 dfn在 l[u] 和 r[u] 之间的点。
int l1=0,r1=dpo[nd].size()-1;
int ansl=-1,ansr=-1;
while(l1<r1){
int mid=(l1+r1)>>1;
if(dfn[dpo[nd][mid]]>=ls[u]) {
r1=mid;
ansl=mid;
}
else l1=mid+1;
}
if(dfn[dpo[nd][l1]]>=ls[u]){
ansl=l1;
}
if(ansl==-1){
cout<<"-1\n";
continue;
}
int l2=0,r2=dpo[nd].size()-1;
while(l2<r2){
int mid=(l2+r2+1)>>1;
if(dfn[dpo[nd][mid]]<=rs[u]) {
l2=mid;
ansr=mid;
}else r2=mid-1;
}
if(dfn[dpo[nd][l2]]<=rs[u]){
ansr=l2;
}
if(ansr==-1||ansl>ansr){
cout<<"-1\n";
continue;
}
i64 temp=val[u]-val[1];
cout<<ask(nd,ansl,ansr)-temp<<"\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
while(t--) {
solve();
}
return 0;
}
网易公司福利 162人发布