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 自行百度书本整理即可