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

A：欧几里得

输入

1
0

输出

1

说明

gcd(1,0) 由于 b=0，不会递归，即是递归0次。

---

根据样例我们可以尝试写出n=2,3,4...的结果，发现他是斐波那契数列，写一个程序输出斐波那契前100位(long long)，打表即可

#include <iostream>
#include <cstdio>
using namespace std;

long long ans[100]={1,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258};

int main(){
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<ans[n]<<endl;
    }
    return 0;
}

B：括号序列

输入

(){}[]

输出

Yes

输入

({[]})

输出

Yes

输入

([)]

输出

No

---

只需要模拟一个栈即可，遇到左括号时压栈，遇到右括号看可否与栈顶元素相匹配，不匹配直接输出错误，匹配则消去栈顶元素。在输入结束后还要检查栈是否为空，为空证明有左括号未匹配

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;

stack<char>s;
char t;

int main(){
    while(scanf("%c",&t)==1&&t!='\n'&&t!='\r'){
        if(!(t=='{'||t=='}'||t=='('||t==')'||t=='['||t==']'))break;
        if(t=='{'||t=='['||t=='(')s.push(t);
        else{
            if(s.empty()){cout<<"No";return 0;}
            char p=s.top();
            if((t=='}'&&p=='{')||(t==']'&&p=='[')||(t==')'&&p=='('))s.pop();
            else {cout<<"No";return 0;}
        }
    }
    if(s.empty())cout<<"Yes";
    else cout<<"No";
    return 0;
}

C：子段乘积

输入

5 3
1 2 3 0 8

输出

6

说明

1*2*3\mod 998244353=61∗2∗3mod998244353=6

---

可以使用双指针，但是需要求逆元，所以我直接用线段树求解

#include <iostream>
#include <cstdio>
#include <cstring>
#define M ((l+r)>>1)
#define LC (p<<1)
#define RC (LC|1)
using namespace std;

const int MAX_N=200050;
const int mod=998244353;
long long ss[4*MAX_N];
int n,k;

void up(int p){
    ss[p]=ss[LC]*ss[RC]%mod;
}

void modify(int p,int x,int v,int l,int r){
    if(l==r){
        ss[p]+=v;
        return;
    }
    if(x<=M)modify(LC,x,v,l,M);
    else modify(RC,x,v,M+1,r);
    up(p);
    return;
}

long long query(int p,int x,int y,int l,int r){
    if(x<=l&&r<=y){
        return ss[p];
    }
    long long res=1;
    if(x<=M)res=res*query(LC,x,y,l,M)%mod;
    if(M<y)res=res*query(RC,x,y,M+1,r)%mod;
    return res;
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        modify(1,i,t,1,n);
    }
    long long ans=0;
    for(int i=1;i+k-1<=n;i++){
        long long t=query(1,i,i+k-1,1,n);
        ans=ans<t?t:ans;
    }
    cout<<ans;
    return 0;
}

D：子段异或

输入

5
1 2 3 2 1

输出

2

说明

子段 [1,3] 和子段 [3,5] 是合法子段。

---

异或运算有自反性 \[ A^\wedge B ^\wedge B = A \] 运用这个性质我们可以得到 l~r的异或和为：前r的异或和 ^ 前l-1的异或和 所以l~r异或和为0当且仅当 l-1异或和==r-1异或和，所以我们 先计算一个异或和的前缀和 然后要找相同的数字，比较好的方法是 对于前缀数组排序，对于每一个数在左右统计相同的数字个数即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

long long s[200050],n;

int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&s[i]);
        s[i]=s[i]^s[i-1];
    }
    sort(s,s+n+1);
    long long ans=0,l=0;
    // for(int i=0;i<=n;i++)cout<<s[i]<<" * ";
    // cout<<endl;
    while(l<=n){
        long long r=upper_bound(s+l,s+n+1,s[l])-s;
        ans+=(r-l)*(r-l-1)/2;
        // cout<<s[l]<<' '<<l<<" "<<(r-l)*(r-l-1)/2<<endl;
        l=r;
    }
    printf("%lld",ans);
    return 0;
}

E：最小表达式

输入

111+1

输出

22

说明

11+11=22

输入

9998765432111

输出

1112345678999

输入

12+35

输出

38

说明

25+13 = 38

输入

23984692+238752+2+34+

输出

5461

说明

嗯，这个答案是可以得到的

---

首先找到这个字符串中+的数目，这个数目+1就是需要分出的数字 然后我们考虑位数问题：

1. 数字有20位，分成5组，那么每个数字均为4位要优于某个大于四位+某个小于四位
2. 数字有21位，分成5组，那么就是一个数字为五位，另外四个均为四位

最高位越小结果越小

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int len,num[500050],ans[500050],cnt_up,cnt_n;
char tmp[500050];

