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

发表于 分类于 ， 阅读次数： 阅读次数： Valine： 本文字数： 10k
原题来自2020牛客寒假算法基础集训营1，作以存档备查

A:honoka和格点三角形

输入描述: 两个正整数和（ \(2\ ≤n,m≤10^9\)）（\(2 ≤n,m≤10^9\)） 输出描述: 面积为1的格点三角形的数量，对 \(10^9+7\)取模的结果。 示例1 输入

2 3

输出

6

说明

格点如下：
*  *  *
*  *  *
不妨设左下角坐标为(1,1)，右上角坐标为到(3,2)。
那么三点坐标可选：
（1，1）（1，2）（3，1）
（1，1）（1，2）（3，2）
（1，1）（2，2）（3，1）
（1，1）（3，1）（3，2）
（1，2）（2，1）（3，2）
（1，2）（3，1）（3，2）
所以共有6个。

示例2 输入

100 100

输出

7683984

就是一个分类讨论，据说有公式，不是特别清楚，注意多加()%mod ，玄学mod 代码

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

const long long mod=1000000007;
long long n,m,ans;

int main(){
    cin>>n>>m;
    if(m>=3&&n>=2)ans=(ans+(((n-1)*(m-2))%mod)*4%mod)%mod;
    if(m>=3&&n>=2)ans=(ans+((((m-2)*(n-1)%mod)*(m-2))%mod)*2%mod)%mod;
    if(m>=2&&n>=3)ans=(ans+((((m-1)*(n-2)%mod)*(m-2))%mod)*2%mod)%mod;
    if(n>=3&&m>=2)ans=(ans+(((m-1)*(n-2))%mod)*4%mod)%mod;
    if(n>=3&&m>=2)ans=(ans+((((n-2)*(m-1)%mod)*(n-2))%mod)*2%mod)%mod;
    if(n>=2&&m>=3)ans=(ans+((((n-1)*(m-2)%mod)*(n-2))%mod)*2%mod)%mod;

    cout<<ans;
    return 0;
}

B:kotori和bangdream

在这里插入图片描述 示例1 输入

100 50 500 400

输出

45000.00

二项分布数学期望 代码

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

int main(){
    double n,x,a,b;
    cin>>n>>x>>a>>b;
    double ans=(n*x/100*a+n*(100-x)/100*b);
    printf("%.2f",ans);
    return 0;
}

C:umi和弓道

在这里插入图片描述 输入

1 1
2 0
-1 2
-2 1

输出

0.50000000

说明

umi要保证能射中的靶子不超过0个，即全部挡住。在y轴上选区间[1,1.5]放置一个长度为0.5的挡板即可。

cout不会尽可能多的显示double位，所以使用printf 思路： 首先统计每一条路径与ox，oy的焦点 然后使用双指针对于ox,oy进行求解

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

double pos_y[100050],pos_x[100050],x_0,y_0;     //y轴上点的位置,x轴上点的位置,x0,y0
int n,k,curx,cury;                              //n,k,x轴上点的数目,y轴上点的数目

int main(){
    cin>>x_0>>y_0>>n>>k;
    for(int i=0;i<n;i++){
        double x,y;                             //输入x y
        cin>>x>>y;
        if(x_0*x>0&&y*y_0>0){continue;}         //同象限跳过
        else if(x_0*x>0&&x==x_0){pos_x[curx++]=x;}//cout<<"    at x= "<< x<<endl;}  //不同象限垂直于ox
        else if(y_0*y>0&&y==y_0){pos_y[cury++]=y;}//cout<<"    at y= "<< y<<endl;}  //不同象限垂直于oy
        else{
            double yy=(y-y_0)/(x-x_0)*(-x_0)+y_0 , xx=(x-x_0)/(y-y_0)*(-y_0)+x_0;   //直线与ox,oy交点,如果交点在两点间则计入
            if(yy>min(y,y_0)&&yy<max(y,y_0)){pos_y[cury++]=yy;}//cout<<"    at y= "<<yy<<endl;}
            if(xx>min(x,x_0)&&xx<max(x,x_0)){pos_x[curx++]=xx;}//cout<<"    at x= "<<xx<<endl;}
        }
    }

    sort(pos_y,pos_y+cury);                         //排序做双指针
    sort(pos_x,pos_x+curx);
    cury=unique(pos_y,pos_y+cury)-pos_y;            //排除的在oy上重复的点 如:x0=1 y0=1 {x=3 y=-1}与{x=4 y=-2} 在ox上均为(2,0)此时应去重
    curx=unique(pos_x,pos_x+curx)-pos_x;

    int global=n-k;
    double ans=0x3f3f3f3f;                      //初始化答案

    if(cury>=global){                           //oy上有足够多的点被选择
        for(int i = 0;i+global-1<cury;i++){     //滑动窗口
            ans=min(ans,pos_y[i+global-1]-pos_y[i]);
        }
    }

    //process ox
    if(curx>=global){
        for(int i = 0;i+global-1<curx;i++){
            ans=min(ans,pos_x[i+global-1]-pos_x[i]);
        }
    }

    if(ans!=0x3f3f3f3f)printf("%.8f",ans);
    else printf("-1");
    return 0;
}

