解题报告
题1、内存管理
题目大意：
对于每次申请，使用最小的内存块，对于每次访问，给出是否允许。
朴素算法：
每次扫描一遍，找出没被占用的内存块，一找到就BREAK。 理论时间复杂度O(nm) n=30000;m为操作次数。 （实际上要快的多）
完美算法：
算法1：优化朴素；
通过仔细分析不难发现，由于释放要等待的时间只有总时间的1/144之一，而指令数又是有限的。所以如果要让我们的朴素超时，出数据的人会出在短时间内有多个申请的数据。既然在短时间内有多个申请，那时间必然会有重复，这样的话。我们只需判断现在的时间与上一次申请的时间做比较，如果一样，我们就沿着上次的答案接着寻找，避免多次无用功的出现。这样就可以在规定时间内出正解了。
Ps:指令是有限的，想让朴素找2w次必然要先使用2w条指令，而这2w条指令又得在600s内发出或者用2w条访问维护，想想如果用访问维护前面被占有，那得在这上面浪费多少指令啊，最后还能卡朴素吗？所以只能在短时间内多个申请，这样之前的优化就非常合适了。
算法2：用堆来实现快速查找
用小根堆记录tr_n哪些点可以用(编号做为关键字)，这样可以在logn的时间内查找出使用哪个内存块。
再拿一个小根堆_tr_t记录每个点被释放的时间的次序，自然tr_t中的结点要知道自己是对应哪个内存块。并记录实际的内存块的具体释放时间，以及内存块对应的树中的结点编号。
具体操作为：
每次读入，查看当前时间是否有内存块可以释放，有则释放。
如果读入为申请内存块，使用堆tr_n中第一个就好，然后将它放入tr_t中，释放时间为当前时间+600s,调整堆tr_t和堆tr_n。
如果是访问则比较访问时间与释放时间大小，如果释放时间大于访问时间则未被释放，释放时间调整为访问时间+600s，调整tr_t中的元素。如果释放时间小于或等于访问时间则禁止访问。
这样时间复杂度就降为O(Mlogn) M为操作次数 ，n为内存块数量就是30000。
题2、买礼物
这题很明显是二维费用背包，但是有诸多限制，需要一个一个解决。 首先解决可以免费送一个礼物的问题。 有一个很暴力的方法就是枚举送哪个礼物，再做背包，但这样时间复杂度是O(n2v1v2),
会超时。
现在我们用f[k,i,j]表示前k个物品第一张卡用i元，第二张卡用j元，并且已经免费拿过物品得到的最大满意度。
g[k,i,j]表示前k个物品第一张卡用i元，第二张卡用j元，并且没有免费拿过物品得到的最大满意度。
这样状态转移方程就是：
F[k,i,j]=max(f[k-1,i,j],
max(f[k-1,i-p[k],j],f[k-1,i,j-p[k],g[k-1,i,j])+v[k]); g[k,i,j]=max(g[k-1,i,j],
max(g[k-1,i-p[k],j],g[k-1,i,j-p[k])+v[k]);
(其中从g转移到F表示这个物品免费送)这样就解决了送的问题了。 接下来还有一个问题，就是有的物品一定要选。 这个问题我们可以通过控制转移来解决。对于所有一定要取的物品我们先做背包，只保留那些全选这些物品的状态。
原来我们用f[k-1,i,j]来更新F[k,i,j]，表示当前物品不选，现在对于这些一定要选的物品不能这样转移，也就是：
F[k,i,j]=max(f[k-1,i-p[k],j],f[k-1,i,j-p[k],g[k-1,i,j])+v[k]; g[k,i,j]=max(g[k-1,i-p[k],j],g[k-1,i,j-p[k])+v[k];
接着再按照原来的方程做其他选不选都行的物品的背包就行了，数组初值要赋成无穷小。
题3、防贼道路
题目大意:
给定无向图G，它的任一棵生成树T的权值P(T)定义为T的所有边权的最大公约数。请你求出其所有生成树T1,T2……的权值P(T1),P(T2)……的最小公倍数。
朴素算法:
枚举所有的生成树，然后计算他们的P(T)，然后计算所有P(T)的最小公倍数。时间复杂度为O（C[m][n-1]）,能过朴素的40分（不过其中20分直接算所有边的最大公约数都可以！！！）。
正确算法：
看到求XX的最大公约数和最小公倍数等很自然地想到了分解质因数。
假设L是一个质数，有M1条边能被L^k整除，如果那M1条边至少能构成一种生成树，那么ans的因数必然包含L^k！所以我们只需要枚举所有的质数，算出最大的k，使得L^k满足上述条件，然后乘入答案，时间复杂度为O（max(d)*M）。不过由于d最大有 2^15-1，这种算法不能A掉所有的数据。
但是仔细想一下，超过√d的质数在d中只可能包含一个，所以我们只需要枚举200以内的质数，算出最大的k之后，使所有的边的质因数不包含该质数（即不断除它，直到无法整除为止）。
那么所有边的d肯定为一个大于200的质数或者等于1。我们只需要快排一遍，如果连续超过n-1条边的权值相同，那么试试这些边能否至少构成一种生成树（小于n-1肯定没办法），如果可以构成就乘入答案。时间复杂度（200*M+MlogM）。
相关推荐：
loading