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

2017ZZUACM省赛选拔试题部分题解----谨以纪念我…

2018-06-17 22:48:19来源：未知阅读 ()

写在前面：

其实心里有些小小的不爽又有点小小的舒畅，为啥捏？不爽当然是因为没被选拔上啦，舒畅捏则是因为没被选拔上反而让自己警醒，学长也提点很多很多。“沉下去，然后一战成名”学长如是对我说，我很开心。其实这完全算不算是题解，只是我个人的一些小想法而已。而且到现在还有一题不会...让自己长点记性吧。

题目 A ：聪明的田鼠

Time Limit: 1 Sec
Memory Limit: 128 MB
Description
田鼠MIUMIU来到了一片农田，农田可以看成是一个M*N个方格的矩阵。每个方格里放有一定的粮食。
MIUMIU看到这里，兴奋不已，它要拿走多多的粮食，以备过冬。但MIUMIU要么往前走（向右） ，
要么往下走。 但它很聪明，一定会找到一条拿走最多粮食的路径。
MIUMIU目前在入口位置, 坐标为（1,1），出口位置在坐标（M,N）。 
请你编程，计算一下当MIUMIU走出农田时,最多能拿走多少粮食。
Input
第一行：  M  N  （ 1≤M ,N ≤50 ）
接下来有M行， 每行有N个整数,分别表示方格中的粮食数  0≤ Aij≤100 (i=1,..M, j=1,…N)
（所有的数之间有一个空格）
Output
一个整数，表示MIUMIU能拿走的最多粮食数。
Sample Input
4  3
5  3  7
5  3  2
5  5  5
6  2  5
Sample Output
30
HINT
Source

题解:这是一道典型的动态规划题，由于考前未学，而只是见过一道类似的三角形的题，然后就把这道题转换为了三角形的题。花费时间有点长...用dp的话倒是代码写起来很简单，虽然空间复杂度达到了n²，但是在此题无所谓，dp本来就是空间换时间。

如诺手机查看代码不好看请转：http://paste.ubuntu.com/24387705/

 1 #include <bits/stdc++.h>
 2 
 3 
 4 using namespace std;
 5 const int maxn=105;
 6 int dp[maxn][maxn];
 7 int a[maxn][maxn];
 8 int Dp(int m,int n)
 9 {
10     for(int i=m-1;i>=0;i--)
11     {
12         for(int j=n-1;j>=0;j--)
13         {
14             dp[i][j]=max(dp[i+1][j],dp[i][j+1])+a[i][j];
15         }
16     }
17     return dp[0][0];
18 }
19 int main()
20 {
21     int m,n;
22     cin>>m>>n;
23     for(int i=0;i<m;i++)
24     {
25         for(int j=0;j<n;j++)
26             {
27                 cin>>a[i][j];
28             }
29     }
30     cout<<Dp(m,n)<<endl;
31     return 0;
32 }

题目 B ：软件安装

Time Limit: 1 Sec  Memory Limit: 128 MB
Description
Dr.Kong有一个容量为N MB (1 <= N <= 50,000)的存储磁盘,不妨设地址空间编号为1到N。现在他需要安装一些软件， 
每个软件要占用一定大小的容量且必须装在连续的地址空间里。比如发出指令“1 100”，表示需要申请100 MB的存储空间。
如果有多个满足条件的连续空间，则选择起始地址最小的一个进行分配。若没有足够的连续空间，将不安装此软件（即使有
足够多的不连续存储空间）。系统可以不定时的卸载软件，释放磁盘的空间。比如：发出“2 23 100”，表示释放起始地址
为23的连续100MB大小的容量。释放时，不需要考虑这些空间里是否安装过软件。
请你编写一个程序，帮助Dr.Kong处理M (1 <= M <= 50,000)个按指令次序请求的任务。第一个请求到来前，磁盘是空的。
Input
第1行:     N  M
第2…M+1行: 每行描述了一个请求，如果是申请，则用2个数字 1 Mi 表示； 如果是释放，则用3个数字 2 Di Mi表示。数据之间用一个空格隔开. （1<=Di ,Mi<= 50,000）
Output
对于每个申请指令，输出占1行。如果请求能被满足，输出满足条件的最小起始地址；如果请求无法被满足，输出0。对于每个释放指令，不产生输出。
Sample Input
10  6
1  3
1  3
1  3
1  3
2  5  5
1  6
Sample Output
1
4
7
0
5

题解：学长说用线段树做，然而本渣渣并不会线段树那么高级的玩意啊，这可咋整捏？然后后面发现set有个equal_range函数炒鸡好用呀，如果用这函数然后去更新区间貌似时间复杂度也是nlogn呀。但是还有个小小滴问题，更新区间时间复杂度是降下来了，查找咋整捏？想了个歪法子，就是用多个set分别把长度大于p[i]的空闲区间存起来。然后到时候可以按照要求的区间长度来找入口查找，就没必要一个个全遍历了。

