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

A.honoka和格点三角形

分析：这题需要分3种情况来讨论。

• 2条边都与坐标轴平行的三角形

  一定存在于或者的矩形中，每个当中存在4个，则只需要统计矩形的数量即可

• 底与坐标轴平行的三角形，且底为2

• 底与坐标轴平行的三角形，且底为1

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
LL n,m;
int main()
{
    cin>>n>>m;
    LL sum=0;
    sum=(sum+(4ll*(n-1)*(m-2)%mod+(4ll*(m-1)*(n-2)%mod))%mod)%mod;
    sum=(sum+((2ll*(m-1)*(n-2)%mod*(n-2)%mod)%mod+(2ll*(n-1)*(m-2)%mod*(m-2)%mod)%mod)%mod)%mod;
    sum=(sum+((2ll*(m-2)*(n-1)%mod*(n-2)%mod)%mod+(2ll*(n-2)*(m-1)%mod*(m-2)%mod)%mod)%mod)%mod;
    cout<<sum<<endl;
    return 0;

}

B.kotori和bangdream

#include "bits/stdc++.h"
using namespace std;
int n,x,a,b;
int main()
{
    scanf("%d%d%d%d",&n,&x,&a,&b);
    int tmp=n*(x*a+((100-x)*b));
    printf("%.2f\n",(double)tmp/100.0);
    return 0;
}

C.umi和弓道

分析：首先如果在同一象限内的，隔板无法分开。如果处于不同象限，我们则分别求出每个点与X轴和与Y轴的交点，然后使得挡板能够挡住n-k个点即可，于是可以通过双指针来求min值

#include "bits/stdc++.h"
using namespace std;
int n,k;
int main()
{
    double x0,y0;
    cin>>x0>>y0;
    cin>>n>>k;
    k=n-k;
    vector<double>v1,v2;
    for(int i=1;i<=n;i++){
        double x,y;
        cin>>x>>y;
        if(x*x0<0){
            v1.push_back(y0-x0*(y-y0)/(x-x0));
        }
        if(y*y0<0){
            v2.push_back(x0-y0*(x-x0)/(y-y0));
        }
    }
    double mi=1e18;
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    if(v1.size()>=k){
        int head=0,tail=k-1;
        while(tail<v1.size()){
            mi=min(mi,v1[tail]-v1[head]);
            head++,tail++;
        }
    }
    if(v2.size()>=k){
        int head=0,tail=k-1;
        while(tail<v2.size()){
            mi=min(mi,v2[tail]-v2[head]);
            head++,tail++;
        }
    }
    if(mi==1e18) printf("-1\n");
    else printf("%.6f\n",mi);
    return 0;
}

D.hanayo和米饭

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e5+100;
int n,a[maxn],vis[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++){
        scanf("%d",&a[i]);
        vis[a[i]]=1;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            printf("%d\n",i);
            return 0;
        }
    }
}

E.rin和快速迭代

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
LL n;
LL solve(LL a){
    if(a==2ll) return 2ll;
    LL tmp=2;
    for(LL i=2;i*i<=a;i++){
        if(i*i==a){
            tmp++;
        }else{
            if(a%i==0) tmp+=2;
        }
    }
    return tmp;
}
int main()
{
    scanf("%lld",&n);
    int cnt=0;
    while(n!=2){
        cnt++;
        n=solve(n);
    }
    printf("%d\n",cnt);
    return 0;
}

F.maki和tree

