2020牛客寒假算法基础集训营1 J题可以回顾回顾

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

这套题整体来说还是很简单的。

A.honoka和格点三角形

这个题目不是很难，不过要考虑周全，面积是1，那么底边的长度可以是1也可以是2，

注意底边1和2会有重复的，所以要注意去除这个重复部分的。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+;
typedef long long ll;
const int mod=1e9+;
int main(){
    ll n,m,ans=;
    scanf("%lld%lld",&n,&m);
    ans=*(m-)%mod*m%mod*(n-)%mod;
    ans+=*(n-)%mod*n%mod*(m-)%mod;
    ans+=*(m-)%mod*(m-)%mod*(n-)%mod;
    ans+=*(n-)%mod*(n-)%mod*(m-)%mod;
    ans%=mod;
    printf("%lld\n",ans);
    return ;
}

A

B.kotori和bangdream

这个题目也很简单，因为每一个音符的概率都是确定的。。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+;
typedef long long ll;

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

B

C.umi和弓道

这个可能看起来稍微复杂一点，不过整体还是很简单，

把所有可以投影到y轴的投影到y轴，可以投影到x轴的投影到x轴。

然后排个序，求长度最短的n-k个点。

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+;
typedef long long ll;
long double dx[maxn],dy[maxn];
long double x[maxn],y[maxn];
int judge(ll x,ll y){
    if(x>&&y>) return ;
    if(x<&&y>) return ;
    if(x<&&y<) return ;
    if(x>&&y<) return ;
}
int main(){
    ll n,k;
    long double x0,y0;
    scanf("%Lf%Lf%lld%lld",&x0,&y0,&n,&k);
    int f=judge(x0,y0);
    int num=,numx=,numy=;
    for(int i=;i<=n;i++){
        scanf("%Lf%Lf",&x[i],&y[i]);
        int ans=judge(x[i],y[i]);
        if(ans==f) num++;
        else if(x0*x[i]>) numx++;
        else if(y0*y[i]>) numy++;
    }
    if(num+numx>k&&num+numy>k){
        printf("-1\n");
        return ;
    }
    int cntx=,cnty=;
    for(int i=;i<=n;i++){
        if(x[i]*x0<){
//            cout<<"i="<<i<<" x[i]="<<x[i]<<" y[i]="<<y[i]<<endl;
            dy[++cnty]=(y0-y[i])/(x0-x[i])*(-x0)+y0;
//            printf("dy[%d]=%Lf\n",cnty,dy[cnty]);
        }
        if(y0*y[i]<){
            dx[++cntx]=(x0-x[i])/(y0-y[i])*(-y0)+x0;
        }
    }
    int res=n-k;
    sort(dy+,dy++cnty);
    sort(dx+,dx++cntx);
    long double ans=2e9;
    for(int i=res;i<=cntx;i++){
//        printf("dx[%d]=%Lf\n",i,dx[i]);
        ans=min(ans,dx[i]-dx[i-res+]);
    }
    for(int i=res;i<=cnty;i++){
//        printf("dy[%d]=%Lf dy[%d]=%Lf\n",i,dy[i],i-res+1,dy[i-res+1]);
        ans=min(ans,dy[i]-dy[i-res+]);
    }
    printf("%.6Lf\n",ans);
    return ;
}

C

D.hanayo和米饭

这个太签到了

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+;
typedef long long ll;

int vis[maxn];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=;i<n;i++){
        int x;
        scanf("%d",&x);
        vis[x]=;
    }
    for(int i=;i<=n;i++){
        if(!vis[i]){
            printf("%d\n",i);
            return ;
        }
    }
}

D

E.rin和快速迭代

这个题目f函数其实求的就是约数的个数，这个还是很好求的，

把这个数唯一分解，x=p1^a1*p2^a2*....*pn^an

那么这个数的约数的个数就是 num=(a1+1)*(a2+1)*...*(an+1)