D：hanayo和米饭

在这里插入图片描述 输入

5
2 5 1 3

输出

4

说明

开始共有5个碗，每个碗内分别有1、2、3、4、5粒米饭。rin拿走的是第四碗。这么简单的样例连tairitsu都看得懂好伐~

大水题

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

int date[100050];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++)scanf("%d",&date[i]);
    sort(date+1,date+n);
    for(int i=1;i<=n-1;i++){
        if(date[i]!=i){cout<<i;break;}
    }
    return 0;
}

E:rin和快速迭代

在这里插入图片描述 输入

12

输出

4

说明

12的因子：1，2，3，4，6，12。共6个。
6的因子：1，2，3，6。共4个。
4的因子：1，2，4。共3个。
3的因子：1，3。共2个。
12 → 6 → 4 → 3 → 2 ， 故迭代了4次。

签到题

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

long long x,times;

long long get_num(long long t){
    long long ans=0,i;
    for(i=1;i*i<=t;i++){
        if(t%i==0){ans++;}
    }
    i--;
    ans*=2;
    if(i*i==t)ans--;
    return ans;
}

int main(){
    long long n;
    long long num;
    cin>>n;
    while(true){
        times++;
        num=get_num(n);
        if(num==2)break;
        n=num;
        // cout<<num<<"**\n";
    }
    cout<<times;
    return 0;
}

F:maki和tree

在这里插入图片描述 输入

3
WBW
1 2
2 3

输出

3

说明

树表示如下：

在这里插入图片描述

其中只有2号是黑色点。
<1,2>、<2,3>、<1,3>三种取法都只经过一个黑色点。

这个题，分类讨论只有两种情况

1. 纯白链-黑点-纯白链
2. 纯白链-黑点

所以枚举每一个黑点，先找出他附近所有纯白链的个数就是2的答案，然后两两组合就是1的答案，这里可以直接使用并查集染色确定每一条纯白块并统计数量，其中的纯白链个数就是块元素个数，然后维护前缀和(不是数组，只是记录前缀和)加速1的运算

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

const int MAX_N=10000050;                                                   //写正确数据范围只过11%qwq
struct edge{
    int v,next;
}E[MAX_N];

long long p[MAX_N],dad[MAX_N],eid=0,num[MAX_N],n;
char s[MAX_N];

long long getdad(int p){                                                   //并查集
    if(dad[p]==p)return p;
    return dad[p]=getdad(dad[p]);
}

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

void insert2(int u,int v){
    insert(u,v);
    insert(v,u);
    if(s[u]=='W'&&s[v]=='W'&&getdad(u)!=getdad(v))dad[getdad(u)]=getdad(v);         //并查集合并
}

void init(){                                                                //初始化
    memset(p,-1,sizeof(p));
    eid=0;
    for(int i=1;i<=n;i++)dad[i]=i;
}

long long get_ans(){
    long long ans=0;
    for(int i=1;i<=n;i++)if(s[i]=='W'){                                     //统计并查集内节点数目
        num[getdad(i)]++;
    }
    for(int i=1;i<=n;i++){
        if(s[i]=='B'){                                                      //找黑色
            int cur=p[i];
            long long sgm=0;                                                //前缀和
            while(cur+1&&s[E[cur].v]=='B')cur=E[cur].next;                  //找到黑色节点连接的第一个白节点
            if(cur==-1)continue;                                            //一个白节点都没有退出
            sgm=num[getdad(E[cur].v)];                                      //第一个白节点所在并查集节点数直接放并查集
            for(cur=E[cur].next;cur+1;cur=E[cur].next){                     //继续往后找
                if(s[E[cur].v]=='B')continue;                               //如果这个是黑色就找下一个白色的
                ans+=num[getdad(E[cur].v)]*sgm;                             //第一张情况
                sgm+=num[getdad(E[cur].v)];                                 //维护前缀和
            }
            ans+=sgm;                                                       //第二种情况
        }
    }
    return ans;
}

