2020牛客寒假算法基础集训营1（全解）

此篇文章来自我的博客园，不过博客园有的时候会出些蜜汁BUG。当然，这个markdown编辑的博客也有这样那样的问题，总之各有优劣吧。。。
我的博客园地址：https://www.cnblogs.com/lonely-wind-/
此片文章地址：https://www.cnblogs.com/lonely-wind-/p/12261665.html
题目链接：https://ac.nowcoder.com/acm/contest/3002#question
emmm，没什么好说的，就是送人头了，
题目说明：
A.honoka和格点三角形 B.kotori和bangdream C.umi和弓道 D.hanayo和米饭
（计数问题）（水题计算）（卡精度题）（水题）

E.rin和快速迭代 F.maki和tree G.eli和字符串 H.nozomi和字符串
（暴力）（DFS遍历）（二分+前缀和）（二分+前缀和）

I.nico和niconiconi J.u's的影响力
（DP）（矩阵快速幂+数论）

A.honoka和格点三角形

没什么好说的，上图：
图片说明

以下是AC代码：

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

#define ll long long
const int mac=2e5+10;
const int inf=1e9+10;
const int mod=1e9+7;

int main()
{
    ll n,m;
    cin>>n>>m;
    ll a=((n-2)*n%mod*(m-1)%mod+(m-2)*m%mod*(n-1)%mod)%mod*2%mod;
    ll b=((m-2)*(n-1)%mod*n+(n-2)*(m-1)%mod*m)%mod*2%mod;
    ll c=((n-2)*(m-1)%mod+(m-2)*(n-1)%mod)%mod*4%mod;
    cout<<(a+b-c+mod)%mod<<endl;
    return 0;
}

B.kotori和bangdream

每个音符的得分期望是 $x$ ， $n$ 个音符的得分总期望就乘以 $n$ 好了
以下是AC代码：

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

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

C.umi和弓道

由于要计算挡板的最短长度，那么挡板一定是挡住了 $n-k$ 个，如果挡住了 $n-k$ 个以上，那么一定可以将挡板长度减少，所以我们判断 $n-k$ 就好了，又所有的点都不在坐标轴上就很好办了。首先确定umi所在位置的象限。很明显同一象限的点是不可能用挡板挡掉的，对于剩下的点找出线段和 $x$ 轴或 $y$ 轴的交点，统计坐标位置。

$kx_{1}+b=y_{1}$

$kx_{2}+b=y_{2}$

可得：

$b=\frac{y_{1}x_{2}-y_{2}x_{1}}{x_{2}-x_{1}}$ $k=\frac{y_{1}-y_{2}}{x_{1}-x_{2}}$

当交点是x轴的时候，我们令 $y=0$ ，那么 $x=-\frac{b}{k}$ ，交点是 $y$ 轴的时候就是 $b$ 了，然后我们交上去就会发现WA了。。。。

在WA了无数发之后我觉得已经没有什么能改的了，只有精度的问题了，那么在计算坐标点的时候我们尽量减少除法的使用，实际上 $x,y$ 轴的交点可以更快算出来：

我们知道斜率 $k=\frac{y_{1}-y_{2}}{x_{1}-x_{2}}$ 那么b的值就可以直接随便带个点去减了： $b=y_{0}-kx_{0}$

仿照b的求法，我们将式子同时除以 $k$ ： $x+\frac{1}{k}b=\frac{1}{k}y$ 那么令 $y_{0}=0$ 的时候 $x=-\frac{1}{k}b$ 而上面的式子我们又可以算出

$-\frac{1}{k}b=x_{0}-\frac{1}{k}y_{0}$ 那么答案也就出来了。我们减少了一次除法运算，只计算了一次k的值

然后我们分别对 $x,y$ 轴上的点进行循环取最小 $n-k$ 长度的大小。

以下是AC代码：

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

const int mac=1e5+10;
const double esp=1e-7;
const double inf=1e10+10;

double point_x[mac],point_y[mac];
int cntx,cnty;

int same(double x,double y,double x0,double y0)
{
    if (1.0*x/x0>0 && 1.0*y/y0>0) return 1;
    return 0;
}

int cross(double x,double y,double x0,double y0)//0->x,1->y,2->x,y
{
    if (1.0*x/x0<0 && 1.0*y/y0<0) return 2;
    else if (1.0*x/x0<0) return 1;
    else if (1.0*y/y0<0) return 0;
}

