二模 (8) day2

第一题:

题目描述:

有 n 个炸弹,有些炸弹牵了一根单向引线(也就是说引线只有在这一端能被炸弹点燃),只要引爆了这个炸弹,用引线连接的下一个炸弹也会爆炸。每个炸弹还有个得分,当这个炸弹被引爆后就能得到相应得分。现在要你引爆 k 个炸弹,使得得分最大。

解题过程:

1.一开始想到算出每个入度为0的点打掉之后的得分,然后做个堆,从大到小打,但是路径会有重叠的情况,也就是说打掉一条路径后可能会导致另外一条路径的权值发生变化。。

2.然后听到YYL大神一直在说2次BFS,就想到可以倒着来做。。从出度为0的点出发,然后计算路径的权值,然后按权值从大到小来打。

于是算法就出来了:

先做个拓扑序,然后dp计算从点i出发(沿反向边走)的最大权值(d[i]=max{ d[j] (j,i)∈E }+val[i])。然后排个序从大到小来打即可。

3.另外有个发现,STL的vector真的会慢很多,一开始用vector存边就TLE一个点,改成前向星就变成0.3s了。。果然偷懒是有代价的。。。以后还是尽量用前向星好了。

4.另外题目没说不会出现环,虽然数据里没有,所以还要缩点。


第二题:

题目大意:有 n 个石子围成一圈,每个石子都有一个权值 a[i]。给你一次且仅一次取石子的机会,取石子的块数不限,取完后统计得分。现在要使取出的石子得分最大。每个石子的得分计算公式是 a[i]*d,d 表示这个石子到两边被取了的石子的距离和。

解题过程:

1.这题坑。。其实只要取权值最大的两个石头就可以。证明见后面。。

2.我的做法是一开始取权值最大的时候,然后按权值从大到小来取,如果把某个石头插入可以得到更多的分数的话,就把它加入。(把它加入之后会使它两边的石头加的分数减少,只要比较是增加的多还是减少得多即可。)写了个线段树来动态维护某个石头两边的石头是谁。。 然后边上开始讨论为什么只要取权值最大的两个石头就可以。。我还不相信,就随机了几组数据,竟然拍出来都一样,顿时给傻了。。。数学直觉还是不够敏锐呵。

3.关于“只要取权值最大的两个石头就可以”的证明:

假设取石头的顺序是按权值从大到小来取的,如果一个石头的权值是mid,它左边的石头权值是L,右边的石头权值是R;

那么有 L,R>=mid.   再设它和左边的石头的距离为Ld,和右边的石头的距离为Rd,那么选了这个石头可以增加的分数为

(Ld+Rd)*mid。   而左边的石头减少的分数为(Rd+1)*L,右边的石头减少的分数为(Ld+1)*R。显然减少的多。


第三题:

题目大意:

有A,B,C三种物品N个(N<=100)排成一条线,从左往右拿,一开始拿10个(不足10个就全部拿完),然后可以选择ABC中的一种,比如选A,就把手上的A全部装箱,然后再拿相应数量的物品,使得手上始终有10个(或者已经拿完了)。求最少的装箱次数使得N个物品全部装箱。

解题过程:
1.时间不是很够,就直接写了个贪心,根据下面的原则:

A:如果流水线上已经没有某种物品了,且手中还有,那么就先给这种物品装箱。

B:如果没有出现情况A,那么就取手上最多的那种物品。

RP爆发,骗了90分说。。

2.标算是dp,下面copy题解了:

设 f[i][A][B][C]表示前 i-1 个产品在流水线上取出了,当前准备装箱的 10 个产品中,有 A 个 A 类产品,B 个 B 类产品,C 个 C 类产品,此时,我们继续装箱,至少需要多少次才能装箱完毕。
那么通过 f[i][A][B][C]可以正向推出 3 个决策

把A装箱:f[i+A][A’][B+B’][C+C’],其中A’,B’,C’表示流水线上第i到第i+A-1个产品中分别有多少个 A 类,B 类,C 类产品。

把B装箱:f[i+B][A+A’][B’][C+C’],其中A’,B’,C’表示流水线上第i到第i+B-1个产品中分别有多少个 A 类,B 类,C 类产品。

把C装箱:f[i+C][A+A’][B+B’][C’],其中A’,B’,C’表示流水线上第i到第i+C-1个产品中分别有多少个 A 类,B 类,C 类产品。

f[i][A][B][C]=min{f[i+A][A’][B+B’][C+C’],f[i+B][A+A’][B’][C+C’],f[i+C][A+A’][B+B’][C’]}+1;

质量很高的3道题。。回到了二模 (5) day2的感觉。。

上一篇:java 打印乘法口诀表


下一篇:Java中的Enumeration、Iterable和Iterator接口详解