int main(){
    scanf("%d",&n);
    init();
    scanf("%s",s+1);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        insert2(u,v);
    }
    cout<<get_ans();
    return 0;
}

G：eli和字符串

在这里插入图片描述 输入

5 2
abeba

输出

3

说明

选择“beb”子串，长度为3，其中包含相同的两个'b'

查找最小子串满足某条件，我想到二分长度 考虑jduge函数：这个子串定义和我们平时不一样，他只能去除头尾，所以上一个双指针结束

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

char ss[200500];
int n,k,times[500];

bool init(int len){
    memset(times,0,sizeof(times));
    for(int i=0;i<len;i++)
        if(++times[ss[i]-'a']>=k)return true;
    return false;
}

bool scoll(int len){
    if(init(len))return true;
    for(int i=1;i+len-1<n;i++){
        --times[ss[i-1]-'a'];
        if(++times[ss[i+len-1]-'a']>=k)return true;
    }
    return false;
}

int main(){
    scanf("%d%d",&n,&k);
    scanf("%s",&ss);
    int l=k,r=n;
    if(!init(n)){cout<<"-1";return 0;}
    while(l<r){
        int mid=(l+r)/2;
        if(scoll(mid))r=mid;
        else l=mid+1;
    }
    cout<<l;
    return 0;
}

H：nozomi和字符串

在这里插入图片描述 输入

5 1
10101

输出

3

说明

只有 1 次操作机会。
将第二个位置的 0 改成 1 ，字符串变成 11101，可以选出 111子串，长度为3 。
如果修改第三个或者第四个位置的字符也可以选出长度为 3 的子串。

又是一个二分双指针????? 于是把前一题代码改了下就交了，TLE 考虑特殊性质， - 首先我发现这个序列仅有 0/1 两个数字 这是一个01序列，所以 我们只需要求它的前缀和就可以得到0-n有多少个1！ 然后长度-1的数字就知道了0的长度 这是一种方法 - 我发现他只有两种字符，我们可以直接计算前n个数中有几个1,0

对于一个位置cur，我们有四个情况情况 这个位置是1，我们只想把后面的0->1 这个位置是1，我们只想把后面的1->0 这个位置是0，我们只想把后面的0->1 这个位置是0，我们只想把后面的1->0 我们只讨论第一个情况 我们 定 cur为这个我选的序列的第一个 我们获取这个点钱的一，因为我们是往后找k个0->1 所以我想找一个点，这个点他的前缀0-开始点前缀0==k，而且我想要这个点尽可能大 用upper_bounder! 然后这题就水过去了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define max(x,y) x>y?x:y
using namespace std;

char ss[200050];
int n,k,num0[200050],num1[200050];

int main(){
    scanf("%d%d%s",&n,&k,ss+1);

    // build the sigma '1'&'0'
    for(int i=1;i<=n;i++){
        if(ss[i]=='0'){num0[i]=num0[i-1]+1;num1[i]=num1[i-1];}
        if(ss[i]=='1'){num1[i]=num1[i-1]+1;num0[i]=num0[i-1];}
    }

    long long int ans=0;

    // 1->0
    for(int i=1;i<=n;i++){
        if(ss[i]=='0')ans=max(ans,upper_bound(num1+i+1,num1+n+1,num1[i]+k)-num1-i);
        if(ss[i]=='1')ans=max(ans,upper_bound(num1+i+1,num1+n+1,num1[i]+k-1)-num1-i);
    }

    // 0->1
    for(int i=1;i<=n;i++){
        if(ss[i]=='1')ans=max(ans,upper_bound(num0+i+1,num0+n+1,num0[i]+k)-num0-i);
        if(ss[i]=='0')ans=max(ans,upper_bound(num0+i+1,num0+n+1,num0[i]+k-1)-num0-i);
    }

    cout<<ans;
    return 0;
}

I：nico和niconiconi

在这里插入图片描述

输入

19 1 2 5
niconiconiconiconi~

输出

7

说明

"niconi"co"niconiconi"~
故为2+5=7分

