我的位置:首页 > .Net系列>C++

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

时间:2020-02-06 23:05:00 来源:互联网 作者: 神秘的大神 字体:

A B C D E F G H I J
\(\checkmark\) \(\checkmark\) \(O\) \(\checkmark\) \(\checkmark\) \(O\) \(\checkmark\) \(O\) \(O\) \(\times\)

\(\checkmark\):代表比赛时通过。

\(O\):代表赛后补题通过。

\(\times\):代表目前还未通过。

A. honoka和格点三角形

题目链接

题目大意

在一个\(n\)\(m\)列的矩阵点阵中求出满足一下要求的三角形的个数:

  • 三角形的三个顶点均为格点(横纵坐标均为整数)。
  • 三角形的面积为\(1\)
  • 三角形至少有一条边和\(x\)轴或者\(y\)轴平行。

解题思路

三角形的面积为\(1\),并且横纵坐标均为整数,那么分为两种情况(平行\(x\)轴或者\(y\)轴的为底边):

  • 底边为\(1\),高为\(2\)
  • 底边为\(2\),高为\(1\)

再根据底边平行的轴不同,分为四种情况即可。

AC代码

#include<bits/stdc++.h>
const int mod = 1e9+7;
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int main()
{
    ll y,x;
    cin>>y>>x;
    ll res;
    if(x>=3) 
        res = ((2LL*(y-1)*(x-2))%mod)*(x-2+y)%mod;
    if(y>=3)
        res+= ((2*(x-1)*(y-2))%mod)*(x+y-2)%mod;
    res%=mod;
    cout<<res<<endl;
}

总结

规律总结题。

B. kotori和bangdream

题目链接

题目大意

每个音符有\(x\%\)的概率得\(a\)分,有\((100-x)\%\)的概率得\(b\)分,求\(n\)个字符的得分期望。

解题思路

求出\(n\)个字符分为全部为\(a\)分和\(b\)的得分,乘以对应的概率即为答案。

AC代码

#include<bits/stdc++.h>
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int main()
{
    double n,x,a,b;
    cin>>n>>x>>a>>b;
    a*=n;
    b*=n;
    a*=x;
    a/=100;
    b*=(100-x);
    b/=100;
    printf("%.2f",a+b);
    return 0;
}

总结

签到题,但由于自己的粗心,没有注意浮点数的使用。在比赛过程中遇到除运算的时候,应当小心一点。

C. umi和弓道

题目链接

题目大意

在二维坐标中有一个起始点\((x_0,y_0)\)与其他\(n\)个点相连构成\(n\)条射线,在\(x\)轴或者\(y\)轴上放一个挡板,切断两点之间的连接,现求挡板的最小长度以使没有被切断的连线的数量不超过\(k\)

解题思路

\(n\)个点中与起始点在同一象限的点是不可能被挡板给挡住的,那么分别统计与起始点不在同一象限的点与起始点的连线在\(x\)轴和\(y\)轴的交点。题目求没有被挡板挡住的连线不超过\(k\),换言之就是要挡住至少\(n-k\)个点。然后找出连续\(n-k\)个点构成区间的最小值。

AC代码

#include<bits/stdc++.h>
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
vector<double>v1,v2;
int main()
{
    double x0,y0;
    cin>>x0>>y0;
    int n,k;
    cin>>n>>k;
    k=n-k;
    for(int i=0;i<n;i++){
        double x1,y1;
        cin>>x1>>y1;
        double a=(y0-y1),b =(x1-x0);
        if(x1*x0<0){
            double jiao=a/b*x0+y0;
            v2.push_back(jiao);
        }
        if(y1*y0<0){
            double jiao=x0+b/a*y0;
            v1.push_back(jiao);
        }
    }
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    double res=1e18;
    if(v1.size()>=k){
        int st=0,ed=st+k-1;
        while(ed<v1.size()){
            res=min(res,v1[ed]-v1[st]);
            st++,ed++;
        }
    }
    if(v2.size()>=k){
        int st=0,ed=st+k-1;
        while(ed<v2.size()){
            res=min(res,v2[ed]-v2[st]);
            st++,ed++;
        }
    }
    if(res==1e18)cout<<"-1"<<endl;
    else printf("%.7lf",res);
    return 0;
}

总结

D. hanayo和米饭

题目链接

题目大意

\(1,2,3 \cdots,n\)个数字,现在从中任意拿走一个数字,根据剩下的\(n-1\)个数字,判断拿走的数字是多少。

解题思路

  • 方案1:直接排序

    将输入的\(n-1\)个数字存在一个数组当中,排一个序,遍历数组,如果数字的下标和数字不相等,即为答案。

  • 方案二:求和

    在输入的过程中求出\(n-1\)个数字的和,再根据高斯公式求出\(n\)个数字的和,两个相减即为答案。

