写在前面

又写篇题解吧~

这场的题整体来说非常友好，也非常适合相关算法的练习，很适合补完。

如果哪题遇到解决不了的问题，或者有什么好的建议给到牛牛，欢迎留言评论区，我们会尽快给出答复。

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