无后效性，dp... 情况1 : dp[i]=max(dp[i],dp[i-4]+a) 情况2 : dp[i]=max(dp[i],dp[i-6]+b) 情况3 : dp[i]=max(dp[i],dp[i-10]+c) 代码：

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

long long dp[300050],n,a,b,c;
char ss[300050];

bool my_cmp(string t,int cur,int len){
    for(int i=0;i<=len;i++)
        if(t[i]!=ss[cur-len+i])return false;
    return true;
}

int main(){
    scanf("%d%d%d%d",&n,&a,&b,&c);
    scanf("%s",ss+1);

    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1];
        if(i>3)
            if(my_cmp("nico",i,3)){dp[i]=max(dp[i],dp[i-4]+a);}//cout<<"*";}
        if(i>5)
            if(my_cmp("niconi",i,5)){dp[i]=max(dp[i],dp[i-6]+b);}//cout<<"&";}
        if(i>9)
            if(my_cmp("niconiconi",i,9)){dp[i]=max(dp[i],dp[i-10]+c);}//cout<<"^";}

    }
    cout<<dp[n]<<endl;
    // for(int i=1;i<=n;i++)cout<<dp[i]<<" * ";
    return 0;
}

J u's的影响力

在这里插入图片描述 输入

4 2 3 2 1

输出

72

说明

f(1)=2，f(2)=3，f(3)=f(1)*f(2)*2=12，f(4)=f(2)*f(3)*2=72

非常明显，可以用Fib(i),Fib(i-1),Fib(i-2)轻松表示出i>=4的式子 然后我想： Fib求大数太慢了，于是用cmath的sqrt用fib通项公式计算 然后用快速幂加速 不行，快速幂处理小数无法取模qwq 用内置的pow 内置pow有效位数太差 那看来只能用递推公式了 但是实在是太慢了!! 这时只能使用矩阵快速幂这个东西 在这里插入图片描述 （看这个博文吧qwq） 完事

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct mt{
    ll a[3][3];
};
mt t(mt a,mt b,ll mod){
    mt res;
    int i,j,k;
    for(i=0;i<3;i++){
        for(j=0;j<3;j++){
            res.a[i][j]=0;
            for(k=0;k<3;k++){
                res.a[i][j]+=a.a[i][k]*b.a[k][j]%mod;
                res.a[i][j]%=mod;
            }
        }
    }
    return res;
}
mt power(mt a,ll b,ll mod){
    mt res;
    int i,j;
    for(i=0;i<3;i++){
        for(j=0;j<3;j++){
            res.a[i][j]=0;
        }
    }
    res.a[0][0]=res.a[1][1]=res.a[2][2]=1;

    while(b){
        if(b&1)res=t(res,a,mod);
        b>>=1;
        a=t(a,a,mod);
    }
    return res;
}
ll feb(ll n,ll mod){
    mt temp;
    int i,j;
    for(i=0;i<3;i++){
        for(j=0;j<3;j++){
            temp.a[i][j]=0;
        }
    }
    temp.a[0][1]=temp.a[1][1]=temp.a[1][0]=temp.a[1][2]=1;
    mt res=power(temp,n-1,mod);
    return (res.a[0][0]+res.a[0][1])%mod;
}
ll feb2(ll n,ll mod){
    mt temp;
    int i,j;
    for(i=0;i<3;i++){
        for(j=0;j<3;j++){
            temp.a[i][j]=0;
        }
    }
    temp.a[0][1]=temp.a[1][1]=temp.a[1][0]=temp.a[1][2]=temp.a[2][2]=1;
    mt res=power(temp,n-1,mod);
    return (res.a[0][0]+2*res.a[0][1]+res.a[0][2])%mod;
}
ll power(ll a,ll b,ll mod){
    ll res=1;

    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
int main(){
    int m=1e9+7;

    int i,j;
    ll n,x,y,a,b;
    cin>>n>>x>>y>>a>>b;
    if(n==1){cout<<x%m;return 0;}
    if(n==2){cout<<y%m;return 0;}
    if(x%m==0||y%m==0||a%m==0){cout<<0;return 0;}
    x%=m;
    y%=m;

    a=power(a%m,b,m);       //这里要注意a对m取模

    cout<<power(x,feb(n-2,m-1),m)*power(y,feb(n-1,m-1),m)%m*power(a%m,feb2(n-2,m-1)%(m-1),m)%m<<endl;

}