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;
}