文档章节

11.8 考试整理

Loi_DL
 Loi_DL
发布于 2016/11/08 18:36
字数 2604
阅读 4
收藏 0

总结:开始考试,先看题,t1 5分钟看明白题意,t2 读了一遍woc做过,再度一遍还是woc做过,就是输出不大一样,心想终于不用爆零了。t3 背包问题?还是二维的?算了最后骗骗分不管了。先做t2,很顺利10分钟打完,20分钟加手读,检查,测试数据30分钟左右终于觉得没问题了。去做T1,求两个时间差多少毫秒,(真蛋疼)╮(╯▽╰)╭还是得做啊。然后现象怎么读入,想了一会读入差不多了,然后怎么处理呢?在纸上画画❀.....去了趟厕所感觉神清气爽。回来感觉思路差不多了,开始打。边打边调。打完了检查一遍开始测样例,竟然全过了激动了一小下,然后我想到考试一定要稳!!!如果是noip,做出这两道day1我的任务就完成了,最后在打打暴力T3骗骗分。嗯(⊙_⊙)开始测试数据,差几年的时候竟然出现了bug,调了一会发现多加了一次,改了就正常了。我也不会对拍,就自己想想极端数据和小数据。测试完成后。一个半小时就差不多了。离结束还有40分钟左右,去看t3,看了看数据范围扔个01背包上去会有多少分?想了两组数据感觉正解啊,压成一维跑01背包。dp本来就不大会,最后寻思着就扔上01背包了。然后考试结束了。

300分考了100分, 基本上就是垫底分,因为t2做过,所以说跟爆零也没啥区别,伤❤。然后开始找哪错了,就算t3不得分,t1怎么着也得√几个点啊。t1栈溢出?!smg问问lc我说我数组开的很正常啊,lc说可能是数组越界了。?越界?,就这次我省空间开了很少的数组,结果真越界了,开了1000的数组,赋值了一个2000.。。。。。。。。。。。。。。。。╮(╯▽╰)╭,改了之后90分,虽然还是wa了一个点,但是加上190的话,在清北那边也能排上前20。t3问了问lxl打得什么骗了40分。他说裸地01背包,我想woc我也是哎,我看了看她代码。一样啊!!!因为多组数据貌似没打换行,dp数组貌似忘请空了啊。。。。。。。。。。40分又没了╮(╯▽╰)╭,230的话清北那边排第5!T1最后一个点貌似是因为开了一个longlong用int赋值,然后int赋值得时候炸了,导致longlong被赋了一个随机错误的答案。全改成longlong就A了,T3正解排序然后O(n)枚举能不能放,然后答案取个max。

考这样怪谁!?

开心点O(∩_∩)O~~就当为noip积累经验了,现在犯了错误noip就不会犯了。加油↖(^ω^)↗。

经验总结:

1.数组在不炸空间的情况下尽量比要求大一点,需要开多大认真思考思考,如果有两个答案拿不准的话并且较大的保证不炸空间就按大的开。

2.稳稳稳,做事要稳健!!!打完之后一点要检查代码,尤其是简单题,自己能拿分的题。

3.不要被题目所迷惑,比如t3虽然写着背包,但是正解根本不用背包思想。以后要认真思考每一个问题,不要被迷惑。

4.有些题虽然是这个算法但并不是裸地,只是需要这个题的思想,用这个思想去做题。还是以题目为主,要思考的是能解决问题的方法!!!!!而不是算法。

5.第二次犯这种错误了,第一次double类型用int赋值,这次longlong类型用int赋值,都挂了惨痛的教训,以后一定要记住强转!!!尽量全部都是同种类型用同种类型赋值!!!

6.注意多组数据的输出。

T1