这个就暴力求就可以了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+;
typedef long long ll;
const int mod=1e9+;
ll v[maxn],isp[maxn],m;
void init1()
{
    for(int i=;i<maxn;i++){
        if(v[i]==){
            isp[m++]=i;
            v[i]=i;
        }
        for(int j=;j<m;j++){
            if(v[i]<isp[j]||i*isp[j]>maxn) break;
            v[i*isp[j]]=isp[j];
        }
    }
}
ll judge(ll x){
    ll ans=,p=;
    for(int i=;i<m;i++){
        while(x%isp[i]==){
//            printf("isp[%d]=%d\n",i,isp[i]);
            p++,x/=isp[i];
        }
        ans*=p,p=;
        if(x==) break;
    }
    if(x>) ans*=;
//    printf("x=%lld ans=%lld\n",x,ans);
    return ans;
}

int main(){
    init1();
    ll n,res=;
    scanf("%lld",&n);
    while(n>) n=judge(n),res++;
    printf("%lld\n",res);
    return ;
}

E

F.maki和tree

这个题目我觉得我写的挺复杂的，

我是先预处理出白色块的连通块。

然后对于每一个黑块去枚举它周围的白色连通块。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+;
typedef long long ll;
struct node{
    int v,nxt;
    node(int v=,int nxt=):v(v),nxt(nxt){}
}e[maxn*];
int head[maxn],cnt;
void add(int u,int v){
    e[++cnt]=node(v,head[u]);
    head[u]=cnt;
    e[++cnt]=node(u,head[v]);
    head[v]=cnt;
}
int f[maxn],sum[maxn];
char s[maxn];
void dfs(int u,int pre){
    f[u]=pre,sum[u]=;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==pre) continue;
        dfs(v,u);
        if(s[u]!='B'&&s[v]!='B') sum[u]+=sum[v];
    }
}
void dfs1(int u,int pre){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==pre) continue;
        if(s[u]!='B'&&s[v]!='B') sum[v]=max(sum[v],sum[u]);
        dfs1(v,u);
    }
}
ll ans=;
void dfsans(int u,int pre){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==pre) continue;
        dfsans(v,u);
    }
    if(s[u]!='B') return ;
    ll all=;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(s[v]=='B') continue;
        all+=sum[v];
        ans-=sum[v]*(sum[v]-)/;
    }
    ans+=all*(all-)/;
}
int main(){
    int n;
    scanf("%d%s",&n,s+);
    for(int i=;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    dfs(,-),dfs1(,-);
    dfsans(,-);
    printf("%lld\n",ans);
}

F

G.eli和字符串

这个题目很简单，直接暴力枚举26个字母即可。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2e5+;
typedef long long ll;
char s[maxn];
int num[],pos[][maxn];
int main(){
    int n,k;
    scanf("%d%d%s",&n,&k,s+);
    int slen=strlen(s+);
    for(int i=;i<=slen;i++){
        int x=s[i]-'a';
        num[x]++;
        pos[x][num[x]]=i;
    }
    int ans=inf;
    for(int i=;i<;i++){
        if(num[i]<k) continue;
        int cnt=;
        for(int j=k;j<=num[i];j++) ans=min(ans,pos[i][j]-pos[i][j-k+]+);
    }
    if(ans>=inf) ans=-;
    printf("%d\n",ans);
    return ;
}

G

H.nozomi和字符串

这个是一个二分，二分最大长度即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+;
typedef long long ll;
const int mod=1e9+;
char s[maxn];
int n,k,slen;
int num[][maxn];
bool check(int x){
    for(int i=x;i<=slen;i++){
        int len0=num[][i]-num[][i-x];
        int len1=num[][i]-num[][i-x];
        if(len0<=k||len1<=k) return true;
    }
    return false;
}
int main(){
    scanf("%d%d%s",&n,&k,s+);
    slen=strlen(s+);
    for(int i=;i<=slen;i++){
        num[][i]=num[][i-];
        num[][i]=num[][i-];
        num[s[i]-''][i]++;
    }
    int l=,r=n,ans=;
    while(l<=r){
        int mid=(l+r)>>;
        if(check(mid)) ans=mid,l=mid+;
        else r=mid-;
    }
    printf("%d\n",ans);
    return ;
}

H

I.nico和niconiconi

这个是一个dp，注意细节的处理。

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+;
typedef long long ll;
char cur[]={'n','i','c','o'},s[maxn];
ll dp[maxn];
int main(){
    ll n,a,b,c;
    scanf("%lld%lld%lld%lld%s",&n,&a,&b,&c,s+);
    for(int i=;i<=n;i++){
        dp[i]=max(dp[i-]+a,dp[i]);
        if(i>=) dp[i]=max(dp[i],dp[i-]+b);
        if(i>=) dp[i]=max(dp[i],dp[i-]+c);
    }
    ll ans=;
    int num=,pos=,slen=strlen(s+);
    s[++slen]='~';
    for(int i=;i<=slen;i++){
        if(s[i]==cur[pos]) {
            pos++;
            if(pos==) num++,pos=;
        }
        else{
            ll res=dp[num];
            if(pos>=){
                if(num>=) res=max(dp[num-]+b,res);
                if(num>=) res=max(dp[num-]+c,res);
            }
            ans+=res,num=,pos=;
            if(s[i]==cur[pos]) pos++;
        }
    }
    printf("%lld\n",ans);
    return ;
}
/*
19 1 2 5
niconiconiniconico
*/

I

J.u's的影响力

这个推一下就会发现，x和y的指数都是斐波那契数列的一项，a^b的指数是斐波那契数列的前缀和。

所以都可以用矩阵快速幂解决，斐波那契数列前缀和也可以用矩阵快速幂解决。

推荐资料：大斐波拉契数列及斐波拉契前缀和(m阶前缀和)求解

斐波那契数列总(这个挺好的）

但是这个还有几个点需要注意，第一个：斐波那契数列求的是指数，所以不可以直接对mod取模，而是要对mod-1取模，因为费马小定理。

a^p-1 mod p == 1 所以只可以对p-1取模。

第二个就是a是p的倍数时，不满足费马小定理，这个要分开考虑。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const long long mod = 1e9+;

int UP;
struct mat
{
    long long mn[][];
    mat() {
        for(int i = ;i<UP;i++) {
            for(int j = ;j<UP;j++) {
                mn[i][j]=;
            }
        }
        for(int i = ;i<UP;i++) {
            mn[i][i] = ;
        }
    }
    void init(){
        for(int i=;i<UP;i++){
            for(int j=;j<UP;j++){
                mn[i][j]=;
            }
        }
    }
   mat operator * (const mat& a) {
        mat res;
        for(int i = ;i<UP;i++) {
            res.mn[i][i] = ;
        }
        for(int i=;i<UP;i++) {
            for(int j=;j<UP;j++) {
                for(int k=;k<UP;k++) {
                    res.mn[i][j] += mn[i][k]*a.mn[k][j]%(mod-);
                    res.mn[i][j] %= (mod-);
                }
            }
        }
        return res;
    }
};

mat fast(mat a,long long c) {
    mat res = mat();
    while(c) {
        if(c&) res  = res * a;
        a = a*a;
        c >>= ;
    }
    return res;
}
ll quick_mul(ll a,ll b,ll mod)
{
    ll ans = ;
    while(b)
    {
        if (b & ) ans = (ans + a) % mod;
        a = (a + a) % mod;
        b >>= ;
    }
    return ans;
}

ll quick_pow(ll a,ll b,ll mod)
{
    ll ans = ;
    while(b)
    {
        if (b & ) ans = quick_mul(ans, a, mod);
        a = quick_mul(a, a, mod);
        b >>= ;
    }
    return ans;
}
int main(){
    UP=;
    ll n,x,y,a,b;
    scanf("%lld%lld%lld%lld%lld",&n,&x,&y,&a,&b);
    if(n==) {
        printf("%lld\n",x%mod);
        return ;
    }
    if(n==){
        printf("%lld\n",y%mod);
        return ;
    }
    if(x%mod==||y%mod==||a%mod==){
        printf("0\n");
        return ;
    }
    mat res;res.init();
    res.mn[][]=,res.mn[][]=res.mn[][]=res.mn[][]=;
    res=fast(res,n-);
    x=quick_pow(x,res.mn[][],mod);
    y=quick_pow(y,res.mn[][],mod);
    a%=mod,a=quick_pow(a,b,mod);
    UP=,res.init();
    res.mn[][]=res.mn[][]=res.mn[][]=;
    res.mn[][]=res.mn[][]=res.mn[][]=;
    res=fast(res,n-);
    a=quick_pow(a,res.mn[][]+res.mn[][],mod);
    printf("%lld\n",quick_mul(quick_mul(a,x,mod),y,mod));
    return ;
}

J