设为首页 加入收藏

TOP

2017ZZUACM省赛选拔试题部分题解----谨以纪念我这卡线滚粗的美好经历(一)
2017-10-12 18:16:01 】 浏览:4332
Tags:2017ZZUACM 选拔 试题 部分 题解 ---- 纪念 卡线滚 美好 经历

写在前面:

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

题目 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的话倒是代码写起来很简单,虽然空间复杂度达到了n2,但是在此题无所谓,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;
 2
首页 上一页 1 2 3 4 下一页 尾页 1/4/4
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇bzoj3289 -- 莫队+树状数组 下一篇C++实现的控制台-贪吃蛇

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目