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

题目链接

J. u’s的影响【矩阵快速幂+欧拉降幂】

首先，先推出前几项：
$1:x$1:x
$2:y$2:y
$3:xy{a}^b$3:xyab
$4:x{y}^2{a}^{2b}$4:xy2a2b
$5:x^2{y}^3{a}^{4b}$5:x2y3a4b
$6:x^3{y}^5{a}^{7b}$6:x3y5a7b
可以发现规律：
$\left(1\right)x的指数：1,0,1,1,2,\mathrm{3...}$(1)x的指数：1,0,1,1,2,3...
$\left(2\right)y的指数：0,1,1,2,3,\mathrm{5...}$(2)y的指数：0,1,1,2,3,5...
$x$x 的指数递推式：
f(i)=⎩⎪⎨⎪⎧​10f(i−1)+f(i−2)​i=1i=2i≥3​
$y$y 的指数递推式：
f(i)=⎩⎪⎨⎪⎧​01f(i−1)+f(i−2)​i=1i=2i≥3​
$\left(3\right)a的指数中b前面的系数：0,0,1,2,4,7,...$(3)a的指数中b前面的系数：0,0,1,2,4,7,...
递推式：
f(i)=⎩⎪⎨⎪⎧​00f(i−1)+f(i−2)+1​i=1i=2i≥3​
$x$x 的指数的构造矩阵如下：
⎣⎡​00​10​⎦⎤​∗⎣⎡​11​10​⎦⎤​(n−2)=⎣⎡​f(n)0​f(n−1)0​⎦⎤​
同理可以构造出 $y$y 的指数的构造矩阵：