void deal(double x,double y,double x0,double y0,int pt)
{
    //y=kx+b
    //double k=1.0*(y-y0)/(x-x0);
    //double b=1.0*(y0*x-y*x0)/(x-x0);//刚开始int,y0*x会爆
    //double cross_x=-b/k;
    double b=y0-1.0*x0*(y-y0)/(x-x0);
    double cross_x=x0-1.0*y0*(x-x0)/(y-y0);
    if (pt==0) point_x[++cntx]=cross_x;
    else if (pt==1) point_y[++cnty]=b;
    else {
        point_x[++cntx]=cross_x;
        point_y[++cnty]=b;
    }
}

int main(int argc, char const *argv[])
{
    int n,k;
    double x0,y0;
    scanf ("%lf%lf",&x0,&y0);
    scanf ("%d%d",&n,&k);
    int len_num=n-k;
    for (int i=1; i<=n; i++){
        double x,y;
        scanf ("%lf%lf",&x,&y);
        if (same(x,y,x0,y0)) continue;
        int point=cross(x,y,x0,y0);//0代表交点在x,1代表在y,2代表x,y都有
        deal(x,y,x0,y0,point);//找出所有与x，y轴的交点
    }
    sort(point_x+1,point_x+1+cntx);
    sort(point_y+1,point_y+1+cnty);
    double ans=inf;
    for (int i=1; i+len_num-1<=cntx; i++){
        double len_len=point_x[i+len_num-1]-point_x[i];
        ans=min(ans,len_len);
    }
    for (int i=1; i+len_num-1<=cnty; i++){
        double len_len=point_y[i+len_num-1]-point_y[i];
        ans=min(ans,len_len);
    }
    if (fabs(ans-inf)<esp) printf("-1\n");
    else printf("%.8f\n",ans);
    return 0;
}

D.hanayo和米饭

没什么好说的，签到题，每个数标记一下，然后遍历输出没标记的那个数就可以了。
以下是AC代码：

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

const int mac=1e5+10;

int vis[mac];

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

E.rin和快速迭代

$10^{12}$ 看起来很多，实际上我们算因子的时候最多只需要循环 $10^{6}$ 次，而每次计算因子的时候都要开根号，所以直接暴力计算因子数所花费的时间并不是很多
以下是AC代码：

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

#define ll long long

int f(ll x)
{
    int ans=0;
    if (x==2) return ans;
    ans=1;
    int sum=0;
    ll m=sqrt(x);
    if (m*m==x) sum++,m--;
    for (int i=1; i<=m; i++){
        if (x%i==0) sum+=2;
    }
    return ans+f(sum);
}

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

F.maki和tree

经过一个黑点的路径有两种：两个端点都是白点；其中一个端点是黑点。
因此我们可以先预处理，将每个白点连通块上的白点个数统计出来。这样我们就可以得知每个黑点所连接的白点的权值（即连通块白点数）。
设某黑点连接了 k 个白点，第 i 个白点的权值为 f(i) 。
那么第一种路径的数量就是 $\sum_{i=1}^{k}\sum_{j=i+1}^{k}f(i)*f(j)$ 如图所示：
图片说明
2到其他的白点的有2-4,2-3,2-5,2-6,2-7
接下来就是4和5到其他白点，由于白块2已经遍历过了，所以往前找，那么就是2*（1+2）....
第二种就没什么好说的了，把所以的白点个数加起来就好了。
emmm，不知道为什么段错误。然后我把手动循环改成auto就可以了。。蜜汁BUG。注意答案要用long long，被坑了。。。
以下是AC代码：

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

const int mac=1e5+10;

vector<int>g[mac],blk[mac];
int mark[mac],root[mac],sz[mac];
char s[mac];

void dfs(int x,int fa)
{
    sz[x]=1;
    for (auto v:g[x]){
        if (v==fa) continue;
        dfs(v,x);
        sz[x]+=sz[v];
    }
}

