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

比赛地址：https://ac.nowcoder.com/acm/contest/3002
比赛来源：2020牛客寒假算法基础集训营1

A honoka和格点三角形

思路：首先是样例中给出的 6 种三角形，其次还有 4 种三角形如下图：
图片说明

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod=1e9+7;

int main(){
    int n,m; scanf("%d%d",&n,&m); 
    ll ans;    
    ans=((1ll*(m-2)*(n-1)*6)%mod+(1ll*(n-2)*(m-1)*6)%mod)%mod;
    ans=(ans+((((1ll*(n-2)*(m-1))%mod)*(m-2))%mod)*2)%mod;//非特殊
    ans=(ans+((((1ll*(m-2)*(n-1))%mod)*(n-2))%mod)*2)%mod;//非特殊 
    ans=(ans+((((1ll*(n-1)*(m-2))%mod)*(m-3))%mod)*2)%mod;//非特殊 
    ans=(ans+((((1ll*(m-1)*(n-2))%mod)*(n-3))%mod)*2)%mod;//非特殊 
    printf("%lld\n",ans);
    return 0;
}

B kotori和bangdream

思路：签到题，直接计算即可。 $(x\%*a+(100-x)\%b)*n$

#include<bits/stdc++.h>
using namespace std;

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

D hanayo和米饭

$map$ 直接记录出现的数字，遍历查找未出现过得数字。

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
int a[maxn];
map<int,int>m;

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

E rin和快速迭代

思路：模板题，查找因子并且记录个数，注意点见代码。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll solve(ll n){
    ll cnt1=0;
    while(n!=2){
        ll cnt=0; cnt1++;
        for(long long i=1;i*i<=n;i++){//sqrt(n)会出错
            if(n%i==0){
                if(i*i==n) cnt++;
                else cnt+=2;
            }
        }
        n=cnt;
    }
    return cnt1;
}

int main(){
    ll n; scanf("%lld",&n);
    ll cnt=solve(n);
    printf("%lld\n",cnt);
    return 0;
}

F maki和tree

思路：满足题意的情况为黑点在路径中间和黑点是端点的情况，我们用并查集可以先预处理出每一个白点连通块并且记录每一个连通块中白点的数量。黑点是端点的情况我们直接加与这个点连接的连通块的白点的个数，在中间的情况见下图。
图片说明
2 和 3 到 1 的路径，3 到 2 的路径。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e5+10;
char str[maxn];
int cnt=0,head[maxn],f[maxn],size[maxn];

struct Edge{
    int u,v,next;
}edge[maxn<<1];

void addedge(int u,int v){
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

int Find(int v){
    if(f[v]==v) return v;
    else return f[v]=Find(f[v]);    
}

void Merge(int u,int v){
    int t1=Find(u),t2=Find(v);
    if(t1!=t2){
        f[t1]=t2;//t1的父节点为t2 
        size[t2]+=size[t1];
    }
}

int main(){
    int n; scanf("%d",&n);
    scanf("%s",str+1);
    for(int i=1;i<=n;i++){
        size[i]=(str[i]=='W'); 
        f[i]=i; head[i]=-1;
    }
    for(int i=1;i<=n-1;i++){
        int u,v; scanf("%d%d",&u,&v);
        addedge(u,v); addedge(v,u);
        if(str[u]==str[v]&&str[u]=='W') Merge(u,v);//预处理出所有的白色连通块 
    }
    //for(int i=1;i<=n;i++) cout<<size[i]<<" "; cout<<endl;
    ll sum=0;
    for(int i=1;i<=n;i++){
        if(str[i]=='B'){
            ll cnt1=0;
            for(int j=head[i];j!=-1;j=edge[j].next) cnt1+=(ll)size[Find(edge[j].v)];//端点 
            sum+=cnt1;
            for(int j=head[i];j!=-1;j=edge[j].next){//中间 
                cnt1-=(ll)size[Find(edge[j].v)];
                sum+=1ll*cnt1*size[Find(edge[j].v)];
            }
        }
    } 
    printf("%lld\n",sum);
    return 0;
}

G eli和字符串

思路：直接二分长度，然后判断此长度下的子字符串中每一个字符出现的次数。如果满足题意，那么再找是否有更短的字符串；若不满足题意，就找更长的字符串。

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;
char str[maxn];
int cnt[30],n,k;

bool check(int len){
    for(int i=0;i<30;i++) cnt[i]=0;
    for(int i=0;i<len;i++){
        cnt[str[i]-'a']++;
        if(cnt[str[i]-'a']==k) return true;
    } 
    for(int i=len;i<n;i++){
        cnt[str[i-len]-'a']--; cnt[str[i]-'a']++;
        if(cnt[str[i]-'a']==k) return true;
    }
    return false;
}

int main(){
    scanf("%d%d",&n,&k);
    scanf("%s",str);
    int l=1,r=n,ans=-1; 
    while(l<=r){
        int mid=l+(r-l)/2;
        if(check(mid)){
            r=mid-1;
            ans=mid;
        }else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

H nozomi和字符串

思路：同 G ，二分长度，记录此长度下，每一个子串 0 1 的个数，如果小的那个小于等于 k，则满足题意，再找是否存在更长的字符串，否则答案可能更短。

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;
char str[maxn];
int cnt[2],n,k;

bool check(int len){
    cnt[0]=cnt[1]=0;
    for(int i=0;i<len;i++) cnt[str[i]-'0']++;
    for(int i=0;i<len;i++){
        if(min(cnt[0],cnt[1])<=k) return true;
    }
    for(int i=len;i<n;i++){
        cnt[str[i-len]-'0']--; cnt[str[i]-'0']++;
        if(min(cnt[0],cnt[1])<=k) return true;
    }
    return false;
}

int main(){
    scanf("%d%d",&n,&k);
    scanf("%s",str);
    int l=1,r=n,ans=0;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(check(mid)){
            l=mid+1;
            ans=mid;
        }else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}

I nico和niconiconi

思路： $dp[i]$ 表示截止到当前字符最大的计分分数。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=3e5+20;
ll dp[maxn];
string str;

int main(){
    int n,a,b,c; cin>>n>>a>>b>>c;
    cin>>str;
    for(int i=1;i<n;i++){
        dp[i]=max(dp[i],dp[i-1]);
        if(i>=3&&str.substr(i-3,4)=="nico") dp[i]=max(dp[i],dp[i-3]+(ll)a);
        if(i>=5&&str.substr(i-5,6)=="niconi") dp[i]=max(dp[i],dp[i-5]+(ll)b);
        if(i>=9&&str.substr(i-9,10)=="niconiconi") dp[i]=max(dp[i],dp[i-9]+(ll)c);
    }
    printf("%lld\n",dp[n-1]);
    return 0;
}