⎣⎡​10​00​⎦⎤​∗⎣⎡​11​10​⎦⎤​(n−2)=⎣⎡​f(n)0​f(n−1)0​⎦⎤​
$a$a 的指数中 $b$b 前面的系数的构造矩阵：
⎣⎡​000​000​100​⎦⎤​∗⎣⎡​111​100​001​⎦⎤​(n−2)=⎣⎡​f(n)00​f(n−1)00​100​⎦⎤​
观察以上矩阵可以发现当n足够大时，各个指数是很大的。
所以根据欧拉定理： $a^{\phi \left(p\right)}=1\left(mod\hspace{0.25em} p\right)$aφ(p)=1(modp)
可以对指数进行降幂，即欧拉降幂。
因为 $p=1e9+7$p=1e9+7 为素数，即 $\phi \left(p\right)=p-1$φ(p)=p−1，所以在用矩阵快速幂计算指数时，可以对 $(p-1)$(p−1) 进行取模，即进行欧拉降幂。
但是应用<mark>欧拉降幂时要注意 $a$a 和 $p$p 是否互质</mark>。
ab=⎩⎪⎨⎪⎧​ab%φ(p)(modp)ab(modp)ab%φ(p)+φ(p)(modp)​a和p互质b<φ(p)b≥φ(p)​
为了避免这种情况，求出指数后，进行快速幂计算值时，记得对指数都进行 $b\%\phi \left(p\right)+\phi \left(p\right)$b%φ(p)+φ(p)的操作。
  <mark>本问题中还要注意的是</mark>，底数的范围是 $1e12$1e12，所以进行快速幂之前要对底数取模 $p$p,否则容易<mark>爆 $longlong$longlong</mark>。并且计算 $a$a 的指数时，注意 $b$b 的范围是 $1e12$1e12 ，其系数的范围是 $1e9$1e9，二者相乘可能<mark>爆 $longlong$longlong</mark>。可以先求 $a$a的 $b$b 系数次幂，再求 $b$b 次幂。

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+6;
const int p=1e9+7;
typedef long long ll;
struct matrix
{
    ll mat[5][5];
    matrix operator *(const matrix b)const
    {
        matrix res;
        memset(res.mat,0,sizeof(res.mat));
        for(int i=1;i<=4;i++)
        {
            for(int k=1;k<=4;k++)
            {
                if(mat[i][k]>0)
                    for(int j=1;j<=4;j++)
                        res.mat[i][j]=(res.mat[i][j]+mat[i][k]*b.mat[k][j]%mod)%mod;
            }
        }
        return res;
    }
};
matrix mpow(matrix a,ll b)
{
    matrix res;//单位阵
    memset(res.mat,0,sizeof(res.mat));
    for(int i=1;i<=4;i++)
            res.mat[i][i]=1;
    while(b)
    {
        if(b&1)
            res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
ll power(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res%p;
}
void init1(matrix &a)
{
    memset(a.mat,0,sizeof(a.mat));
    a.mat[1][2]=1;
}
void init2(matrix &a)
{
    memset(a.mat,0,sizeof(a.mat));
    a.mat[1][1]=1;
}
void init3(matrix &a)
{
    memset(a.mat,0,sizeof(a.mat));
    a.mat[1][3]=1;
}
void initB1(matrix &b)
{
    memset(b.mat,0,sizeof(b.mat));
    b.mat[1][1]=1;
    b.mat[1][2]=1;
    b.mat[2][1]=1;
}
void initB2(matrix &b)
{
    memset(b.mat,0,sizeof(b.mat));
    b.mat[1][1]=1;
    b.mat[1][2]=1;
    b.mat[2][1]=1;
    b.mat[3][1]=1;
    b.mat[3][3]=1;
}
int main()
{
    ll n,x,y,a,b;
    scanf("%lld%lld%lld%lld%lld",&n,&x,&y,&a,&b);
    if(n==1)
    {
        printf("%lld\n",x%p);
        return 0;
    }
    if(n==2)
    {
        printf("%lld\n",y%p);
        return 0;
    }
    matrix A1,A2,A3,B1,B2;
    init1(A1);
    init2(A2);
    init3(A3);
    initB1(B1);
    initB2(B2);
    matrix t1=A1,t2=A2,t3=A3;
    if(n>2)
    {
        t1=A1*mpow(B1,n-2);
        t2=A2*mpow(B1,n-2);
        t3=A3*mpow(B2,n-2);
    }
    ll nx=t1.mat[1][1]%mod+mod;//cout<<nx%mod<<endl;
    ll ny=t2.mat[1][1]%mod+mod;//cout<<ny%mod<<endl;
    ll na=t3.mat[1][1]%mod+mod;//cout<<na%mod<<endl;
    ll ans=power(x%p,nx)*power(y%p,ny)%p*power(power(a%p,b),na)%p;
    printf("%lld\n",ans);
    return 0;
}

C. umi和弓道

  首先，判断象限。同象限肯定不能阻挡。其次，x坐标字符相同的点，只有放在x轴上才能阻挡，y坐标相同的，同理。把各点和人坐标连线，求出与坐标轴交点，注意斜率为0和不存在。分别对x轴和y轴的点用两个指针固定距离扫描，求出最小。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> P;
const int N=1e5+5;
const ll inf=4e9+5;
const double eps=1e-6;
ll x[N],y[N];
P dx[N],dy[N];
int main()
{
    int n,k,xx=0,yy=0,cntx=0,cnty=0,tp=0,nx=0,ny=0;
    scanf("%lld%lld",&x[0],&y[0]);
    if(x[0]>0)
        xx=1;
    else if(x[0]<0)
        xx=-1;
    if(y[0]>0)
        yy=1;
    else if(y[0]<0)
        yy=-1;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&x[i],&y[i]);
        if(x[i]*xx>0&&y[i]*yy>0)//同象限
            tp++;
        else
        {
            if(x[i]*xx>0)//放在x轴上能阻挡，y轴不能
            {
                if(x[i]==x[0])
                {
                    dx[++cntx].first=1.0*x[i];
                    dx[cntx].second=i;
                }
                else
                {
                    double kt=1.0*(y[i]-y[0])/(x[i]-x[0]);
                    double tx=-1.0*y[0]/kt+x[0];
                    dx[++cntx].first=tx;
                    dx[cntx].second=i;
                }
                nx++;
            }
            else if(y[i]*yy>0)//放在y轴上能阻挡，x轴不能
            {
                if(y[i]==y[0])
                {
                    dy[++cnty].first=1.0*y[i];
                    dy[cnty].second=i;
                }
                else
                {
                    double kt=1.0*(y[i]-y[0])/(x[i]-x[0]);
                    double ty=-kt*x[0]+y[0];
                    dy[++cnty].first=ty;
                    dy[cnty].second=i;
                }
                ny++;
            }
            else//都可以
            {
                double kt=1.0*(y[i]-y[0])/(x[i]-x[0]);
                double tx=-1.0*y[0]/kt+x[0];
                double ty=-kt*x[0]+y[0];
                dx[++cntx].first=tx;
                dx[cntx].second=i;
                dy[++cnty].first=ty;
                dy[cnty].second=i;
            }
        }
    }//cout<<"cnt="<<cnt<<" tp="<<tp<<endl;
    if(tp+nx>k&&tp+ny>k)//无论放在x轴函数y轴都不行
        printf("-1\n");
    else
    {
        k-=tp;//现在的性质<=k
        double ans=1.0*inf;
        int l,r,f=0;
        sort(dx+1,dx+1+cntx);
        sort(dy+1,dy+1+cnty);
        if(cntx+ny>k&&ny<=k)//把板子放在x轴
        {

            f=1,l=1,r=cntx-k+ny;
            while(r<=cntx)
            {//cout<<dx[l].first<<" "<<dx[r].first<<endl;
                double tt=dx[r].first-dx[l].first;
                if(ans-tt>eps)
                    ans=tt;
                l++;
                r++;
            }
        }
        if(cnty+nx>k&&nx<=k)
        {//cout<<"cnty="<<cnty<<endl;
            f=1,l=1,r=cnty-k+nx;
            while(r<=cnty)
            {
                double tt=dy[r].first-dy[l].first;
                //cout<<"tt="<<tt<<endl;
                //cout<<"ans="<<ans<<endl;
                if(ans-tt>eps)
                    ans=tt;//cout<<ans<<endl;
                l++;
                r++;
            }
        }
        if(!f)
            ans=0;
        printf("%f\n",ans);
    }
    return 0;
}