int main(){
    scanf("%s",tmp);
    for(int i=0;tmp[i]!='\0';i++){
        if(tmp[i]>='1'&&tmp[i]<='9')num[cnt_n++]=tmp[i]-'0';
        else cnt_up++;
    }
    int len_normal=cnt_n/(cnt_up+1),len_special=cnt_n%(cnt_up+1);
    sort(num,num+cnt_n);
    for(int i=0;i<len_special;i++)ans[0]+=num[i];

    int cur=len_special;
    for(int i=1;i<=len_normal;i++){
        for(int j=0;j<=cnt_up;j++){
            ans[i]+=num[cur++];
        }
        // cout<<"**"<<ans[i]<<"**"<<endl;
    }
    for(int i=len_normal;i>=1;i--){
        if(ans[i]>9)ans[i-1]+=ans[i]/10,ans[i]=ans[i]%10;
    }
    if(ans[0]!=0)cout<<ans[0];
    for(int i=1;i<=len_normal;i++)cout<<ans[i];
    return 0;
}

F：树上博弈

输入

3
1 2

输出

2

说明

当且仅当牛牛在1号点，牛妹在3号点，或者牛牛在3号点，牛妹在1号点时，牛牛才获胜。

输入

2
1

输出

0

说明

由于无论如何牛牛都无路可走，因此必然牛妹获胜。

输入

30
1 1 2 1 2 1 3 2 3 4 2 3 1 2 3 4 2 4 5 6 3 4 12 12 12 13 13 13 13

输出

428

说明

QwQ

---

我们设两人距离为d 那么一个人走一步，另一个人走一步，最后他们的距离一定为d或d-2或d+2，所以d奇偶性是不变的，经过无数字运动，一定会出现一种情况，牛妹进入了一个子树，但是唯一的出口被牛牛堵了，也就是牛妹进入了死胡同 牛妹必然会最终移动到叶子上。同样，如果最初D是奇数，则牛妹获胜。 因此，答案取决于距离的奇偶性：如果是偶数，则牛牛获胜，否则牛妹获胜。

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;

const int MAX_N=1e6+50;
ll p[MAX_N],eid=0,deep_j,deep_o,n;
struct edge{
    int v,next;
}E[MAX_N];

void init(){
    eid=0;
    memset(p,-1,sizeof(p));
}

void insert(int u,int v){
    E[eid].next=p[u];
    E[eid].v=v;
    p[u]=eid++;
}

void dfs(int node,int deep){
    if(deep%2)deep_j++;
    else deep_o++;
    for(int i=p[node];i+1;i=E[i].next){
        dfs(E[i].v,deep+1);
    }
}

int main(){
    init();
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        int t;
        scanf("%d",&t);
        insert(t,i);
    }
    dfs(1,1);
    cout<<deep_j*(deep_j-1)+deep_o*(deep_o-1);
    return 0;
}

G：音乐鉴赏

输入

10
99 99 99 99 99 99 99 99 99 99

输出

50.00%

说明

需要随机占比50%。

---

首先解释一下官方题解的意思

1. Q: 这里的-y不应该是(y-90)吗？ A: 确实是，但是可以发现，因为\(y \in [0,90]\)所以y-90 均匀的分布在[-90,0]这与-y的分布式相同的，所以写了-y简便运算

2. Q: E是怎么推出来的? A: 在上一个式子中，带入y=90，得到\(\frac{(sorce-90)*(1-x)}{90x} \geq 1\)，如果一个一个分数满足题意，他的\(\frac{(sorce-90)*1-x}{90x} \geq 1\)，从数学期望上说，10%的人优秀，相当于0.1*n的人均下来要恰好=1 这就有了E式

实际上不必那么麻烦，我们可以按自己思路写下去 \[ sorce*(1-x)+xy \geq 90 \\ \frac{sorce*(1-x)-90} {-x} \leq y\\ \] 小于等于90的概率是 \[ \frac{sorce*(1-x)-90} {-90x}\\ \] 大于等于90的概率是 \[ 1-\frac{sorce*(1-x)-90} {-90x}\\ \frac{90x-90+sorce*(1-x)} {90x}\\ \] 于是 \[ \sum_{i=1}^{n}\frac{90x-90+sorce*(1-x)} {90x} = 0.1n \]

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main(){
    int n,sumn=0;
    cin>>n;
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        sumn+=t;
    }
    double s2=(sumn-90*n);
    printf("%.2f%%",(s2/(9*n+s2)*100));
    return 0;
}

H: 坐火车

输入

5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输出

0 3 4 3 0

---

考虑构建一个数组记录某个颜色在当前状态(下标) 下，位置左边有多少个该颜色火车(sum_l[color])，右边有多少个火车(sum_r[color])，构建的这个数组随着当前数组下标位置的改变而改变 在构建一个前缀和，记录某个颜色在当前状态(下标) 左乘右的值(也就是贡献值)，这样，对于每一次查询我们只需要做一个差就可以了，我们用树状数组实现它 对于一次状态(数组下标)的移动(以从红色移到蓝色为例)，发生的变化是

1. 红色作左边的个数+1(sum_l[红色]++)
2. 这个红色可以和右边的红色匹配，所以红色贡献值+=sum_r[红色]
3. 蓝色作右边的个数-1(sum_r[蓝色]--)
4. 这个蓝色失去了和左边的蓝色的匹配，所以蓝色贡献值-=sum_l[蓝色]

