牛客小白月赛65题解

A 牛牛去购物

循环枚举买多少个篮球，剩下的钱能买多少足球就买多少即可，时间复杂度 $O(n)O(n)$。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,a,b;
    cin>>n>>a>>b;
    int ans=n;
    for(int i=0;i*a<=n;i++){
        ans=min(ans,(n-i*a)%b);
    }
    cout<<ans;
    return 0;
}

B 牛牛写情书

定义一个字符串 $pp$ ，遍历 $ss$ ，如果当前位 $\in [a,z]\backslash in[a,z]$ ，就把当前位加到 $pp$ 中，这样就获得了原始牛牛的情书，之后循环 $ii$ 枚举起点，$O(\mathrm{\mid }m\mathrm{\mid })O(|m|)$ 检验 $p[i,i+m-1]p[i,i+m-1]$ 与 $mm$ 是否相等即可，时间复杂度 $O(\mathrm{\mid }s\mathrm{\mid }\times \mathrm{\mid }m\mathrm{\mid })O(|s|\backslash times\; |m|)$。

#include <bits/stdc++.h>
using namespace std;
int n,m;
string s,k,p;
bool check(int x){
    for(int i=x;i<x+m;i++){
        if(p[i]!=k[i-x]) return false;
    }
    return true;
}
int main(){
    cin>>n>>m>>s>>k;
    for(auto i:s){
        if(i>='a'&&i<='z') p+=i;
    }
    for(int i=0;i+m<=p.length();i++){
        if(check(i)){
            cout<<"YES";
            return 0;
        }
    }
    cout<<"NO";
    return 0;
}

C 牛牛排队伍

题目相当于有一个 $11$ 到 $nn$ 的序列 $aa$ ，存在删除操作，求 $a[i-1]a[i-1]$。对于三个数 $a[i-1],a[i],a[i+1]a[i-1],a[i],a[i+1]$ ，删除 $a[i]a[i]$ 后对该序列的影响本质其实就是 $a[i+1]a[i+1]$ 的前一项变成了 $a[i-1]a[i-1]$ ，$a[i-1]a[i-1]$ 的后一项变成了 $a[i+1]a[i+1]$ ，其他相邻的元素前后对应关系都不变，所以可以用两个数组表示元素的前一项以及后一项是多少，初始化 $qian[i]=i-1,hou[i]=i+1qian[i]=i-1,hou[i]=i+1$ ，删除 $a[i]a[i]$ 的操作可以等价于 $qian[hou[i]]=qian[i],hou[qian[i]]=hou[i]qian[hou[i]]=qian[i],hou[qian[i]]=hou[i]$ ，这样删除操作时间复杂度变为 $O(1)O(1)$ ，查询也只需要输出 $qian[x]qian[x]$ 即可，查询时间复杂度也是 $O(1)O(1)$ ，整体时间复杂度为 $O(n+m)O(n+m)$ 。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k,op,x;
int qian[N],hou[N];
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        qian[i]=i-1;
        hou[i]=i+1;
    }
    while(k--){
        cin>>op>>x;
        if(op==1){
            qian[hou[x]]=qian[x];
            hou[qian[x]]=hou[x];
        }else{
            cout<<qian[x]<<'\n';
        }
    }
    return 0;
}

D 牛牛取石子

除了 $a=1,b=1a=1,b=1$ 的特例牛牛会输掉以外，只要 ，牛牛都可以把少的那堆直接拿完导致牛妹拿不了而赢得比赛。除此之外观察取石子的 $22$ 种方案可知，不管牛牛选择哪种方案，牛妹都可以拿另一种使得 $a,ba,b$ 两堆的石子数量同时 $-3-3$ ，因此只要 $a,ba,b$ 中较小的那个数是 $33$ 的倍数 ，牛妹一定能把那一堆拿到 $00$ 个使得牛牛无法行动，而对于 的情况，牛妹也一定可以最后把两堆石子拿到都只剩 $11$ 个从而赢得比赛。

#include <bits/stdc++.h>
using namespace std;
void solve(){
    long long n,m;
    cin>>n>>m;
    if(n>m) swap(n,m);
    if(n==1&&m==1) cout<<"niumei\n";
    else if(n<3) cout<<"niuniu\n";
    else if(n%3==0) cout<<"niumei\n";
    else if(n==m&&n%3==1) cout<<"niumei\n";
    else cout<<"niuniu\n";
}
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int _=1;
    cin>>_;
    for(int i=1;i<=_;i++){
        solve();
    }
    return 0;
}

E 牛牛做构造

对于任意一个已经构建好的长度为 $m-1(m-1\mathrm{\ne }0)m-1(m-1\backslash neq0)$ 的数组，在数组开头插入一个 $mm$ ，都会新增 $\lfloor lo{g}_2(m-1)\rfloor +1\backslash lfloor\; log\_2(m-1)\backslash rfloor+1$ 个满足题意的二元组 ，