如诺手机查看代码不好看请转：http://paste.ubuntu.com/24387736/

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 const int maxn=50005;
  5 set<int> mem;//标记所有起始空闲地址
  6 set<int>::iterator it;
  7 int kx[maxn+1];//所有空闲起始地址的空闲空间
  8 set<int> kxcs[20];  //分别存储所有长度大于等于p[i]的起始地址
  9 const int p[20]={1,2,3,4,5,6,7,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};//分组
 10 pair<set<int>::const_iterator,set<int>::const_iterator> pr;
 11 void insertit(int insertcs,int len);
 12 void deleteit(int deletecs);
 13 int lg2(int len)
 14 {
 15     int getit;
 16     int i=0;
 17     for(;p[i]<=len&&i<20;i++);
 18     getit=i-1;
 19     return getit;
 20 }
 21 int searchit(int len)//查找
 22 {
 23     int addr=lg2(len);//选择入口
 24     set<int>::iterator itit;
 25     for(itit=kxcs[addr].begin();itit!=kxcs[addr].end();itit++)//从入口开始遍历
 26     {
 27         int getcs=*itit;
 28         if(kx[getcs]>=len)
 29         {
 30             int afterlen=kx[getcs]-len;
 31             int aftercs=getcs+len;
 32             kx[aftercs]=afterlen;
 33             deleteit(getcs);
 34             if(afterlen!=0)
 35             {
 36                 insertit(aftercs,afterlen);
 37             }
 38             return getcs;
 39         }
 40     }
 41     return 0;
 42 }
 43 void insertit(int insertcs,int len)//添加 起始地址与长度
 44 {
 45     int addr=lg2(len);
 46     mem.insert(insertcs);//更新总数据
 47     kx[insertcs]=len;
 48     for(int i=0;i<=addr;i++)//更新分组数据
 49     {
 50         kxcs[i].insert(insertcs);
 51     }
 52   /*  for(set<int>::iterator itit=mem.begin();itit!=mem.end();itit++)
 53     {
 54         cout<<*itit<<endl;
 55     }*/
 56 }
 57 void deleteit(int deletecs)
 58 {
 59     int addr=lg2(kx[deletecs]);
 60     kx[deletecs]=0;
 61     mem.erase(deletecs);
 62     for(int i=0;i<=addr;i++)
 63     {
 64     kxcs[i].erase(deletecs);
 65     }
 66 }
 67 int m,n,sta,di,mi;
 68 int main()
 69 {
 70     memset(kx,0,sizeof(kx));
 71     kx[maxn]=maxn;
 72     scanf("%d %d",&n,&m);
 73     mem.insert(0);
 74     mem.insert(maxn);//用于保护，以免出现段错误
 75     insertit(1,n);
 76     while(m--)
 77     {
 78         scanf("%d",&sta);
 79         if(sta==1)
 80         {
 81             scanf("%d",&mi);
 82             printf("%d\n",searchit(mi));
 83         }
 84         else
 85         {
 86             scanf("%d %d",&di,&mi);
 87             int flag=false;
 88             int si=di;
 89             if(si>n)continue;
 90             int ei=di+mi-1;
 91             if(ei>n)ei=n;//限制边界
 92             pr=mem.equal_range(di);//该函数可以从容器中返回第一个大于等于或大于指定数的数
 93             it=pr.first;
 94             it--;//往后一个即为最后一个比它小的
 95             if(*it+kx[*it]-1>=ei&&*it+kx[*it]-1>=si-1)continue;//新区间直接被原先区间覆盖，那该次释放无意义 
 96             if(*it+kx[*it]-1>=si-1)//如果最后一个比它小的结束地址大于本次释放区间起始地址，则这两个区间将连起来，初始地址将是*it
 97             {
 98                 si=*it;
 99                 deleteit(*(it++));//先删除该区间，下面重建，因为还不知道区间长度
100             }
101             else it++;
102             while(true)
103             {
104                 if(*it+kx[*it]-1>ei)//遍历新的释放空间会重合的所有区间，当某区间结束地址比新区间的结束地址大时遍历结束
105                 {
106                     if(*it<=ei+1)//该区间与新区间相连接起来
107                     {
108                         ei=*it+kx[*it]-1;
109                         deleteit(*it);//连接起来则全算为新区间的，把该区间删除
110                     }
111                     insertit(si,ei-si+1);//把新区间加进去
112                     break;
113                 }
114                 if(*it<=ei)
115                 {
116                     deleteit(*(it++));//区间起始地址小于等于新区间结束地址都是要和新区间重合的
117                 }
118                 else it++;
119             }
120         }
121     }
122     return 0;
123 }

