T1玩具谜题

Solution

这一年唯一一道良心题，直接加上在取个模就可以了。

Code

#include
     
      #include
      
       using namespace std;int a[100009],n,m,tag,num,now;char b[100009][109];int main(){    scanf("%d%d",&n,&m);    for(int i=0;i
      
     

T2天天爱跑步

https://www.cnblogs.com/ZH-comld/p/9384690.html

T3换教室

Solution

对于路径的问题，弗洛伊德跑一下就可以了。

对于这道题，比较朴素的想法是设dp[i][j][0/1]表示在i天，申请了j次，现在的位置（前一天是否申请成功）。

但这样是有问题的，因为不能体现出申请的时候的成功与失败结果。

写起来也是有问题的，甚至没有办法初始化。。。。

所以我们要算出每次走的路径的期望，所以我们设dp[i][j][0/1]表示在i时刻，一共申请了j次，有没有提交申请。

转移的话枚举上一次是否申请了，边权要乘上上一次成功的概率和这次成功的概率。

Code

#include
     
      #include
      
       #include
       
         using namespace std;int c[2009],d[2009],n,m,v,e,u,o;double dis[309][309],dp[2009][2009][2],k[2009],ans,w;int main(){    cin>>n>>m>>v>>e;    ans=1e20;    for(int i=1;i<=v;++i)      for(int j=1;j<=v;++j)        dis[i][j]=1e15;    for(int i=1;i<=n;++i)      scanf("%d",&c[i]);    for(int i=1;i<=n;++i)      scanf("%d",&d[i]);    for(int i=1;i<=n;++i)      scanf("%lf",&k[i]);    for(int i=1;i<=v;++i)dis[i][i]=0;    for(int i=1;i<=e;++i)    {      scanf("%d%d%lf",&u,&o,&w);      if(w
        
         =1)dp[i][j][1]=min(dp[i-1][j-1][0]+dis[c[i-1]][c[i]]*(w-k[i])+dis[c[i-1]][d[i]]*k[i],dp[i-1][j-1][1]+dis[c[i-1]][c[i]]*(w-k[i-1])*(w-k[i])+dis[c[i-1]][d[i]]*(w-k[i-1])*k[i]+dis[d[i-1]][c[i]]*(k[i-1])*(w-k[i])+dis[d[i-1]][d[i]]*k[i-1]*k[i]);        }   for(int i=0;i<=m;++i)     ans=min(min(ans,dp[n][i][0]),dp[n][i][1]);    printf("%.2lf",ans);    return 0;}
        
       
      
     

 

T4组合数问题

Solution

也是一道良心题，n平方求组合数对k取个模，求一个前缀和，每次询问可以做到O（1）回答。

Code

#include
     
      #include
      
       using namespace std;int y[2009][2009],t,k,n,m;long long dp[2009][2009];int main(){    scanf("%d%d",&t,&k);    y[1][1]=1;    for(int i=2;i<=2002;++i)      for(int j=1;j<=i;++j)        y[i][j]=(y[i-1][j-1]+y[i-1][j])%k;/*    for(int i=1;i<=10;++i)    {        for(int j=1;j<=min(i,10);++j)          cout<
       
        <<" ";        cout<
        
         n)m=n;        printf("%lld\n",dp[n+1][m+1]);    }    return 0;    }
        
       
      
     

 

T5蚯蚓

观察到先被切断的一定比后切段的长度大，开三个队列维护即可。

#include
     
      #include
      
       #include
       
        #define N 7000002#define inf 0x7f7f7f7fusing namespace std;typedef long long ll;ll ji;double u,v;int n,m,q,tt,h[3],t[3],a[3][N],num,tag,x,y;bool cmp(int a,int b){    return a>b;}int main(){    scanf("%d%d%d%lf%lf%d",&n,&m,&q,&u,&v,&tt);    for(int i=1;i<=n;++i)scanf("%d",&a[0][i]);    sort(a[0]+1,a[0]+n+1,cmp);    h[0]=1;t[0]=n;h[1]=h[2]=1;t[1]=t[2]=0;    for(int i=1;i<=m;++i){        num=-inf;        for(int j=0;j<3;++j)            if(h[j]<=t[j]&&a[j][h[j]]>num){                num=a[j][h[j]];                tag=j;            }        if(!(i%tt))printf("%lld ",num+ji);        num+=ji;        h[tag]++;        x=num*(double)u/v;        y=num-x;        a[1][++t[1]]=x-q-ji;        a[2][++t[2]]=y-q-ji;        ji+=q;    }            printf("\n");    for(int i=1;i<=n+m;++i){        num=-inf;        for(int j=0;j<3;++j)          if(h[j]<=t[j]&&a[j][h[j]]>num){              num=a[j][h[j]];              tag=j;          }        h[tag]++;        if(!(i%tt))printf("%lld ",num+ji);    }    return 0;}
       
      
     

 

 

T6愤怒的小鸟

直接dp复杂度过高无法接受。

我们每次取出一个状态钦定里面第一个0和我枚举的点组成一条抛物线，他们的代价我可以n^2预处理处理出来。

#include
     
      #include
      
       #include
       
        #include
        
         #define N 20#define eps 1e-8using namespace std;int ji[N][N],n,m,dp[1<<18],t,ma;double x[N],y[N],a,b;inline int get(int i){    for(int j=0;j
         
          -eps)continue;                b=y[i]/x[i]-a*x[i];            for(int k=1;k<=n;++k)             if(fabs(a*x[k]*x[k]+b*x[k]-y[k])
          
           <