先 $O(n)O(n)$ 预处理出每一个 $xx$ 放在 $[1,x-1][1,x-1]$ 的排列开头能新增多少， 之后从 $nn$ 到 $11$ 每个数考虑贡献，对于每次考虑的数 $xx$ ： 假如 $k\ge f(x)k\backslash ge\; f(x)$ ，那就把这个 $xx$ 放在接下来所有数的开头，然后令 $k=k-f(x)k=k-f(x)$ ，代表这个数给整个数组贡献了 $f(x)f(x)$ 的价值。 假如 ，那就把这个 $xx$ 放在接下来所有数的后面，代表这个数给整个数组贡献了 $00$ 的价值。 所有数都处理完如果 $k>0k>0$ ，代表不存在解，输出 $-1-1$ 。 所有数都处理完如果 $k=0k=0$ ，只需要新建两个数组 $a,ba,b$ ，对于遍历过程中 $k>=f(x)k>=f(x)$ 时，把 $xx$ 放进 $aa$ 数组，否则把 $xx$ 放进 $bb$ 数组，顺序输出 $aa$ 数组，逆序输出 $bb$ 数组即可。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,f[N];
int k;
vector<int>a,b;
int main(){
    cin>>n>>k;
    int now=1;
    for(int i=2;i<=n;i++){
        f[i]=f[i-1];
        if(i-1==now) {
            f[i]++;
            now*=2;
        }
    }
    for(int i=n;i>=1;i--){
        if(k>=f[i]) {
            a.push_back(i);
            k-=f[i];
        }else b.push_back(i);
    }
    if(k) cout<<"-1";
    else {
        reverse(b.begin(),b.end());
        for (auto i:a) cout << i << " ";
        for (auto i:b) cout << i << " ";
    }
    return 0;
}

F 牛牛的考试

题意可以简化成给定一颗根节点为 $11$ 的树，每次可以花费 $xx$ 的时间让任意两个或一个叶子结点的值都 $-x-x$ ，如果一个结点的值 ，那么这个结点就消失了，如果一个结点的所有子节点都消失了，这个结点就变成了叶子结点，直到所有结点都消失的最小总时间。 用dfs自底向上遍历这棵树，对于每个结点，用一个pair<int,int>来表示这个结点的状态，第一维是以这个结点为子树的最大双开时间，第二维是以这个结点为子树的对应单开时间。

假如现在有一颗这样的树，从1号点开始dfs遍历时先遍历到3，3的对应状态是 $(0,3)(0,3)$ ，4的对应状态是 $(0,4)(0,4)$ ，5的对应状态是 $(0,5)(0,5)$，因为它们都是单独的一个结点，单看的话都只能单开学习，这三个点都遍历完dfs回到1号点，1号点刚开始是 $(0,0)(0,0)$ ，遇到3号的数据汇上来变成 $(0,3)(0,3)$ ，然后遇到4号点的数据 $(0,3)+(0,4)=(3,1)(0,3)+(0,4)=(3,1)$，相当于把3号点和4号点各自单开的3分钟拿来双开，之后遇到5号点的数据 $(0,5)(0,5)$，$(3,1)+(0,5)=(1,5)+(0,5)=(6,0)(3,1)+(0,5)=(1,5)+(0,5)=(6,0)$，这里把 $(3,1)(3,1)$ 变成 $(1,5)(1,5)$ 的原因在于，新汇上来的结点的单开时间>当前单开时间，那么从贪心的角度来看，应该通过减少当前的双开时间，让当前的单开时间尽可能接近新汇上来结点的单开时间，这样最后结合起来尽可能使单开时间=0，以达到能双开就双开的最优解。最后$(6,0)(6,0)$ 再加上自身的1分钟变成 $(6,1)(6,1)$，返回当前状态。 因此只需要dfs遍历这棵树，每次把子节点的状态合并，pair<int,int>的第二维再加上当前结点的时间，一层层向上返回状态即可。因为每次维护的单开时间尽量去合并，保证单开的时间是最少的，一直在双开，所以时间总花费最小，时间复杂度 $O(n)O(n)$。

#include <bits/stdc++.h>
#define int long long
const int N=1e6+10;
using namespace std;
typedef pair<int, int> PII;
int n,a[N];
vector<int>v[N];
PII add(PII x,PII y){
    if(x.second>y.second) swap(x,y);
    int cha=min((y.second-x.second)/2,x.first);
    x.first-=cha;
    x.second+=2*cha;
    x.first+=x.second;
    x.second=y.second-x.second;
    x.first+=y.first;
    return x;
}
PII dfs(int now){
    PII ans=PII(0,0);
    for(auto i:v[now]){
        PII v=dfs(i);
        ans=add(ans,v);
    }
    ans.second+=a[now];
    return ans;
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        v[x].push_back(i);
    }
    PII ans= dfs(1);
    cout<<ans.first+ans.second;
    return 0;
}