【题目描述】
给你两个日期,问这两个日期差了多少毫秒。
【输入格式】
两行,每行一个日期,日期格式保证为“YYYY - MM- DD  hh:mm:ss ”这种形式。第二个日期时间一定比第一个日期时间要大两个日期的年份一定都是 21 世纪的年份。
【输出格式】
一行一个整数代表毫秒数。
【样例输入 1】
2000-01-01 00:00:00
2000-01-01 00:00:01
【样例输出 1】
1000
【样例输入 2】
2000-01-01 00:00:00
2000-11-11 00:00:00
【样例输出 2】
27216000000
【数据范围与规定】
对于10%的数据,两个日期相同。
对于20%的数据,两个日期只有秒数可能不同。
对于30%的数据,两个日期只有秒数、分钟数可能不同。
对于40%的数据,两个日期的年月日一定相同。
对于60%的数据,两个日期的年月一定相同。
对于80%的数据,两个日期的年份一定相同。 
对于100%的数据,两个日期一定都是 21 世纪的某一天,且第二个日期一定
大于等于第一个日期。 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int rn[10000];   //本来开的1000
int ry[]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int zy[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
char y1[1000],y2[1000];
long long nian1,nian2,yve1,yve2,ri1,ri2,xs1,xs2,fz1,fz2,miao1,miao2;  //这个地方得开longlong要不下面int会被乘炸
int main()
{
	freopen("two.in","r",stdin);
	freopen("two.out","w",stdout);
	for(int i=2001;i<=2099;i++)
	if(i%4==0) rn[i]=1;
	rn[2000]=1;  //所以这里数组越界了
	gets(y1);
	nian1=(y1[0]-'0')*1000+(y1[1]-'0')*100+(y1[2]-'0')*10+y1[3]-'0';
	yve1=(y1[5]-'0')*10+y1[6]-'0';
	ri1=(y1[8]-'0')*10+y1[9]-'0';
	xs1=(y1[11]-'0')*10+y1[12]-'0';
	fz1=(y1[14]-'0')*10+y1[15]-'0';
	miao1=(y1[17]-'0')*10+y1[18]-'0';
	//cout<<nian1<<" "<<yve1<<" "<<ri1<<" "<<xs1<<" "<<fz1<<" "<<miao1<<endl;
	gets(y2);
	nian2=(y2[0]-'0')*1000+(y2[1]-'0')*100+(y2[2]-'0')*10+y2[3]-'0';
	yve2=(y2[5]-'0')*10+y2[6]-'0';
	ri2=(y2[8]-'0')*10+y2[9]-'0';
	xs2=(y2[11]-'0')*10+y2[12]-'0';
	fz2=(y2[14]-'0')*10+y2[15]-'0';
	miao2=(y2[17]-'0')*10+y2[18]-'0';
	//cout<<nian2<<" "<<yve2<<" "<<ri2<<" "<<xs2<<" "<<fz2<<" "<<miao2<<endl;
	long long ans=0,jian=0,jia=0;
	if(nian1!=nian2)
	{
		for(int i=nian1;i<nian2;i++)
		{
			if(rn[i]==1)
			ans+=31622400000;
			else
			ans+=31536000000;
		}
	}
	jian+=miao1*1000;
	jian+=fz1*60000;
	jian+=xs1*3600000;
	jian+=ri1*86400000;  //这int可能会炸
	long long dst=0;
	for(int i=1;i<yve1;i++)
	{
		if(rn[nian1]==1)
			dst+=ry[i];
		else
			dst+=zy[i];
	}
	jian+=dst*86400000;
	jia+=miao2*1000;
	jia+=fz2*60000;
	jia+=xs2*3600000;
	jia+=ri2*86400000;
	dst=0;
	for(int i=1;i<yve2;i++)
	{
		if(rn[nian2]==1)
			dst+=ry[i];
		else
			dst+=zy[i];
	}
	jia+=dst*86400000;
	printf("%lld",ans-jian+jia);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T2

【问题描述】
现在有𝑀个位置可以打 sif ,有𝑁 + 1个人在排队等着打 sif 。现在告诉你前𝑁个人每个人需要多长的时间打 sif ,问你第𝑁 + 1个人什么时候才能打 sif。 (前𝑁个人必须按照顺序来)
【输入格式】
第一行两个整数𝑁, 𝑀如上所述。
接下来𝑁行每行一个整数代表每个人所需要用的时间。
【输出格式】
一行一个整数表示答案。
【样例输入】
3 2
1
1
1
【样例输出】
1
【样例解释】
山里有座庙。
【数据规模与约定】
对于100%的数据,每个人所需用的时间不超过10^5。
测试点  𝑁  𝑀  测试点  𝑁  𝑀
1  10  10  6 5000  500
2  20  10  7  100000  5000
3  50  10  8  100000  10000
4  1000  500  9  100000  20000
5  2000  500  10  100000  50000

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
priority_queue<LL> q;
LL n,m;
LL num[1000000];
void read(LL &a)
{
	a=0;
	char c=getchar();
	while (c<'0'||c>'9')
	c=getchar();
	while (c>='0'&&c<='9')
	{
		a*=10;
		a+=c-'0';
		c=getchar();
	}
}
int main()
{
	freopen("death.in","r",stdin);
	freopen("death.out","w",stdout);
	read(n);read(m);
	for(int i=1;i<=n;i++)
		read(num[i]);
	if(n<m)
		printf("%d",0);
	else 
	{
		for(int i=1;i<=n;i++)
		{
			if(i<=m)
				q.push(-num[i]);
			else 
			{
				LL t=-q.top();
				q.pop();
				t+=num[i];
				q.push(-t);
			}
		}
		LL ans=-q.top();
		printf("%lld",ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T3

【问题描述】
背包是个好东西,希望我也有。给你一个二维的背包,它的体积是𝑁 × 𝑀。现在你有一些大小为1 × 2和1 x 3的物品,每个物品有自己的价值。你希望往背包里面装一些物品,使得它们价值和最大,问最大的价值和是多少。
【输入格式】
第一行一个整数𝑇代表该测试点的数据组数。
对于每组数据,第一行有四个整数𝑁, 𝑀, 𝑛1, 𝑛2,其中𝑛1, 𝑛2分别代表大小1 × 2和大小为1 × 3的物品个数。
接下来一行有𝑛1个数代表每个1 × 2物品的价值。
接下来一行有𝑛2个数代表每个1 × 3物品的价值。
【输出格式】
对于每组询问,输出能够达到的价值最大值。
【样例输入】
1
2 3 2 2
1 2
1 2
【样例输出】
4
【样例解释】
庙里有座山。
【数据规模与约定】
对于20%的数据,𝑁, 𝑀 ≤ 10, 𝑛1, 𝑛2≤ 100。
对于70%的数据,𝑁, 𝑀 ≤ 100, 𝑛1, 𝑛2≤ 2000。
对于100%的数据,1 ≤ 𝑇 ≤ 10,1 ≤ 𝑁, 𝑀 ≤ 500,0 ≤ 𝑛1, 𝑛2≤ 10000。 

暴力:

错误估计时间复杂度    尴尬     2w*25w

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
LL T,n,m,n1,n2;
int jz[100000];
int hf[1000000];
int dp[1000000];
int main()
{
	freopen("eyesight.in","r",stdin);
	freopen("eyesight.out","w",stdout);
	scanf("%lld",&T);
	while (T!=0)
	{
		T--;
        memset(dp,0,sizeof(dp));  // 忘了
		memset(jz,0,sizeof(jz));
		memset(hf,0,sizeof(hf));
		scanf("%lld%lld%lld%lld",&n,&m,&n1,&n2);
		for(int i=1;i<=n1;i++)
		{
			scanf("%d",&jz[i]);
			hf[i]=2;
		}
		for(int i=n1+1;i<=n1+n2;i++)
		{
			scanf("%d",&jz[i]);
			hf[i]=3;
		}
		for(int i=1;i<=n1+n2;i++)
			for(int j=n*m;j>=hf[i];j--)  //   >= 
			dp[j]=max(dp[j],dp[j-hf[i]]+jz[i]);
		printf("%d\n",dp[n*m]);  //忘了多组数据
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

正解:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL T,n,m,n1,n2;
LL jz1[100000];
LL jz2[100000];
LL sum1[100000];
LL sum2[100000];
LL cp(LL x,LL y)
{
	return x>y;
}
int main()
{
	freopen("eyesight.in","r",stdin);
	freopen("eyesight.out","w",stdout);
	scanf("%lld",&T);
	while (T!=0)
	{
		T--;
		LL ans=-1;
		memset(jz1,0,sizeof(jz1));
		memset(jz2,0,sizeof(jz2));
		scanf("%lld%lld%lld%lld",&n,&m,&n1,&n2);
		for(int i=1;i<=n1;i++)
			scanf("%lld",&jz1[i]);
		for(int i=1;i<=n2;i++)
			scanf("%lld",&jz2[i]);
		sort(jz1+1,jz1+1+n1,cp);
		sort(jz2+1,jz2+1+n2,cp);
		for(int i=1;i<=n1;i++)
			sum1[i]=sum1[i-1]+jz1[i]; 
		for(int i=1;i<=n2;i++)
			sum2[i]=sum2[i-1]+jz2[i];
		for(int i=0;i<=n1;i++)
		{
			if(2*i>n*m) continue;
			LL t=(n*m-2*i)/3;
			t=min(t,n2);
			ans=max(ans,sum1[i]+sum2[t]);
		}
		printf("%lld\n",ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

 

© 著作权归作者所有

Loi_DL
粉丝 0
博文 60
码字总数 48692
作品 0
莱芜
私信 提问
11.8 日报

今天 UED 首页、全部分类完成,猜你喜欢30% 程文丽 海外购完成 华洁霞 APP 唤起native 60% 首页样式调整 @windy 刘涛 前端 tms搭建 50% 前端架构50%,全部分类开始做 @黄冬林 服务端 文档完成...

客户端-刘涛
2014/11/18
2
0
Fedora Linux 16 r3 发布

貌似都没有消息呢,我发一下吧。 下载地址 热切期盼着11.8号的正式版

everyx
2011/11/01
1K
8
Contao 3.0.beta1 发布,PHP 建站系统

Contao 是一个采用 PHP 开发的 CMS 建站系统,具备非常高的安全性和良好的搜索;残疾人也可以非常方便的访问,可方便设置用户权限、在线更新服务和先进的CSS框架以及例如日历、新闻和表单等基...

oschina
2012/05/22
423
0
AMD Catalyst 11.8 Linux Driver Released

AMD 发布了新版本的 ATI 显卡 linux 驱动: Catayst 11.8, 主要改进包括: 1. 修改了驱动中 ATI 的 “ 烙印” 例如,将 aticonfig 重命名为 amdconfig, Reference 中也有相应的改动。 2. 更...

杨英超
2011/08/18
439
0
自考总结--爱恨交加的计算机网络

第五次自考,这次是最后一科,计算机网络。接下来,可能是一大篇励志鸡汤。不喜欢喝的可以看其他博客,需要的继续读下去下面有惊喜。 由于项目和个人问题,计算机网络在考试一周之前并没有好...

weienjun
2018/04/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Jenkins基础入门-5-用户和权限管理

本篇,我们来介绍下Jenkins上如何创建用户,以及如何管理用户,和那些用户可以有ProjectA的权限。这个很好理解,一个项目,有开发和测试,和运维,每个团队都有不同的角色,例如有测试经理和...

shzwork
25分钟前
1
0
linux上解压版安装jdk,tomcat

需要的安装包 1.vmware12 2.centos7版本 3.安装完成后需要xshell来连接远程虚拟机,虚拟机保证要联网,网络畅通。 4.xftp用来向linux传输文件用,一般来说xshell和xftp配套使用 5.对应的压缩...

architect刘源源
今天
26
0
使用 spring 的 IOC 解决程序耦合

工厂模式解耦 在实际开发中我们可以把三层的对象都使用配置文件配置起来,当启动服务器应用加载的时候,让一个类中的方法通过读取配置文件,把这些对象创建出来并存起来。在接下来的使用的时...

骚年锦时
今天
2
0
group by分组后获得每组中时间最大的那条记录

用途: GROUP BY 语句用于 对一个或多个列对结果集进行分组。 例子: 原表: 现在,我们希望根据USER_ID 字段进行分组,那么,可使用 GROUP BY 语句。 我们使用下列 SQL 语句: SELECT ID,US...

豆花饭烧土豆
今天
3
0
android6.0源码分析之Camera API2.0下的Preview(预览)流程分析

本文将基于android6.0的源码,对Camera API2.0下Camera的preview的流程进行分析。在文章android6.0源码分析之Camera API2.0下的初始化流程分析中,已经对Camera2内置应用的Open即初始化流程进...

天王盖地虎626
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部