2020牛客寒假算法基础集训营1 题解-白红宇

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

阅读量：3899 次

发布时间：2019-05-23

本文共 5108 字，大约阅读时间需要 17 分钟。

【A-honoka和格点三角形】

呕，花我时间最多的一道题，因为一开始推导错了各种思维发散，后来节奏全乱了。

因为面积为1的三角形只有两种情况，一种是底边为1，高为2；一种是底边为2，高为1。因此我们可以从这里入手，考虑底边分别为1和2时的情况数*边数，特别注意的是，存在同时底边为1和底边为2的三角形，所以要删去重复部分。

#include 
   
    using namespace std;typedef long long ll;const int N=1e6+5;const ll mod=1e9+7;int main(){    ll n,m;    scanf("%lld%lld",&n,&m);    ll a=(((n-2)*n%mod)*(2*m-2)%mod+((m-2)*m%mod)*(2*n-2)%mod)%mod; //底边为2    ll b=(((n-2)*(n-1)%mod)*(2*m-4)%mod+((m-2)*(m-1)%mod)*(2*n-4)%mod)%mod;    printf("%lld\n",(a+b)%mod);    return 0;}

【B-kotori和bangdream】

签到题一。

printf("%.2f\n",(double)n*((x/100.0)*a+(1-x/100.0)*b));

【C-umi和弓道】

将每个点与起始点(x0,y0)连接并记录下与X轴或Y轴的交点（如果有），分别在X轴和Y轴用双指针法确定包含n-k个点的最短长度，最后输出最小值（不可能输出-1）。

#include 
   
    using namespace std;typedef long long ll;const int N=1e6+5;vector 
    
      v[3];int main(){    double x,y; scanf("%lf%lf",&x,&y);    int n,k; scanf("%d%d",&n,&k);    for(int i=0;i
     
      =n-k){            sort(v[t].begin(),v[t].end());            for(int i=n-k-1,j=0;i

【D-hanayo和米饭】

签到题二，排序遍历查找即可。

【E-rin和快速迭代】

签到题三，暴力迭代计数即可。

【F-maki和tree】

首先，我们可以通过在纸上画画算算得到解法：即以黑色的节点为根结点并且只连接白节点构造出一棵树，在构造的过程中，假如我们定义Ans记录答案，那么Ans=Ans+已构造的树上的所有节点数目C*新加进去的子树的节点数目Cou，直到构造完成。而且我们比较容易得到，把所有黑色结点单独拿出构造这样一棵树，那么总和Ans就是我们要的答案。

但是，在这个过程中，白节点子树的所有节点数目是我们重复计算的，因此我们可以预先处理出每个白节点子树的所有节点数目。用队列处理一下并且记录一下父亲结点就可以得到。

#include 
   
    using namespace std;typedef long long ll;const int N=1e6+5;char s[N];vector 
    
      vec[N];int pre[N];int cnt[N];int vis[N];ll cul(int r){    ll ret=0;    int l=vec[r].size();    ll t=1;    for(int i=0;i

q; while(!q.empty()) q.pop(); int cou=1; vis[i]=1; q.push(i); while(!q.empty()){ int pos=q.front();q.pop(); int l2=vec[pos].size(); for(int j=0;j

【G-eli和字符串】

字符串仅由小写字母组成，那么如果存在答案最多只有26种可能，所以我们直接判断每一种可能字母的k个相同该字母的最短长度并更新答案即可。解法：首先我们跑出每个位置pos的下一个字母 'a'+i 的位置p[i][pos]，便于后续位置的转移。对于字母C，我们首先找出第一个满足k个相同字母C的子串，然后依次将头尾往后移动到下一个相同字母C的位置，并更新最短长度。以此类推。

#include 
   
    using namespace std;typedef long long ll;const int N=1e6+5;int a[30];char s[N];int p[30][N];int main(){    int n,k; scanf("%d%d",&n,&k);    scanf("%s",s+1);    int l=strlen(s+1),ma=0;    for(int i=1;i<=l;i++)        a[s[i]-'a']++,ma=max(ma,a[s[i]-'a']);    if(ma
    
     0;j--){ //这个位置的下一个位置            for(int i=0;i<26;i++){                if(s[j]-'a'==i) p[i][j-1]=j;                else p[i][j-1]=p[i][j];            }        }        for(int i=0;i<26;i++){            if(a[i]

【H-nozomi和字符串】

做法与上一题类似，细节部分稍有不同。

两种情况，连续全为1或0。跑出每个位置的下一个0/1的位置，便于后续操作中位置的转移。

以全为1为例：我们定义bg,ed分别记录子串的起点和终点，我们先跑出第一个用k次转换的连续1串。然后依次取消头部的转换并且将尾部的下一个0转换成1，在这个过程中更新最长连续串的长度。细节见代码，应该比较好懂。

#include 
   
    using namespace std;typedef long long ll;const int N=1e6+5;char s[N];int p[3][N];int main(){    int n,k; scanf("%d%d",&n,&k);    scanf("%s",s+1);    int l=n;    p[0][l]=p[1][l]=-1;    for(int j=l;j>0;j--){ //这个位置的下一个位置        for(int i=0;i<2;i++){            if(s[j]-'0'==i) p[i][j-1]=j;            else p[i][j-1]=p[i][j];        }    }    int ans=0;    //全为0/1    for(int i=0;i<2;i++){        int cnt=1;        int bg=1,ed=p[i][0];        while(cnt

【I-nico和niconiconi】

动态规划，暴力枚举所有可能性选择最优。

#include 
   
    using namespace std;typedef long long ll;const int N=1e6+5;string s;ll dp[N];int main(){    int n; ll a,b,c;    cin>>n>>a>>b>>c>>s;    s="1"+s;    for(int i=1;i<=n;i++){        dp[i]=dp[i-1];        if(i>=3&&s.substr(i-3,4)=="nico")            dp[i]=max(dp[i],dp[i-4]+a);        if(i>=5&&s.substr(i-5,6)=="niconi")            dp[i]=max(dp[i],dp[i-6]+b);        if(i>=9&&s.substr(i-9,10)=="niconiconi")            dp[i]=max(dp[i],dp[i-10]+c);    }    printf("%lld\n",dp[n]);    return 0;}

【J-u's的影响力】

（不补）

官方题解：

#include
   
    using namespace std;#define ll long longstruct 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<

转载地址：http://fefen.baihongyu.com/

你可能感兴趣的文章