Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

11/9
21:30
TEST

钟神的P73

P73

T1

题意:给定两个日期,求它们之间间隔了多少毫秒。

对于100%的数据,两个日期一定都是 21 世纪的某一天,且第二个日期一定 大于等于第一个日期。

当然是大力暴力啦!分别求出当前日期从2000-01-01 00:00:00开始一共过去了多少毫秒,然后输出差值就可以了。

 

T2

题意:n个人,m个位置,n个人按顺序打sif,每个人需要耗费一定的时间,问轮到第n+1个人打sif的时间。

n<=100000, m <= 50000.

这就是一个打水问题嘛,用优先队列搞一下就好了。

 

T3

题意:背包是个好东西,希望我也有。 给你一个二维的背包,它的体积是𝑁 × 𝑀。现在你有一些大小为1 × 2和1 ×3的物品,每个物品有自己的价值。你希望往背包里面装一些物品,使得它们的价值和最大,问最大的价值和是多少。

对于20%的数据,𝑁, 𝑀 ≤ 10, 𝑛1, 𝑛2≤ 100。 对于70%的数据,𝑁, 𝑀 ≤ 100, 𝑛1, 𝑛2≤ 2000。 对于100%的数据,1 ≤ 𝑇 ≤ 10,1 ≤ 𝑁, 𝑀 ≤ 500,0 ≤ 𝑛1, 𝑛2≤ 10000。

嗯……刚开始没有想到正解,但感觉一般情况下可以抽象成一个容量为n*m的背包,而两种物品的体积分别为2和3,这样就变成了01背包问题。但是因为memset的原因,tle了三个点……没有拿全40分 要不然就rank3了,哼唧

 

关于正解!是一个贪心……枚举1*3的物体放多少个即可得到正解。

当然,处理不是这么简单的。

一般情况下,13的物体最多可以放nm/3个;

而当背包的长或宽为2的时候,也就是说13的物体只能横着或竖着放。如果背包的宽为2,长为k3+2(k >= 0)的时候,13的物体最多可以放(nm-4)/ 3个

也就是

这样处理完就可以了,同时注意n1和n2可能不够的情况。