榜单:http://acm.neu.edu.cn/hustoj/contestrank.php?cid=1051

标称:http://www.cnblogs.com/acvc/category/677830.html

A

炒股有个macd技术指标,通过快线与慢线的关系,来判断下一日是买入还是卖出.

快线是指最近K天股票收盘价之和/K , 慢线是M天股票收盘价之和/M 。 (M > K)

当快线自下而上穿过慢线,则输出买入标志,当快线自上而下穿过慢线,输出卖出标志。

然后如果数据天数<=M ,则输出silent

这题很简单吧。普及下macd知识

这样我们只需要每次纪录前一天的快线,慢线值,然后再算出今日的 快线、慢线值, 这两个判断是否形成交叉就可以了。方法太多了。
B

答案是6*n-3,由于n超过长整型,所以得用高精度(c,c++手写高精度或者用JAVA大数类)

C

首先题意你要搞懂,就是N个建筑物,高度是可能会变的,范围在[1,Hi], 然后你要给一个至少多长的绳索,使其无论高度怎么变化,都能让人走过去。

看下数据 1<=n,w,H<=100

这就是最基础的动态规划了。。挺水的。。
f[H1][H2], f纪录最优的答案 , H1是前一个建筑物的高度, H2是当前建筑物的高度

有下面的递推关系:

ans[i][j] = max(ans[i][j],ans[i-1][z] + sqrt(w*w + (z-j)*(z-j))); (1<=z<=H[前] ,1<=j<=H[后])

D

题意为求A和B在L和R区间中的最大公约数。

N个询问、L到R区间,暴力肯定超时。

想一下最大公约数的定义,

比如A=420=2*2*3*5*7

B=540=2*2*3*3*3*5

则最大公约数=2*2*3*5=60,其余的公约数也肯定是2,2,3,5的组合

所以我们只要求出A,B的最大公约数,gcd(A,B)的所有公约数然后二分即可

用STL里的upper_bound(常用的还有lower_bound)一行代码即可解决二分

E

分组背包,限制是每组至少取一个
由于有分组,所以不能像01背包那样写成一维dp的形式,所以f[i][j]表示前i组总共j重量下的最大价值。
由于有每组至少取一个的限制,所以转移时注意先对当前组做转移状态,再对前一组做状态转移

//当前物品非当前组的第一件
if (f[i][w-c]>-1) {
f[i][w]=max(f[i][w],f[i][w-c]+v);
}
//当前物品为当前组的第一件
if (f[i-1][w-c]>-1) {
f[i][w]=max(f[i][w],f[i-1][w-c]+v);
}

需要注意就是上面两个if的顺序不能反,因为物品的重量有可能是0…

F

题意:给出n条线段,然后每次询问给一条线段,问这条线段包含前面给出的n条线段的多少条。

首先需要升下维度,吧一维的线段[x1,x2] 看成二维空间中的点,然后画图发现如果一条线段包含另一条线段一定就是满足某种关系。可以见下图。

图片1

方法一:可以直接利用二维前缀和预处理,由于x,y才1000完全可以直接前缀和求出前缀。

方法二:对于方法1如果题目加上修改操作就不能实行,所以可以采用二维的树状数组去求解。

G

显然Kid画的是一个无向欧拉图,其满足两个条件:
1.每个点的度数是偶数
2.图是连通的

对于邻接矩阵A,其平方B=A^2中,B[i][j]表示从点i到点j的路径条数。
首先我们看B[i][i],有两个部分组成:
1.每个点都有自环,所以可以通过这个自环走两次回到自身
2.走到另一个点再走回来(同一条边),这部分等于该点除自环外的度数
由定义可知,如果原图是无向欧拉图,那么第二部分的结果是个偶数,加上第一部分,所以B[i][i]一定是奇数。所以
不满足这个条件的就输出No
然后对于B[i][j],如果大于0,那么就存在这么一种可能:沿i的自环走一次,再走一次到j,即原图中i和j一定有边相连,
所以利用这个条件可以构造出原图。再用并查集判断一下这样构造出来的原图是不是连通的。

H

题意就不叙述了。。

(下面的图画错了,应该是逆时针转)

这题情况蛮多,最基本的思路也是二分。

因为如果qishen能在t时间内抓到萝莉,那他肯定也能在大于t的时间内抓到萝莉

现在需要二分时间t,

首先我们肯定得计算t时间后luoli的位置。

情况A,如果qishen与luoli在t时间的位置A的直线相连不经过灰圆,那么肯定是直接跑过去。

图片2

情况B:

直线连接穿过灰圆

则现在需要求出qishen与圆的切线的切点,luoli与圆切线的切点,考虑蓝色弧长+两段切线的长,看qishen能否在t时间走过这段距离。

图片3

涉及:二分、判断点在某时刻在圆上的位置、直线是否与圆相交、求点与圆的切线、求弧长等。较恶心 >_<

I

一道挺好的数据结构题,据出题人说有4种做法。。
这里给其中的一种做法,就是先预处理出序列中每个数在序列中出现的位置(用10^5个vector存,但总大小不会超过10^5)
然后每次查询时二分左右区间L,R的位置,然后就能得出结果了。

 

分类: 培训通知

发表评论

电子邮件地址不会被公开。 必填项已用*标注