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