注意的是第一次是没有12步骤的，因为刚刚移动到第一节火车

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_N=5e5+50;

long long sum_l[MAX_N],sum_r[MAX_N],s[MAX_N],n,col[MAX_N],col_l[MAX_N],col_r[MAX_N];

void add(int x,int v){
    for(int i=x;i<=MAX_N;i+=i&(-i))s[i]+=v;
}

long long query(int x){
    long long res=0;
    for(int i=x;i;i-=i&(-i))res+=s[i];
    return res;
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d%d",&col[i],&col_l[i],&col_r[i]);
        sum_r[col[i]]++;
    }
    for(int i=0;i<n;i++){
        sum_r[col[i]]--;
        add(col[i],-sum_l[col[i]]);
        if(i==0){
            printf("%d ",query(col_r[i])-query(col_l[i]-1));
            continue;
        }
        sum_l[col[i-1]]++;
        add(col[i-1],sum_r[col[i-1]]);
        printf("%lld ",query(col_r[i])-query(col_l[i]-1));
    }
    return 0;
}

I: 匹配星星

输入

2
1 1 0
2 2 1

输出

1

输入

2
1 1 1
2 2 1

输出

0

---

我们构建一个可重复集合存放那些待配匹配的星星，他们的z一定是0，这样读取到z=1的星星的时候我们就拿z=1的星星尝试和他们匹配 在处理星星的时候我们遵循以下顺序 x小的优先读取，这样保证后读的星星x一定大，这样我准备去匹配的z=1星星一定比在待匹配集合中的星星x大，z大 匹配时我们的xz都比集合中的星星大，我们只要找y比匹配星星小的即可，那选哪个呢？选比匹配星星的y小的里面y最大的，这样，不仅满足了这次匹配，也为下次匹配创建了最大的机会 这么找这个星星呢？ 可以使用upper_bound. upper_bound在一般情况下是找严格大于一个数的第一个数据 所以我们可以重载<从而实现找到严格小于这个数据的第一个数据，看这里 可重复集合使用multiset即可实现，multiset自带一个upper_bounder的方法，用这个不需要指定查找范围

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

const int MAX_N=1e5+50;

struct star{
    int x,y,z;

    bool operator < (const star t)const{
        return y>t.y;
    }

}a[MAX_N];

bool cmp(star a,star b){
    return a.x==b.x?a.z>b.z:a.x<b.x;
}

multiset<star>s;     //s

int main(){
    int n,ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++){
        if(a[i].z==0)s.insert(a[i]);
        else{
            auto it=s.upper_bound(a[i]);
            if(it!=s.end()){
                s.erase(it);
                ans++;
            }
        }
    }
    printf("%d",ans);
    return 0;
}

J: 二维跑步

输入

5 2

输出

5616

---

在这里插入图片描述

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
int mod = 998244353;
inline int sq(int x){return 1ll*x*x%mod;}
inline int sub(int a,int b){return a<b?a-b+mod:a-b;}
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int pow(int a,int b){if(b == 0)return 1;return b&1?mul(sq(pow(a,b/2)),a):sq(pow(a,b/2));}
const int N = 3000010;
int G[N],fac[N],invfac[N],pow2[N],pow3[N],n,m;
inline int C(int n,int m){return mul(fac[n],mul(invfac[m],invfac[n-m]));}

inline int F(int n,int m){
    if(m>n || m<0) return 0;
    return mul(mul(fac[n],mul(invfac[m],invfac[n-m])),mul(pow2[n-m],pow3[m]));
}
int main() {
    fac[0] = pow2[0] = pow3[0] = 1;
    for(int i=1;i<N;i++){
        fac[i] = 1ll*fac[i-1]*i%mod;
        pow2[i] = 1ll*pow2[i-1]*2%mod;
        pow3[i] = 1ll*pow3[i-1]*3%mod;
    }
    invfac[N-1] = pow(fac[N-1],mod-2);
    for(int i=N-2;i>=0;i--) invfac[i] = 1ll*invfac[i+1]*(i+1)%mod;
    cin>>n>>m;
    G[n] = 1;
    int upb = 0,lwb = 0,ans = 1;
    for(int move=n;move>=0;move--){
        int nlwb = max((-m+n-move+1)/2,0),nupb = min((m+n-move)/2,n-move);
        while(lwb<nlwb)ans = sub(ans,F(n-move,lwb)),lwb++;
        while(lwb>nlwb)lwb--,ans = add(ans,F(n-move,lwb));
        while(upb<nupb)upb++,ans = add(ans,F(n-move,upb));
        while(upb>nupb)ans = sub(ans,F(n-move,upb)),upb--;
        G[move] = ans;
        ans = mul(ans,5);
        ans = add(ans,mul(3,F(n-move,lwb-1)));
        ans = add(ans,mul(2,F(n-move,upb+1)));
        upb+=1;
    }
    ans = 0;
    for(int i=n;i>=0;i--) ans = add(ans,mul(G[i],C(n,i)));
    cout<<ans<<endl;
    return 0;
}