W round 1 题解

比赛链接 https://www.luogu.org/contest/18397

.好题

• 题目意思

  给一个巨大的杨辉三角，采用类似入门题(数字三角形)的方式求从顶点到指定点的最小累加和。

• 输出样例，和样例中的第二组数据一样呀

• 应该比较好写吧

• 组合数问题

顶点到指定点的最小累加和，一定是走边上。因为边上的数值最小。从顶点到指定点的最小累加和，是先走步竖直向下的，每步取最小值，然后再斜向下走一直到.累加和为。另外，我们可以发现，当时，先斜向下走到，再竖直向下走到，路径上的数值累加和是最小的。但是这道题目直接运用求组合数是会超时的，要加不少预处理才行。

• 思维难度：左右
• 代码难度：左右

标准程序

#include <bits/stdc++.h>
#define int long long
#define re register
using namespace std;
int n,m,p,res,Case,cnt,bin[2005][10090],pri[20005],zs[2001];

inline bool pd(int x) {
    if(x<2) return false;
    for ( re int i=2;i*i<=x;i++ ) 
        if(x%i==0) return false;
    return true;
}

inline void phi() {
    for ( re int i=2;i<=1e4;i++ ) 
        if(pd(i)) pri[i]=++cnt,zs[cnt]=i;
}

inline int ksm(int a,int b) {
    int ret=1;
    while(b) {
        if(b&1) ret=ret*a%p;
        a=a*a%p; b>>=1;
    }
    return ret%p;
}

inline void init() {
    for ( re int i=1;i<=cnt;i++ ) {
        bin[i][0]=1;
        for ( re int j=1;j<=10000;j++ ) 
            bin[i][j]=bin[i][j-1]*j%zs[i];
    }
}

inline int C(int n,int m) {
    if(n<m) return 0;
    int summ=ksm((bin[pri[p]][n-m]),p-2)%p;
    int a=((bin[pri[p]][n])*summ)%p;
    int b=bin[pri[p]][m];
    return a*ksm(b,p-2)%p;
}

inline int Lucas(int n,int m,int p) {
    if(!m) return 1;
    else return (C(n%p,m%p)*Lucas(n/p,m/p,p));
}

inline int read() {
    int sum=0,ff=1; char ch=getchar();
    while(ch<'0' or ch>'9') { if(ch=='-') ff=-1; ch=getchar(); }; 
    while(ch>='0' and ch<='9') { sum=sum*10+ch-'0'; ch=getchar(); }; 
    return sum*ff;
}

signed main() {
    phi(); init(); 
    int T=read();
    while(T--) {
        n=read(),m=read(),p=read();
        if(m>n/2) m=n-m;
        printf("%lld\n",(Lucas(n+1,m,p)+n-m+p)%p);
    }
    return 0;
}

模拟爆蛋题

这道题目的出题人是巨神，再这里他

• 数位DP

比较容易些吧。

• 发现规律似乎是裴波那切数列

然后写一个矩乘，就可以啦

• 可以参照这道题目

里面的题解有详细的证明，在这里不证明了（逃

• 思维难度：
• 代码难度：

  标准程序

  #include<bits/stdc++.h>
  #define LL long long
  using namespace std;
  const int N=1e4,S=30000001;
  char s[S];
  LL pi[N],k[N],P;
  inline LL gcd(register LL n,register LL m){while(m^=n^=m^=n%=m); return n;}
  inline LL lcm(register LL n,register LL m){return n/gcd(n,m)*m;}
  struct matrix
  {
    LL a[3][3];
    matrix(){memset(a,0,sizeof(a));}
    matrix operator*(matrix x)
    {
        matrix s;
        for(register int i=1;i<=2;i++) for(register int j=1;j<=2;j++) for(register int k=1;k<=2;k++) s.a[i][j]=(s.a[i][j]+a[i][k]*x.a[k][j])%P;
        return s;
    }
    matrix operator^(register LL k)
    {
        matrix s=*this,e;
        e.a[1][1]=e.a[2][2]=1;
    for(;k;k>>=1,s=s*s) if(k&1) e=e*s; 
        return e;
    }
  };
  inline int power(register LL n)
  {
    matrix a,ans;
    a.a[1][1]=a.a[1][2]=a.a[2][1]=1,a.a[2][2]=0;
    ans=a^n;
    return ans.a[1][2];
  }
  inline LL Get(register LL p)
  {
    register int s=sqrt(p),tot=0;
    for(register int i=2;i<=s;++i)
    if(!(p%i))
    {
        pi[++tot]=i,k[tot]=1;
        while(!(p%i)) p/=i,k[tot]*=i;
    }
    for(register int i=1;i<=tot;++i) k[i]/=pi[i];
    if(p!=1) k[++tot]=1,pi[tot]=p;
    for(register int i=1;i<=tot;++i)
        if(pi[i]==2) k[i]*=3;
        else if(pi[i]==3) k[i]*=5;
        else if(pi[i]==5) k[i]*=20;
        else if(pi[i]%5==1||pi[i]%5==4) k[i]*=pi[i]-1;
        else k[i]*=(pi[i]+1)<<1;
    register LL ans=k[1];
    for(register int i=2;i<=tot;++i) ans=lcm(ans,k[i]);
    return ans;
  }
  int main()
  {
    register int len;
    register LL m,n=0;
    scanf("%s%lld",s+1,&P),len=strlen(s+1);
    if(P==1) return cout<<0,0;
    m=Get(P);
    for(register int i=1;i<=len;++i) n=((n<<3)+(n<<1)+(s[i]^48))%m;
    if(!n) return cout<<0,0;
    if(n==1) return cout<<1,0;
    return cout<<power(n),0;    
  }