AC代码

#include<bits/stdc++.h>
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int a[maxn];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>a[i];
    }
    sort(a,a+n-1);
    for(int i=0;i<n;i++){
        if(a[i]!=i+1){
            cout<<i+1<<endl;
            break;
        }
    }
    return 0;
}

总结

签到题。

E. rin和快速迭代

题目链接

题目大意

给你一个式子\(f(x)\)表示\(x\)的正整数因子的个数,不断迭代\(f(x)\)的结果,求最终结果为\(2\)时的迭代次数。

解题思路

直接模拟题意迭代即可,刚开始拿到这道题的时候,以为有什么规律,所以一开始的方向就错了。

时间复杂度为\(O(\sqrt{n})\)

AC代码

#include<bits/stdc++.h>
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int solve(ll x){
    int cnt=0;
    for(ll i=2;i*i<=x;i++){
        if(x%i==0){
            cnt+=2;
            if(i*i==x)cnt--;
        }
    }
    return cnt;
}
int main()
{
    ll n;
    cin>>n;
    int res=0;
    ll mid=solve(n)+2;
    while(mid!=2){
        res++;
        mid=solve(mid)+2;
        // cout<<mid<<endl;
    }
    res++;
    cout<<res<<endl;
    return 0;
}

总结

在做题的过程中一定要重视计算时间复杂度,最开始以为直接模拟会炸,所以没有去写,往找规律的方向去思考去了,耽误了时间。同时要注意数据的范围,这道题就犯了这个错误。

F. maki和tree

题目链接

题目大意

在一个有\(n\)个点的树上,每个点被标记为白色或者黑色,问有多少条只包含一个黑点的简单路径。

解题思路

简单路径只有两种情况下会包含一个黑点:

  • 起始点和终点都为白点。
  • 两个断点其中一个是黑点。

这道题个人认为切入点为黑点,因为路径中只有一个黑点,那么这个黑点要么为起始或者重点,要么将多个白点连接起来作为中间点。这样一来就要找到黑点连接的白点所在的联通块总共有多少个白点,因为是在树上,所以每个联通块是各自独立的,不存在重复计算的情况。计算联通块中节点的个数可以用并查集,并查集中在连接两个节点的时候,统计其所在父亲的孩子数量,这样其他节点所在联通块的节点数量为其父亲节点的孩子数量加\(1\)

假设某一个黑点,连接了\(k\)个节点,其中\(f(i)\)表示第\(i\)个节点所在联通块的节点个数:

  • 第一种情况的计算结果为\(\sum_{i=1}^k{\sum_{j=i+1}^k}f(i)*f(j)\)
  • 第二种情况的计算结果为\(\sum_{i=1}^kf(i)\)

AC代码

#include<bits/stdc++.h>
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int n;
string color;
vector<int>G[maxn];
int pre[maxn];
void init(){
    for(int i=0;i<maxn;i++){
        pre[i]=i;
    }
}
int childnum[maxn];
int nodenum[maxn];
int find(int x)
{
    int r=x;
    while(r!=pre[r]){
        r=pre[r];
    }
    int i=x,j;
    while(i!=pre[i]){
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}
void uni(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx!=fy){
        pre[fx]=fy;
        childnum[fy]+=childnum[fx]+1;
    }
}
ll sum[maxn];
ll solve(vector<int>temp){
    ll res=0;
    for(int i=0;i<temp.size();i++){
        res+=temp[i];
    }
    //求前缀和
    for(int i=0;i<temp.size();i++){
        sum[i+1]=sum[i]+temp[i];
    }
    for(int i=1;i<temp.size();i++){
        res+=temp[i]*sum[i];
    }
    return res;
}
int main()
{
    // freopen("data.txt","r",stdin);
    cin>>n;
    cin>>color;
    //对并查集数组进行初始化
    init();
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
        if(color[x-1]=='W'&&color[y-1]=='W'){
            uni(x,y);
        }
    }
    ll res=0;
    for(int i=1;i<=n;i++){
        nodenum[i]=childnum[find(i)]+1;
    }
    for(int i=1;i<=n;i++){
        if(color[i-1]=='B'){
            vector<int>temp;
            for(int j=0;j<G[i].size();j++){
                 if(color[G[i][j]-1]=='W')
                    temp.push_back(nodenum[G[i][j]]);
            }
            res+=solve(temp);
        }
    }
    cout<<res<<endl;
    return 0;
}

总结

本以为自己对并查集的掌握比较牢靠,但这道题还是没有做的出来,唉!这道题用并查集来做的思维还是比较独特。希望自己多多积累经验。

G. eli和字符串

题目链接

题目大意

给你一个只包含小写字母的字符串,求满足有\(k\)个相同字母的子串的最小长度。

解题思路

