10.21测试-白红宇

10.21测试

阅读量：6687 次

发布时间：2019-06-25

本文共 5693 字，大约阅读时间需要 18 分钟。

QAQ（蒟蒻一枚），居然全打暴力。

　　T1能看出来是DP，但实在想不到那个奇技淫巧，果断暴搜（20）。

　　T2应该比较简单，写完正解跟暴力对拍，错了QAQ，直接交了暴力。

　　T3压根没往floyd想，交暴力。

T1（cogs 1292.打砖块）

暴力：

1 #include
      
        2 #include
       
         3 #define mysister 4 using namespace std; 5 const int maxn=50; 6 int read(){ 7     int x=0,f=1;char ch=getchar(); 8     while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();} 9     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}10     return x*f;11 }12 void Emine(){13     freopen("brike.in","r",stdin);14     freopen("brike.out","w",stdout);15 }16 int n,m,a[maxn][maxn],ans=0,vis[maxn][maxn];17 void dfs(int cc,int aa,int bb){18     if(cc==m){19           int anss=0;20           for(int i=0;i
        
         =n-aa||aa>=n) return;28     for(int i=bb;i

View Code

正解：

1 //f[i][j][k]表示截止到第i行，总共已经选j个砖块，其中第i行已经选了前k个砖块的最大值。 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define maxn 55 7 using namespace std; 8 void Emine(){ 9     freopen("brike.in","r",stdin);10     freopen("brike.out","w",stdout);11 }12 int n,m,v[maxn][maxn],s[maxn],sum[maxn][maxn],ans,f[maxn][10*maxn][maxn];13 int main(){14     Emine();15     scanf("%d%d",&n,&m);16     for(int i=1;i<=n;i++)for(int j=i;j<=n;j++) scanf("%d",&v[j][i]);17     for(int i=1;i<=n;i++)for(int j=1;j<=i;j++) sum[i][j]=sum[i][j-1]+v[i][j];18     for(int i=1;i<=n;i++) s[i]=s[i-1]+i;19     memset(f,-333,sizeof(f)); f[0][0][0]=0;20     for(int i=1;i<=n;i++){
    //截止到第i行21         for(int j=0;j<=min(m,s[i]);j++){
    //总共已经选j个砖块22             for(int k=0;k<=min(i,j);k++){
    //第i行已经选了前k个砖块23                 for(int p=max(k-1,0);p
          
           <=j-k;p++)24                     f[i][j][k]=max(f[i][j][k],f[i-1][j-k][p]+sum[i][k]);25                 ans=max(ans,f[i][j][k]);26             }27         }28     }29     printf("%d\n",ans);30     return 0; 31 }

View Code

T2（luogu 1631.序列合并）

暴力：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #define ll long long 8 using namespace std; 9 priority_queue
            
             
              ,greater
              
                > q;10 int n;ll a[100005],b[100005];11 int main(){12 scanf("%d",&n);13 for(int i=1;i<=n;i++)scanf("%lld",&a[i]);14 for(int i=1;i<=n;i++)scanf("%lld",&b[i]);15 for(int i=1;i<=n;i++)16 for(int j=1;j<=n;j++)17 q.push(a[i]+b[j]);18 for(int i=1;i<=n;i++){19 printf("%lld ",q.top());20 q.pop();21 }22 return 0;23 }

View Code

正解：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define maxn 100005 6 using namespace std; 7 int a[maxn],b[maxn],ans[maxn]; 8 priority_queue 
          
            q; 9 int main(){10     int n;cin>>n;11     for(int i=1;i<=n;i++)scanf("%d",&a[i]);12     for(int i=1;i<=n;i++){13         scanf("%d",&b[i]);14         q.push(b[i]+a[1]);15     }16     for(int i=1;i<=n;i++)17         for(int j=2;j<=n;j++){18             int temp=b[i]+a[j];19             if(temp>q.top()) break;20             else{21                 q.pop();22                 q.push(temp);23             }24         }25     for(int i=1;i<=n;i++){26         ans[n-i+1]=q.top();27         q.pop();28     }29     for(int i=1;i<=n;i++)30         cout<
           
            <<" ";31 return 0;32 }

View Code

T3（cogs 501.最小密度路径）

暴力：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int cnt,n,m,x,y,q,next[100001],last[100001],to[100001],cost[100001],b[101][101]; 7 double ans,a[101][101]; 8 int read(){ 9     int x=0,f=1;char ch=getchar();10     while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}11     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}12     return x*f;13 }14 void Emine(){15     freopen("path.in","r",stdin);16     freopen("path.out","w",stdout);17 }18 void dfs(int num,int sum,int len){19       if(num==y){20           if((double)sum/(double)len
          
           =100002) printf("OMG!\n");45           else printf("%.3lf\n",ans);46     }47     return 0;48 }

View Code

正解：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define maxn 55 6 #define maxm 1005 7 #define inf 0x3f3f3f3f 8 using namespace std; 9 int d[maxn][maxn][maxn],n,m,q;10 double ans[maxn][maxn];11 void Emine(){12     freopen("path.in","r",stdin);13     freopen("path.out","w",stdout);14 }15 int main(){16     Emine();17     scanf("%d%d",&n,&m);18     memset(d,inf,sizeof(d));19     for(int i=1;i<=m;i++){20         int u,v,w;scanf("%d%d%d",&u,&v,&w);21         d[u][v][1]=min(d[u][v][1],w);22     }23     for(int t=2;t<=n;t++)24         for(int k=1;k<=n;k++)25             for(int i=1;i<=n;i++)26                 for(int j=1;j<=n;j++){27                     if(d[i][k][t-1]==inf||d[k][j][1]==inf) continue;28                     d[i][j][t]=min(d[i][j][t],d[i][k][t-1]+d[k][j][1]);29                 }30     for(int i=1;i<=n;i++)31         for(int j=1;j<=n;j++){32             ans[i][j]=inf;33             if(i==j){ans[i][j]=0;continue;}34             for(int k=1;k<=n;k++) ans[i][j]=min(ans[i][j],(double)d[i][j][k]/(double)k);35         }36     scanf("%d",&q);37     while(q--){38         int u,v;scanf("%d%d",&u,&v);39         if(ans[u][v]>=1e6) printf("OMG!\n");  //被坑QAQ，最大密度为最大边权w/1==1e6; 40         else printf("%.3lf\n",ans[u][v]);41     }42     return 0;43 }