【题解】2020牛客寒假算法基础集训营4

╰半橙微兮° 2023-07-05 05:21 12阅读 0赞

> 比赛链接：[https://ac.nowcoder.com/acm/contest/3005][https_ac.nowcoder.com_acm_contest_3005]  
> 其他比赛题解：  
> [【题解】2020牛客寒假算法基础集训营1][2020_1]  
> [【题解】2020牛客寒假算法基础集训营2][2020_2]  
> [【题解】2020牛客寒假算法基础集训营3][2020_3]  
> [【题解】2020牛客寒假算法基础集训营5][2020_5]

### 试题目录 ###

*  A - 欧几里得（规律 + 斐波那契数列）
 *  B - 括号序列（栈）
 *  C - 子段乘积（尺取法+逆元 / 线段树）
 *  D - 子段异或（前缀异或）
 *  E - 最小表达式（模拟 + 贪心）
 *  F - 树上博弈（异或 + 思维）

# A - 欧几里得（规律 + 斐波那契数列） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3005/A][https_ac.nowcoder.com_acm_contest_3005_A]

*  **思路：** 对于这类问题，暴力肯定超时。那么可以先打下表，把前十个 a 和 b 打表找规律，会发现 a 和 b 分别是斐波那契数列。

**Code：**

#include <iostream>
    using namespace std;
    typedef long long ll;
    ll f1[100],f2[100],ans[100];
    int main(){ 
        f1[0]=1,f1[1]=2;
        for(int i=2;i<=80;i++)
            f1[i]=f1[i-1]+f1[i-2];
        f2[0]=0,f2[1]=1;f2[2]=2;
        for(int i=3;i<=80;i++)
            f2[i]=f2[i-1]+f2[i-2];
        for(int i=0;i<=80;i++)
            ans[i]=f1[i]+f2[i];
        int t;    cin>>t;
        while(t--){ 
            int n;    cin>>n;
            cout<<ans[n]<<endl;
        }
        return 0;
    }

# B - 括号序列（栈） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3005/B][https_ac.nowcoder.com_acm_contest_3005_B]

*  **思路：** 经典栈问题。

**Code：**

#include <iostream>
    #include <stack>
    using namespace std;
    int main(){ 
        string str;    cin>>str;
        stack<char> s;
        for(int i=0;i<str.length();i++){ 
            if(str[i]=='(')
                s.push(str[i]);
            if(str[i]==')'){ 
                if(!s.empty() && s.top()=='(')
                    s.pop();
                else{ 
                    cout<<"No"<<endl;
                    return 0;
                }
                    
            }
            if(str[i]=='[')
                s.push(str[i]);
            if(str[i]==']'){ 
                if(!s.empty() && s.top()=='['){ 
                    s.pop();
                    
                }
                else{ 
                    cout<<"No"<<endl;
                    return 0;
                }
                    
            }
            if(str[i]=='{')
                s.push(str[i]);
            if(str[i]=='}'){ 
                if(!s.empty() && s.top()=='{'){ 
                    s.pop();
                    
                }
                else{ 
                    cout<<"No"<<endl;
                    return 0;
                }
                    
            }
        }
        if(s.empty())
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
        return 0;
    }

# C - 子段乘积（尺取法+逆元 / 线段树） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3005/C][https_ac.nowcoder.com_acm_contest_3005_C]

*  **思路：** 本题可以使用线段树，也可以使用尺取法 + 逆元。

1.  尺取法：l 代表左端点，r 代表右端点。l 先不动，r 往前扫描，如果成功扫到，有 k 个非0元素的子段就累乘起来，最后把最左端的元素除了（用乘法逆元，否则会出现除以 0 的异常），左端点往前移动，l++，再继续扫描。在未达到 k 个非零元素的子段前，如果遇到 0，当前的区间重置 ,左端点直接到 0 的下一个位置继续扫描。
2.  线段树：线段树裸题，只用到查询，还不用更新。

**Code1：**

//尺取法 + 乘法逆元
    #include <iostream>
    using namespace std;
    typedef long long ll;
    const int N=2e5+100;
    const ll mod=998244353;
    int n,k;
    ll a[N];
    ll q_pow(ll a,ll b){ 
        ll ans=1,res=a%mod;
        while(b){ 
            if(b&1)    ans=ans*res%mod;
            res=res*res%mod;
            b>>=1;
        }
        return ans%mod;
    }
    ll inv(ll a,ll mod){ 
        return q_pow(a,mod-2)%mod;
    }
    int main(){ 
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int l=1,r=1;
        ll mul=1,ans=0;
        while(r<=n){ 
            if(a[r]){ 
                mul=mul*a[r]%mod;
                if(r-l+1==k){ 
                    ans=max(ans,mul);
                    mul=mul*inv(a[l],mod)%mod;
                    l++;
                }
            }
            else{ 
                mul=1;
                l=r+1;
            }
            r++;
        }
        cout<<ans<<endl;
        return 0;
    }

**Code2：**

//线段树
    #include <iostream>
    using namespace std;
    typedef long long ll;
    const int N=2e5+100;
    const ll mod = 998244353;
    ll a[N];
    struct node{ 
        int l,r;
        ll v;
    }tree[N<<2];
    void build_tree(int node,int l,int r){ 
        tree[node].l=l,    tree[node].r=r;
        if(l==r){ 
            tree[node].v=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build_tree(node<<1,l,mid);
        build_tree(node<<1|1,mid+1,r);
        tree[node].v=tree[node<<1].v*tree[node<<1|1].v%mod;
    }
    ll query(int node,int l,int r){ 
        if(tree[node].l==l && tree[node].r==r)
            return tree[node].v;
        int mid=(tree[node].l+tree[node].r)>>1;
        if(r<=mid)    return query(node<<1,l,r);
        if(l>mid)    return query(node<<1|1,l,r);
        return query(node<<1,l,mid)*query(node<<1|1,mid+1,r)%mod;
    }
    int main(){ 
        int n,k;    cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        build_tree(1,1,n);
        ll ans=0;
        for(int i=1;i<=n-k+1;i++)
            ans=max(ans,query(1,i,i+k-1));
        cout<<ans<<endl;
        return 0;
    }

# D - 子段异或（前缀异或） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3005/D][https_ac.nowcoder.com_acm_contest_3005_D]

*  **思路：** 异或和：【L,R】=【1,R】^【1，L-1】，要使异或和为 0 ，那么必须有【1，R】==【1，L-1】，因为 A ^ A = 0 。所以前缀异或并存入 map，如果前面存在前缀异或与当前的前缀异或相等，那么答案就加上前面前缀异或的数量。

**Code：**

#include <iostream>
    #include <map>
    using namespace std;
    typedef long long ll;
    const int N=2e5+100;
    ll a[N];
    map<ll,ll> mp;
    int main(){ 
        int n;    cin>>n;
        mp[0]=1;
        ll cur=0,ans=0;
        for(int i=0;i<n;i++){ 
            cin>>a[i];
            cur^=a[i];
            if(mp[cur])    
                ans+=mp[cur];
            mp[cur]++;
        }
        cout<<ans<<endl;
        return 0;
    }

# E - 最小表达式（模拟 + 贪心） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3005/E][https_ac.nowcoder.com_acm_contest_3005_E]

*  **思路：** 有 cnt 个加号，就有 cnt + 1 个数，统计 1 ~ 9 数字的个数。对于表达式中的每个数，要把最大的尽量放在最低位，比如 9 尽量放在个位上。然后计算每个位置上的数值，大于 10 的就要进位。最后依次输出各个位置上的数值，要注意的就是中间的 0 也要输出。

**Code：**

#include <iostream>
    using namespace std;
    const int N=5e5+100;
    int n[N],s[N],sum[N];
    int main(){ 
        string str;    cin>>str;
        int cnt=1;
        for(int i=0;i<str.length();i++){ 
            if(str[i]!='+')
                n[str[i]-'0']++;
            else
                cnt++;
        }
        int p1=0,p2=0;
        for(int i=9;i>=1;i--){ 
            while(n[i]){ 
                sum[p1]+=i;
                n[i]--;
                p2=(p2+1)%cnt;
                if(!p2)    p1++;
            }
        }
        for(int i=0;i<=p1+100;i++){ 
            sum[i+1]=sum[i+1]+sum[i]/10;
            sum[i]%=10;
        }
        int vis=0;
        for(int i=p1+100;i>=0;i--){ 
            if(sum[i] || vis){ 
                cout<<sum[i];
                vis=1;
            }
        }
        cout<<endl;
        return 0;
    }

# F - 树上博弈（异或 + 思维） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3005/F][https_ac.nowcoder.com_acm_contest_3005_F]

*  **思路：** 当两人间的距离（边数）为偶数时，总是牛牛胜。否则总是牛妹胜。故两人同为奇数深度和同为偶数深度的情况即为答案。用异或 1 将其深度转化为 0 或 1 来表示奇数和偶数，再统计 0、1 的个数即可。

**Code：**

#include <iostream>
    using namespace std;
    typedef long long ll;
    const int N=1e6+100;
    ll depth[N],cnt[5];
    int main(){ 
        int n;    cin>>n;
        int p;
        depth[1]=0,cnt[0]=1;
        for(int i=2;i<=n;i++){ 
            cin>>p;
            depth[i]=depth[p]^1;
            cnt[depth[i]]++;
        }
        cout<<cnt[0]*(cnt[0]-1)+cnt[1]*(cnt[1]-1)<<endl;
        return 0;
    }

[https_ac.nowcoder.com_acm_contest_3005]: https://ac.nowcoder.com/acm/contest/3005
[2020_1]: https://blog.csdn.net/weixin_44668898/article/details/104284030
[2020_2]: https://blog.csdn.net/weixin_44668898/article/details/104286708
[2020_3]: https://blog.csdn.net/weixin_44668898/article/details/104291713
[2020_5]: https://blog.csdn.net/weixin_44668898/article/details/104308608
[https_ac.nowcoder.com_acm_contest_3005_A]: https://ac.nowcoder.com/acm/contest/3005/A
[https_ac.nowcoder.com_acm_contest_3005_B]: https://ac.nowcoder.com/acm/contest/3005/B
[https_ac.nowcoder.com_acm_contest_3005_C]: https://ac.nowcoder.com/acm/contest/3005/C
[https_ac.nowcoder.com_acm_contest_3005_D]: https://ac.nowcoder.com/acm/contest/3005/D
[https_ac.nowcoder.com_acm_contest_3005_E]: https://ac.nowcoder.com/acm/contest/3005/E
[https_ac.nowcoder.com_acm_contest_3005_F]: https://ac.nowcoder.com/acm/contest/3005/F