电梯

题目意思

就是有两种运输机，一种比较贵但是效率高，一种便宜但效率低，问你把所有物品运输完成的最小花费。

• 错误贪心—大力贪心

• DP

设表示前面个物品,次电梯的最优解

设表示在还是停留的花费少

先预处理出预处理出

于是开始大力,这个很显然

因为肯定是有转移过来,于是暴力转移即可

最后再O统计答案即可

总体复杂度大约为因为每次循环都是跑不满的,所以O(能过)

• 思维难度：

• 代码难度：

  标准程序

  #include <bits/stdc++.h>
  #define int long long 
  #define re register
  using namespace std;
  const int N=55;
  int h[N],f[N][N],min_dis[N][N],w1,w2,n,res,s1,ff; 
  signed main() {
    scanf("%lld %lld %lld",&n,&w1,&w2);
    for ( re int i=1;i<=n;i++ ) scanf("%lld",&h[i]),res+=h[i]*w2;
    sort(h+1,h+n+1);
    memset(f,63,sizeof(f));
    for ( re int i=0;i<=n;i++ ) 
        for ( re int j=i+1;j<=n;j++ ) 
            for ( re int k=i+1;k<=j-1;k++ ) 
                min_dis[i][j]+=min(h[k]-h[i],h[j]-h[k]);
    for ( re int i=1;i<=n;i++ ) {
        f[i][1]=w1;
        for ( re int j=1;j<=i-1;j++ ) 
            f[i][1]+=w2*min(h[j],h[i]-h[j]);
    }
    for ( re int i=2;i<=n;i++ ) 
        for ( re int j=2;j<=i;j++ ) 
            for ( re int k=j-1;k<=i-1;k++ ) 
                f[i][j]=min(f[i][j],w1+f[k][j-1]+min_dis[k][i]*w2);
    for ( re int i=1;i<=n;i++ ) 
        for ( re int j=1;j<=i;j++ ) {
            int tmp=0;
            for ( re int k=i+1;k<=n;k++ ) 
                tmp+=(h[k]-h[i])*w2;
            res=min(res,tmp+f[i][j]);
    }
    printf("%lld\n",res);
    return 0;
  }

  深度优先搜索

• 送分题

这道题目很简单,就好了

对于进行四进制转换，然后，扫一遍，统计转换后的每一种数字出现个数，输出出现次数最多的即可。

• 思维难度：
• 代码难度：

  标准程序

  #include <bits/stdc++.h>
  using namespace std;
  const int maxn=1000005,maxm=maxn*10+10; 
  char c[maxn];
  int num[maxm],n,m,ans,len;
  int main() {
    scanf("%s",c+1);
    len=strlen(c+1);
    scanf("%d",&n);
    for ( int i=1;i<=len;i++ ) {
        int sum=0;
        for ( int j=i;j<=min(len,i+n);j++ ) {
            if(c[i]=='A') sum=sum*1+1;
            if(c[i]=='G') sum=sum*2+1;
            if(c[i]=='C') sum=sum*3+1;
            if(c[i]=='T') sum=sum*4+1;
        }
        num[sum]++;
    }
    for ( int i=1;i<=10000000;i++ ) ans=max(ans,num[i]);
    printf("%d\n",ans);
    return 0;
  }