Loi_Vampire's Blog

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

11/15
10:33
TEST

11.15 test

试题

T1:

询问把n个数变成互不相同的数的最小价值。

n <= 10w, ai<=10w

这个做法有很多……可以 先排个序 或者 用set来做 都是可以的

说一下我在考场上的做法:是用到了并查集的思想。开一个数组fa, fa[i]表示大于等于i的第一个没有出现的数字。然后每次修改 find一下就好了

预处理的话 fa[i] = i。 如果一个数出现过的话,fa[i]改为i+1

 

T2:

n个点 m条有向边,求所有点到一号点的最短路之和。如果有任意一个点无法到达,输出-1.

奇怪的边权生成方式:w = (上一条边的边权 a + b) % c . w初始值为10,第一条边的权值为(10 a + b) % c

对于 30%的数据 n<= 200 , m <= 500 , a,b <= 100, c<=10000 对于 60%的数据 n<=10000 m <= 15000 a,b<=10000 c <= 10^7 对于 100%的数据 n <= 100000 m <= 200000 a,b <= 10^16, c <= 10^9

30分做法:floyd 同时w = (上一条边的边权 * a + b) % c不会爆掉int

60分做法:spfa 同时w = (上一条边的边权 * a + b) % c不会爆掉long long

100分做法:spfa 而这时需要及时取模 w = (((w % c) * (a % c)) % c + (b % c)) % c 要知道%运算时满足分配律的

30分floyd

 

100分spfa

 

T3:

划分型DP 自行百度书本整理即可

 

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可能不够的情况。