int main(int argc, char const *argv[])
{
    int n;
    scanf ("%d",&n);
    scanf ("%s",s+1);
    int cnt=0;
    for (int i=1; i<=n; i++){
        mark[i]=s[i]=='B';
        if (mark[i]) root[++cnt]=i;
    }
    for (int i=1; i<n; i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if (mark[u] || mark[v]) {
            if (mark[u] && mark[v]) continue;
            if (mark[u]) blk[u].push_back(v);//黑点u的白儿子
            else blk[v].push_back(u);//黑点v的白儿子
            continue;
        }
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans=0;
    for (int i=1; i<=cnt; i++){
        int u=root[i];
        int sum=0;
        for (auto v:blk[u]){
            dfs(v,0);//以白儿子v为根进行遍历计算连通块v的大小
            sum+=sz[v];
        }
        ans+=sum;
        for (auto v:blk[u]){
            ans+=sz[v]*(sum-sz[v]);
            sum-=sz[v];
        }
    }
    printf("%d\n",ans);
    return 0;
}

G.eli和字符串

看一下题目。。。秒出二分，至于怎么求区间相同字母的个数，直接用前缀和就好了时间复杂度 $O(26n)$ 。加上二分的log就是 $O(logn*26n)$
以下是AC代码：

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

#define ll long long
const int mac=2e5+10;
const int inf=1e9+10;

char s[mac];
int dp[mac][30];

int ok(int x,int n,int k)
{
    for (int i=1; i+x-1<=n; i++){
        int p=-1;
        for (int j=0; j<='z'-'a'; j++){
            p=max(dp[i+x-1][j]-dp[i-1][j],p);
        }
        if (p>=k) return 1;
    }
    return 0;
}

int main()
{
    int n,k;
    scanf ("%d%d",&n,&k);
    scanf ("%s",s+1);
    int l=1,r=n,mid,ans=inf;
    for (int i=1; i<=n; i++)
        for (int j=0; j<='z'-'a'; j++){
            dp[i][j]=dp[i-1][j]+(s[i]=='a'+j);
        }
    while (l<=r){
        int mid=(l+r)>>1;
        if (ok(mid,n,k)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    if (ans==inf) printf("-1\n");
    else printf("%d\n",ans);
    return 0;
}

H.nozomi和字符串

这题也是一眼二分，和G题一样的，搞个前缀和维护一下就好了
以下是AC代码：

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

const int mac=2e5+10;

char s[mac];
int dp[mac][2];

int ok(int x,int k,int n)
{
    for (int i=1; i+x-1<=n; i++){
        if (dp[i+x-1][0]-dp[i-1][0]<=k) return 1;
        if (dp[i+x-1][1]-dp[i-1][1]<=k) return 1;
    }
    return 0;
}

int main()
{
    int n,k;
    scanf ("%d%d",&n,&k);
    scanf ("%s",s+1);
    for (int i=1; i<=n; i++){
        for (int j=0; j<=1; j++){
            dp[i][j]=dp[i-1][j]+(s[i]=='0'+j);
        }
    }
    int l=1,r=n,mid,ans=-1;
    while (l<=r){
        mid=(l+r)>>1;
        if (ok(mid,k,n)){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}

I.nico和niconiconi

这题一眼dp，状态转移也很好写：

$if (sbtring(i-3,i)==nico) dp[i]=max(dp[i],dp[i-4]+a)$

$if (sbtring(i-5,i)==niconi) dp[i]=max(dp[i],dp[i-6]+b)$

$if (sbtring(i-9,i)==niconiconi) dp[i]=max(dp[i],dp[i-10]+c)$

以下是AC代码：

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

#define ll long long

const int mac=3e5+10;

char s[mac];
ll dp[mac];
string s1,s2,s3;

int ok(int x,string ss)
{
    int len=ss.length();
    int cnt=0;
    if (x<len) return 0;
    for (int i=x-len+1; i<=x; i++){
        if (s[i]!=ss[cnt++]) return 0;
    }
    return 1;
}

int main(int argc, char const *argv[])
{
    int n,a,b,c;
    scanf ("%d%d%d%d",&n,&a,&b,&c);
    scanf("%s",s+1);
    s1="nico";s2="niconi";s3="niconiconi";
    for (int i=1; i<=n; i++){
        dp[i]=dp[i-1];
        if (ok(i,s1)) dp[i]=max(dp[i],dp[i-4]+a);
        if (ok(i,s2)) dp[i]=max(dp[i],dp[i-6]+b);
        if (ok(i,s3)) dp[i]=max(dp[i],dp[i-10]+c);
    }
    printf("%lld\n",dp[n]);
    return 0;
}

J.u's的影响力

这一题才是重头戏。。。

$f(i)=f(i-1)*f(i-2)*a^{b}$ ，其中 $f(1)=x,f(2)=y$ ，问 $f(n)$ 。重点是 $n,x,y,a,b<=10^{12}$ 。取模 $1e9+7$

我们可以先找规律：

$f(1)=x,f(2)=y,f(3)=xya^{b},f(4)=xy^{2}a^{2b}$

$f(5)=x^{2}y^{3}a^{4b},f(6)=x^{3}y^{5}a^{7b},f(7)=x^{5}y^{8}a^{12b}$

.....

很明显我们可以 $x,y,a$ 的幂是满足斐波那契数列的变形，

其中x和y的幂满足 $f(i)=f(i-1)+f(i-2)$ a的幂满足 $f(i)=f(i-1)+f(i-2)+b$

那么我们将每个幂算出来就好了（一个简单的矩阵快速幂）。。。。然后你们发现幂太大了，存不下（难道取模吗？）

。。。。幂如果取模的话好像有问题，不过注意这里的模数是 $1e9+7$ ，是个素数，我们根据费马小定理 $a^{p-1}\equiv 1(modp)$

那么有 $a^{1e9+6}\equiv 1(mod 1e9+7)$

也就是说我们可以直接对幂的 $（1e9+6）$ 取模。。。。好像不用欧拉降幂了

这里的矩阵也很简单 $x$ 的幂是 $f(1)=1,f(2)=0$ , $y$ 的幂是 $f(1)=0,f(2)=1$ , $a$ 的幂是 $f(1)=0,f(2)=0,f(3)=b$

那么三个矩阵也很好写出来了：
$图片说明$ 这是 $x$ 的幂
$图片说明$ 这是 $y$ 的幂
$图片说明$ 这是 $a$ 的幂
以下是AC代码：

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

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

int up;

struct Mat
{
    ll m[5][5];
    Mat(){memset(m,0,sizeof m);}
};

ll qick(ll a,ll b)
{
    ll ans=1;
    a%=mod;
    while (b){
        if (b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

Mat multi(Mat a,Mat b)
{
    Mat ans;
    for (int i=1; i<=up; i++)
        for (int j=1; j<=up; j++){
            for (int k=1; k<=up; k++){
                ans.m[i][j]+=a.m[i][k]*b.m[k][j]%(mod-1);
                ans.m[i][j]%=(mod-1);
            }
        }
    return ans;
}

Mat qick_mat(Mat a,ll n)
{
    Mat ans;
    for (int i=1; i<=up; i++) ans.m[i][i]=1;
    while (n){
        if (n&1) ans=multi(ans,a);
        a=multi(a,a);
        n>>=1;
    }
    return ans;
}

int main(int argc, char const *argv[])
{
    ll n,x,y,a,b;
    cin>>n>>x>>y>>a>>b;
    if (n==1){cout<<x%mod<<endl;return 0;}
    else if (n==2){cout<<y%mod<<endl;return 0;}
    else if (x%mod==0 || y%mod==0 || a%mod==0) {cout<<0<<endl;return 0;}//注意！！！
    else {
        up=2;
        Mat mx,star_mx;
        mx.m[1][1]=mx.m[1][2]=mx.m[2][1]=1;
        star_mx.m[2][1]=1;
        mx=qick_mat(mx,n-2);
        mx=multi(mx,star_mx);
        ll ans1=qick(x,mx.m[1][1]);
        //cout<<ans1<<endl;

        Mat my,star_my;
        my.m[1][1]=my.m[1][2]=my.m[2][1]=1;
        star_my.m[1][1]=1;
        my=qick_mat(my,n-2);
        my=multi(my,star_my);
        ll ans2=qick(y,my.m[1][1]);
        //cout<<ans2<<endl;

        up=3;
        Mat ma,star_ma;
        ma.m[1][1]=ma.m[1][2]=ma.m[1][3]=1;
        ma.m[2][1]=ma.m[3][3]=1;
        star_ma.m[1][1]=b%(mod-1);star_ma.m[2][1]=0;star_ma.m[3][1]=b%(mod-1);
        ma=qick_mat(ma,n-3);
        ma=multi(ma,star_ma);
        ll ans3=qick(a,ma.m[1][1]);
        //cout<<ans3<<endl;

        ll ans=(ans1*ans2%mod*ans3)%mod;
        cout<<ans<<endl;
    } 
    return 0;
}