F. maki和tree

  一开始用暴力，每遇到一个黑色的点就把它周围的白色点遍历一遍。可能是数据水，过了。正解是，先求出每个白色连通块的点个数，然后在取遍历黑色点，防止一个白色点被遍历好多遍。
  对于一个连通块，可以用并查集求父亲计数，也可以直接在搜索时指定计数节点。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char ss[N];
vector<int>pic[N];
bool vis[N];
int pre[N];
long long num[N];
int Find(int x)
{
    if(x!=pre[x])
        return pre[x]=Find(pre[x]);
    else
        return x;
}
void Join(int x,int y)
{
    int px=Find(x);
    int py=Find(y);
    if(px!=py)
        pre[px]=py;
}
void dfs(int v,int p)
{
    num[Find(v)]++;
    vis[v]=1;
    for(int i=0;i<pic[v].size();i++)
    {
        int t=pic[v][i];
        if(t!=p&&ss[t]=='W')
            dfs(t,v);
    }
}
int main()
{
    int n,u,v;
    long long ans=0;
    scanf("%d",&n);
    scanf("%s",ss+1);//cout<<ss+1<<endl;
    for(int i=1;i<=n;i++)
        pre[i]=i;
    memset(vis,0,sizeof(vis));
    memset(num,0,sizeof(num));
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        pic[u].push_back(v);
        pic[v].push_back(u);
        if(ss[u]=='W'&&ss[v]=='W')
            Join(u,v);
    }
    for(int i=1;i<=n;i++)//扫一遍所有的白色的连通块
    {
        if(ss[i]=='W'&&!vis[i])
            dfs(i,-1);
    }
    for(int i=1;i<=n;i++)
    {
        if(ss[i]=='B')
        {
            long long res=0;
            for(int j=0;j<pic[i].size();j++)
            {
                int t=pic[i][j];
                if(ss[t]=='W')
                    res+=num[Find(t)];
            }
            for(int j=0;j<pic[i].size();j++)
            {
                int t=pic[i][j];
                if(ss[t]=='W')
                {
                    int pt=Find(t);
                    res-=num[pt];
                    ans+=(num[pt]*(res+1));
                }
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}
/* 8 WBBBWWBW 1 3 2 3 3 4 3 6 5 6 6 7 6 8 */

I.nico和niconiconi

简单dp:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
ll dp[N];
char ss[N];
int main()
{
    int n,a,b,c;
    scanf("%d%d%d%d",&n,&a,&b,&c);
    scanf("%s",ss+1);
    for(int i=1;i<=n;i++)
    {//nico niconi niconiconi
        dp[i]=dp[i-1];
        if(i>=4&&ss[i]=='o'&&ss[i-1]=='c'&&ss[i-2]=='i'&&ss[i-3]=='n')
            dp[i]=max(dp[i-4]+a,dp[i]);
        if(i>=6&&ss[i]=='i'&&ss[i-1]=='n'&&ss[i-2]=='o'&&ss[i-3]=='c'&&ss[i-4]=='i'&&ss[i-5]=='n')
            dp[i]=max(dp[i-6]+b,dp[i]);
        if(i>=10&&ss[i]=='i'&&ss[i-1]=='n'&&ss[i-2]=='o'&&ss[i-3]=='c'&&ss[i-4]=='i'&&ss[i-5]=='n'&&ss[i-6]=='o'&&ss[i-7]=='c'&&ss[i-8]=='i'&&ss[i-9]=='n')
            dp[i]=max(dp[i-10]+c,dp[i]);
    }
    printf("%lld\n",dp[n]);
    return 0;
}