利用二维数组,分别统计\(26\)种字母的位置。如果每种字母的个数都小于\(k\),那么就不存在这样的字符串,输\(-1\)
对于每一种字母的情况,遍历每一行,\(i\)下标对应的值表示第\(1\)个字母出现的位置,\(i+k-1\)下标对应的值表示第\(k\)个字母出现的位置,维护区间最小值即可。

AC代码

#include<bits/stdc++.h>
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
vector<int>a[30];
int main()
{
    int n,k;
    cin>>n>>k;
    string str;
    cin>>str;
    for(int i=0;i<str.size();i++){
        a[str[i]-'a'].push_back(i);
    }
    int maxlen=0;
    for(int i=0;i<26;i++){
        int len = a[i].size();
        maxlen=max(len,maxlen);
    }
    if(maxlen<k){
        cout<<"-1"<<endl;
        return 0;
    }
    int res=2e5+10;
    // cout<<a[1][0]<<" "<<a[1][1]<<endl;
    for(int i=0;i<26;i++){
        if(a[i].size()<k)continue;
        for(int j=0;j<a[i].size()&&j+k<=a[i].size();j++){
            res = min(res,a[i][j+k-1]-a[i][j]+1);
        }
        // cout<<res<<endl;
    }
    cout<<res<<endl;
    return 0;
}

总结

简单的统计,没有什么难度。

H. nozomi和字符串

题目链接

题目大意

给你一个长度为\(n\)只包含\(01\)字符的字符串,拥有\(k\)次操作将字符\(0\)变为\(1\)或者将\(1\)改变为\(0\),问经过最多\(k\)次操作(\(k\)次机会可以不用完)之后字符相同的子串的最长长度。

解题思路

总体思路是贪心。先考虑\(k\)大于等于\(1\)的个数或者大于\(0\)的个数的情况,那么结果就是字符串的长度;另一种情况则统计每一个\(1\)的前缀\(1\)和后缀\(1\)的位置,然后遍历一遍,以\(start\)为起点,\(end\)为终点,贪心\(k\)个1的位置,将这\(k\)\(1\)都改变为\(0\),那么字符串区间为为下标\(end+1\)的值减去下标\(start-1\)的值再加\(1\)

AC代码

/*
    H题补题
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    string str;
    cin>>str;
    vector<int>v[2];
    v[0].push_back(-1);
    v[1].push_back(-1);
    for(int i=0;i<str.size();i++){
        if(str[i]=='0')
            v[0].push_back(i);
        else 
            v[1].push_back(i);
    }
    int res=0;
    if(v[0].size()-1<=k||v[1].size()-1<=k)res=n;
    for(int i=0;i<2;i++){
        for(int j=1;j<v[i].size()&&j+k<=v[i].size();j++){
            res=max(res,v[i][j+k]-v[i][j-1]-1);
        }
    }
    cout<<res<<endl;
    return 0;
}

总结

最开始在做这道题的时候想的太过于复杂,想到用动态规划去做,没有往贪心上靠。

I. nico和niconiconi

题目链接

题目大意

给你一个长度为\(n\)的字符串,其中"nico" 计\(a\)分,"niconi" 计\(b\)分,"niconiconi" 计\(c\)分,求出字符串最多能得多少分。(已经计算过的字符不能重复进行计算)

解题思路

利用动态规划的思想,\(dp[i]\)表示前\(i\)个字符的最大值,转移方程为:
\[ \begin{align} &if(i>=3\&\&substr(i-3,4)=nico)dp[i]=max(dp[i],dp[i-3]+a)\\ &if(i>=5\&\&substr(i-5,6)=niconi)dp[i]=max(dp[i],dp[i-5]+b)\\ &if(i>=9\&\&substr(i-9,10)=niconiconi)dp[i]=max(dp[i],dp[i-9]+c)& \end{align} \]

AC代码

#include<bits/stdc++.h>
const int maxn=3e5+10;
typedef long long ll;
using namespace std;
ll dp[maxn];
int main()
{
    int n,a,b,c;
    cin>>n>>a>>b>>c;
    string str;
    cin>>str;
    int len=str.size();
    dp[0]=0;
    for(int i=1;i<len;i++){
        dp[i]=dp[i-1];
        if(i>=3&&str.substr(i-3,4)=="nico")
            dp[i]=max(dp[i],dp[i-3]+a);
        if(i>=5&&str.substr(i-5,6)=="niconi")
            dp[i]=max(dp[i],dp[i-5]+b);
        if(i>=9&&str.substr(i-9,10)=="niconiconi")
            dp[i]=max(dp[i],dp[i-9]+c);
    }
    cout<<dp[len-1]<<endl;
    return 0;
}

总结

动态规划还是自己的弱点啊,根本没有想到这方面,其实理解之后还是蛮简单的,但就是当时看到这道题过题人数不是很多,给自己造成了心理压力,先入为主。