题目 C ：V型积木

Time Limit: 1 Sec  Memory Limit: 128 MB
Description
 Dr.Wu的宝宝1岁了，所以Dr.Wu准备买些积木给宝宝玩，促进孩子大脑的发育。由于宝宝太小，
所以他将高低不同的积木摆放的毫无规律（如图A）。然而Dr.Wu发现，如果从当前的积木中抽走
一部分（图B，C中虚线的即表示抽走的积木），剩下的积木能够呈现出“V”形，即积木的高度先
严格递减，然后严格递增。图B中，需要抽走三个积木，剩下的积木就可以呈现出“V”形，而图C
中仅需抽走一根积木。Dr.Wu需要你帮忙找出最少抽走多少积木，剩下的积木就能呈现出“V”型？

Input
第一行： T     表示以下有T组测试数据（1≤T ≤8）
对每组测试数据：
第一行:    N表示积木的个数。 （2<N<=100），
第二行是空格隔开的N个正整数，每个正整数Hi表示第i个积木的高度（0<Hi<=10000）。
输出中，仅一个数，即最少抽走的积木数。如果怎么抽走积木都无法呈现出“V”形，则输出“No Solution”。
Output
每组测试数据，输出占一行，仅一个数，即最少抽走的积木数。如果怎么抽走积木都无法呈现出“V”形，则输出“No Solution”。
Sample Input
2
6
50  30  40  10  20  60
6
5  4  3  1  2  6
Sample Output
1
0

题解：一开始想着bfs来着，然后gg。后来学习到最长上升子序列，然后就明白了什么...遍历每一个积木，求得其左边序列的最长下降子序列以及右边最长上升子序列，和最大的就是抽掉的最少的。

如诺手机查看代码不好看请转：http://paste.ubuntu.com/24387742/

#include <bits/stdc++.h>

using namespace std;
int shumu;
int jm[1050];
int b[1050];
int weizhi;
int res;
int maxv=1000000+7;
int ss()
{
   int len=0;
   b[0]=0;
   for(int i=weizhi;i<shumu;i++)
   {
        if(jm[i]>b[len])
       {
           len++;
           b[len]=jm[i];
       }
       else
       {
           for(int j=1;j<=len;j++)
           {
               if(jm[i]<=b[j])
               {
                   b[j]=jm[i];
                   break;
               }
           }
       }
   }
   return len;
}
int xj()
{
    int len=0;
   b[0]=maxv;
   for(int i=0;i<weizhi+1;i++)
   {
       if(jm[i]<b[len])
       {
           len++;
           b[len]=jm[i];
       }
       else
       {
           for(int j=1;j<=len;j++)
           {
               if(jm[i]>=b[j])//大于等于都换，否则长度算出来有问题
               {
                   b[j]=jm[i];
                   break;
               }
           }
       }
   }
   return len;
}
int main()
{
    int T;
    cin>>T;
    for(int i=0;i<T;i++)
    {
        cin>>shumu;
        int yc=0;
        memset(jm,0,sizeof(jm));
        for(int j=0;j<shumu;j++)
        {
            cin>>jm[j];
        }
            res=shumu;
            for(int k=0;k<shumu;k++)
            {
                    weizhi=k;
                    int m,n;
                    m=ss();n=xj();
                    if(m==1||n==1)
                    {
                        continue;
                    }
                    int u=shumu-m-n+1;
                    if(res>u)res=u;              
            }
            if(res<shumu-2)
            {
                cout<<res<<endl;
            }
            else
            {
                cout<<"No Solution"<<endl;
            }
    }
    return 0;
}

题目 D ：最佳地址

Time Limit: 2 Sec  Memory Limit: 128 MB
Description
某地区M座煤矿，其中第i号矿每年产量为Ai吨，现有火力发电厂一个，每年需用煤B吨，
每年运行的固定费用（包括折旧费，不包括煤的运费）为H元，每吨原煤从第i号矿运到
原有发电厂的运费为Ci0（i=1，2，…，M）。 
现规划新建一个发电厂，M座煤矿每年开采的原煤将全部供给这两座发电厂。现有N个备选
的厂址。若在第j号备选厂址建新厂，每年运行的固定费用为Hj元。每吨原煤从第i号矿运
到j号备选厂址的运费为Cij（i=1，2，…，M；j=1，2，…，N）。 
试问：应把新厂厂址选取在何处？M座煤矿开采的原煤应如何分配给两个发电厂，才能使
每年的总费用（发电厂运行费用与原煤运费之和）为最小。 

Input
第一行： T     表示以下有T组测试数据（1≤T ≤5）
对每组测试数据：
第1行：       M  B  H  N 
第2行：       A1  A2 …  Am               （0<=Ai<=500,   A1+A2+...+An>=B）
第3行：      H1  H2 …  Hn               （0<=Hi<=100）
第4行：       C10  C20 … Cm0              
第5行：       C11  C21 … Cm1 
                              …   … 
