首页 > > 程序设计 > C/C++ >

10.21测试

2018-06-17 21:43:30来源：未知阅读 ()

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

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

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

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

T1（cogs 1292.打砖块）

暴力：

 1 #include<cstdio>
 2 #include<iostream>
 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;++i)
21             for(int j=0;j<n-i;++j)
22                   if(vis[i][j])
23                     anss+=a[i][j];
24           ans=max(anss,ans);
25           return;
26     }
27     if(bb>=n-aa||aa>=n) return;
28     for(int i=bb;i<n-aa;++i)
29         if(aa==0||(vis[aa-1][i]&&vis[aa-1][i+1])){
30               vis[aa][i]=1;
31               dfs(cc+1,aa,i+1);dfs(cc+1,aa+1,0);
32               vis[aa][i]=0;
33         }
34 }
35 int main(){
36     Emine();
37     n=read(),m=read();
38     for(int i=0;i<n;++i)
39           for(int j=0;j<n-i;++j)
40             a[i][j]=read();
41     dfs(0,0,0);
42     printf("%d\n",ans);
43     return 0;
44 }

View Code

正解：

 1 //f[i][j][k]表示截止到第i行，总共已经选j个砖块，其中第i行已经选了前k个砖块的最大值。
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 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<i&&s[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<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<vector>
 7 #define ll long long
 8 using namespace std;
 9 priority_queue<ll,vector<ll>,greater<ll> > 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<cstdio>
 2 #include<iostream>
 3 #include<queue>
 4 #include<algorithm>
 5 #define maxn 100005
 6 using namespace std;
 7 int a[maxn],b[maxn],ans[maxn];
 8 priority_queue <int> 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<<ans[i]<<" ";
31     return 0;
32 }

View Code

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

暴力：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 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<ans) ans=(double)sum/(double)len;
21           return ;
22     }
23       int t=last[num];
24       while(t){
25           dfs(to[t],sum+cost[t],len+1);
26           t=next[t];
27     }
28 }
29 int main(){
30     Emine();
31       n=read(),m=read();
32       for(int i=1;i<=m;i++){
33           x=read(),y=read();
34           next[++cnt]=last[x],last[x]=cnt,to[cnt]=y,cost[cnt]=read();
35     }
36       scanf("%d",&q);
37       while(q--){
38           x=read(),y=read(),ans=100002;
39           if(!b[x][y]){
40              dfs(x,0,0);
41              a[x][y]=ans,b[x][y]=1;
42         }
43           else ans=a[x][y];
44           if(ans>=100002) printf("OMG!\n");
45           else printf("%.3lf\n",ans);
46     }
47     return 0;
48 }

View Code

正解：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 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 }