分析：如果我们以黑色结点为跟结点节点，则假设它的子树中白色结点数量分别为，则总的方案数为，化简一下，即为

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+100;
char s[maxn];
int n;
vector<int>g[maxn];
LL sum;
void dfs(int u,int fa){
    if(s[u]=='B') return;
    sum++;
    for(auto v:g[u]){
        if(v!=fa) dfs(v,u);
    }
}
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    LL ans=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='B'){
            LL res1=0,res2=0;
            for(auto v:g[i]){
                sum=0;
                dfs(v,v);
                ans+=sum;
                res1+=sum;
                res2+=sum*sum;
            }
            ans+=(res1*res1-res2)/2;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

G.eli和字符串

分析：依次记录每个字母出现的位置，同时维护k个该字母长度的最小值。

#include "bits/stdc++.h"
using namespace std;
const int maxn=27;
vector<int>g[maxn];
int v[maxn];
int n,k;
string s;
int main()
{
    cin>>n>>k;
    cin>>s;
    int len=s.length();
    for(int i=0;i<26;i++) v[i]=INT_MAX;
    for(int i=0;i<len;i++){
        int tmp=s[i]-'a';
        g[tmp].push_back(i+1);
        if(g[tmp].size()>=k){
            int l=g[tmp].size()-1;
            int mi=g[tmp][l]-g[tmp][l-k+1]+1;
            v[tmp]=min(v[tmp],mi);
        }
    }
    int mx=INT_MAX;
    for(int i=0;i<26;i++){
        mx=min(mx,v[i]);
    }
    if(mx==INT_MAX) printf("-1\n");
    else printf("%d\n",mx);
    return 0;
}

H.nozomi和字符串

分析：通过维护前缀和来快速维护区间中1和0的数量，然后分别计算把0改为1和把1改为0所能维护的最长序列即可

#include "bits/stdc++.h"
using namespace std;
const int maxn=2e5+100;
int n,k,a[maxn],b[maxn],dp1[maxn],dp2[maxn];
string s;
int main()
{
    scanf("%d%d",&n,&k);
    cin>>s;
    for(int i=1;i<=n;i++){
        a[i]=s[i-1]-'0';
        b[i]=1-a[i];
        dp1[i]=dp1[i-1]+a[i];
        dp2[i]=dp2[i-1]+b[i];
    }
    int l=1,r=1,mx=0;
    while(r<=n&&l<=r){
        while(dp1[r]-dp1[l-1]<=k&&r<=n) r++;
        mx=max(mx,r-l);
        //cout<<mx<<endl;
        l++;
    }
    l=1,r=1;
    while(r<=n&&l<=r){
        while(dp2[r]-dp2[l-1]<=k&&r<=n) r++;
        mx=max(mx,r-l);
        //cout<<mx<<endl;
        l++;
    }
    printf("%d\n",mx);
    return 0;
}

I.nico和niconiconi

分析：这个是一个比较简单的DP，分别从"nico"，"niconi"，"niconiconi" 三个位置转移过来求最大值即可

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

J.u's的影响力

分析：这个题目出得非常有意思，咋一看上去不知道怎么矩阵快速幂，但仔细思考后，发现是可以构造矩阵进行快速幂的。在这里我们应该和的幂次做矩阵快速幂。我们推一下出现的次数，可知其实一个前2项为的斐波拉契数列。同理，我们可以推出的出现次数是一个前2项为的斐波拉契数列。我们再做进一步推理可以发现，的第项，就是的第项。同时，的第n项就是。最后由于指数比较大，同时右由于是个素数，所以我们很自然可以想到用费马小定理来进行降幂，即当为素数时，。

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
LL n,x,y,a,b;
void mul(LL f[2],LL res[2][2]){
    LL c[2];
    memset(c,0,sizeof(c));
    for(int j=0;j<2;j++){
        for(int k=0;k<2;k++)
            c[j]=(c[j]+f[k]*res[k][j])%(mod-1);
    }
    memcpy(f,c,sizeof(c));
}
void mulself(LL res[2][2]){
    LL c[2][2];
    memset(c,0,sizeof(c));
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                c[i][j]=(c[i][j]+res[i][k]*res[k][j])%(mod-1);
            }
        }
    }
    memcpy(res,c,sizeof(c));
}
LL quick(LL a,LL b){
    LL res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res%mod;
}
int main()
{
    cin>>n>>x>>y>>a>>b;
    if(n==1){
        cout<<x%mod<<endl;
        return 0;
    }
    if(n==2){
        cout<<y%mod<<endl;
        return 0;
    }
    if(x%mod==0||y%mod==0||a%mod==0){
        cout<<"0"<<endl;
        return 0;
    }
    x%=mod,y%=mod,a%=mod;
    a=quick(a,b);
    LL f[2]={1,0};
    LL res[2][2]={{0,1},{1,1}};
    n--;
    for(;n;n>>=1){
        if(n&1) mul(f,res);
        mulself(res);
    }
    LL tmp1=quick(x,f[0]);
    LL tmp2=quick(y,f[1]); 
    LL tmp3=quick(a,f[0]+f[1]-1);
    cout<<((tmp1*tmp2)%mod*tmp3)%mod<<endl;
    return 0;
}