第n+4行：  C1n  C2n … Cmn              （0<=Cij<=50）
Output
每组测试数据，输出占一行，两个整数，即新厂址编号和总费用。如果有多个编号满足要求，输出最小的。
Sample Input
1
4  2  7  9 
3  1  10  3 
6  3  7  1  10  2  7  4  9 
1  2  4  3 
6  6  8  2 
4  10  8  4 
10  2  9  2 
7  6  6  2 
9  3  7  1 
2  1  6  9 
3  1  10  9 
4  2  1  8 
2  1  3  4
Sample Output
8 49

题解：哈哈，这题写出来时间空间复杂度都超级低，嘿嘿（学长用时200+ms，我的0-4ms左右）。大概思路呢就是先不管原发电厂要多少煤求出最小费用，然后在此期间，分别用了两个结构体数组记忆运到原发电厂比新建发电厂贵的费用差和具有的煤的数量（rem0），以及新建发电厂比原发电厂贵的费用差和具有的煤的数量（rem），然后看一下不管条件的最小费用后的给原发电厂的煤是多了还是少了，如果多了，就从rem0里按每吨煤价值差小（sort）的在前面先算，一吨吨卸下来（类似部分背包）。反之同理。

如诺手机查看代码不好看请转：http://paste.ubuntu.com/24387745/

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 const int maxn=105;
  5 struct Rem
  6 {
  7     int value;
  8     int weight;
  9 };
 10 bool bmp(Rem a,Rem b)
 11 {
 12     return (a.value<b.value);
 13 }
 14 int temp=0;
 15 int a[maxn];int h[maxn];
 16 int c0[maxn];
 17 int c[maxn];
 18 Rem rem[maxn];
 19 Rem rem0[maxn];
 20 int m,b,H,n;
 21 int main()
 22 {
 23     int T;
 24     scanf("%d",&T);
 25     while(T--)
 26     {
 27        temp=0;
 28        int res=1000000000+7;
 29        scanf("%d %d %d %d",&m,&b,&H,&n);
 30        for(int i=1;i<=m;i++)
 31        {
 32            scanf("%d",&a[i]);
 33        }
 34        for(int i=1;i<=n;i++)
 35        {
 36            scanf("%d",&h[i]);
 37        }
 38         for(int i=1;i<=m;i++)
 39         {
 40             scanf("%d",&c0[i]);
 41         }
 42        int test=1;
 43        int u=1,r=1;
 44        int weight=0;
 45        int needweight=0;
 46        int num=0;
 47        for(;test<=n;test++)
 48        {
 49            temp=0;weight=0;needweight=0;u=1;r=1;
 50            for(int k=1;k<=m;k++)
 51            {
 52                scanf("%d",&c[k]);
 53                if(c[k]<c0[k])
 54                {
 55                    rem[u].value=c0[k]-c[k];
 56                    rem[u++].weight=a[k];
 57                    temp+=c[k]*a[k];
 58                }
 59                else
 60                {
 61                    rem0[r].value=c[k]-c0[k];
 62                    rem0[r++].weight=a[k];
 63                    temp+=c0[k]*a[k];
 64                    weight+=a[k];
 65                }
 66            }
 67            if(weight>=b)
 68            {
 69                sort(rem0+1,rem0+r,bmp);
 70                needweight=weight-b;
 71                for(int k=1;k<r;k++)
 72                {
 73                    if(rem0[k].weight>=needweight)
 74                    {
 75                         temp+=needweight*rem0[k].value;
 76                         needweight=0;
 77                         break;
 78                    }
 79                    else
 80                    {
 81                        needweight-=rem0[k].weight;
 82                         temp+=rem0[k].value*rem0[k].weight;
 83                    }
 84                }
 85                if(res>temp+H+h[test])
 86                {
 87                    res=temp+H+h[test];
 88                    num=test;
 89                }
 90            }
 91            else
 92            {
 93                sort(rem+1,rem+u,bmp);
 94                 needweight=b-weight;
 95                 for(int k=1;k<u;k++)
 96                 {
 97                     if(rem[k].weight>=needweight)
 98                     {
 99                         needweight=0;
100                         temp+=needweight*rem[k].value;
101                         break;
102                     }
103                     else
104                     {
105                         needweight-=rem[k].weight;
106                         temp+=rem[k].value*rem[k].weight;
107                     }
108                 }
109                 if(res>temp+H+h[test])
110                {
111                    res=temp+H+h[test];
112                    num=test;
113                }
114            }
115        }
116        printf("%d %d\n",num,res);
117     }
118     return 0;
119 }