Author Archives: 20134161

2015年NEUACM第三次月赛题解

Published by:

榜单: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的位置,然后就能得出结果了。

 

2015年NEUACM二月月赛题解

Published by:

最终的board:http://acm.neu.edu.cn/hustoj/contestrank.php?cid=1049

首先恭喜高思坦同学拿到了winner,其他同学要好好努力了呀~

感觉这次题目的类型还是挺全的,有各路大神来参与,出题人表示蛮开心的= =,虽然中间C题的数据有点波折,但感谢mathlover同学帮忙验证了题目数据。

标称挂在http://www.cnblogs.com/acvc/category/661566.html,以后这个就作为NEU月赛挂代码的地方吧。

 

A.简单的模拟题,分别判断同一行,同一列,对角线和反对角线四种情况就可以了。

 

B.题意:给出2n个value,要求分成两组每组n个,要求分成的这两组满足差值最小。

solution :

可能有很多人搞过一个uva上的题目那个题目没要求均分,所以直接一个裸背包就好了,但是这题要求均分,同样的可以使用背包,但是要多增加一个状态表示到目前为止分给第一组的个数,所以有 :

dp[i][j][k]=max(dp[i][j][k],max(dp[i-1][j-1][k-v[i]]+v[i],dp[i-1][j][k]));

表示都目前为止枚举到第i个value,给第一组分了j个,所用的体积为k的最优状态。

考虑内存所以要用到滚动数组,需要注意枚举的顺序。枚举的时候注意优化否则会tle.

 

C.基础的几何题,在纸上画几下就能发现规律。

(训练指南后面有n个圆的,这题简化了,只有一个圆)

在两点间连线,如果不被圆阻挡,那么走直线就行了。如果被圆阻挡了,就两个点做对圆的切线,则距离等于切线长加上中间一段圆弧的距离。

需要注意的是两点都在圆内的情况,这时也是走直线。

PS:这题好波折,中间发现标称有问题,然后改了一下,后来发现有两组数据没法手算删掉了,后来经人提醒用几何画板验证是对的就又加上了= =

 

D.改编的汉诺塔= =考了递归和矩阵快速幂。

设A[n]为从n个圆盘移动到相邻柱子的最小次数,B[n]为n个圆盘移动到下下个柱子的最小次数。则可以找到递推式A[n]=2*B[n-1]+1,B[n]=A[n-1]+2*B[n-1]+1.

由于n最大可以到10^9,所以需要用矩阵快速幂,构造矩阵

图片2

这样就行了=。=

 

E.基本的图论问题。解法是利用欧拉回路的知识+并查集。

如果只有一个连通分量,那么答案就是奇数度的点的个数/2,因为每两个奇数点连线就可以了。而且一个连通分量里奇数度的点一定只有偶数个。

如果有多个连通分量,就答案分成两个部分,在每个连通分量里,如果奇数度的点的个数超过2个,那么这部分添加边数是(奇数度的点的个数-2)/2,然后将所有连通分量练成一个圈(剩余两个奇数度的点的连这两个奇数点,如果没剩奇数点就随便连两个点就行了)

其实在纸上画画就发现结论了。。

Trick的地方就是如果一个连通分量内只有一个点,那么就不需要经过,因为我们要经过的是边。

 

F.

题意:给出n个数字,要求分成两组,其中一组要求每个数互素,求两组差值的最小值。

solution :

由于n小于100 既然要求互素当然就要考虑素因子,100内的素因子的数量小于27个,数据量还是很大。但是小于50的素因子只有15个,因为大于50的因子不会重复出现所以不用考虑,对于15这么小的数据量显然要用状态压缩。

dp[i+1][state|v[i+1]]=max(dp[i][state]+1,dp[i+1][state|v[i+1]]) 表示当前选到第i+1个数字,素因子选择的状态为state|v[i+1] ,转移显而易见,就是从上一次状态转移过来。最后枚举dp[n][state] 得到最大值。

有了最大值之后判断差值的最小值就很容易了。

(这题数据比较水了,没想到有真么多做法。直接暴力都能骗过我的数据)

 

G.本来想出质因子分解的,然后比赛时发现出水了。。直接暴力枚举就行了= =

为了加快速度注意利用性质,比如随着数字的增大连续的数字的个数是非递增的之类的。

 

H.这题最后还是没人过哩,好忧桑= =,标称的做法是离线+树状数组(求全局最大值)

首先对于每个数,预处理出其和其它数&的所有可能的结果(比如5,其可能结果是1,4,5)

再开一个last数组,记录每个数(0到1024)在离线扫描的时候上一次出现的位置。然后离线扫描,没遇到一个新的元素,就在其上一次出现过的位置将其所有可能&的结果加入到树状数组中,然后对于一组查询(r等于当前处理到的元素),求出其l处向右的最大值。原理就是出现过至少两次的最大的数就是所求的&的最大值。

说得比较含糊,具体看代码吧~

 

下学期马上就要开学了,很快就是省赛和四省赛了呀,同学们可要加把劲呀。从这次比赛看出,很多同学寒假的训练还是不够勤奋。新生从月赛中看到什么还不会的算法数据结构神马的就要多去学,老队员建议多打比赛(CF,TC,各个OJ月赛神马的)保持状态。

接下三月份还有月赛,希望每个同学努力训练,争取下一次多多AC^_^.

 

 

NEUACM 2015年一月月赛 题解

Published by:

第一次月赛为了照顾下新生,所以题目比较水,没怎么考算法。。所以后果是有10+个人ak了= =b..

A

题目意思就是给你A,B,C 三种方式理财,然后每个月会给你一个年利率,然后每个月的本金+利润可以在下一个月接着理财, 但你也可以不选择任何方式理财。

double a[3][100];

double money;

int n;

int main(){

scanf(“%d”,&n);

while(n–){

for(int i = 0;i < 3;i++){

for(int j = 0;j < 12;j++){

scanf(“%lf”,&a[i][j]);

}

}

scanf(“%lf”,&money);

double begin = 1.0;

for(int i = 0;i < 12;i++){

double v = 0;

for(int j = 0;j < 3;j++){

if(a[j][i] > v)

v = a[j][i];

}

v /= 100.0;

begin = begin * (1 + v);

}

money = money * (begin – 1.0);

printf(“%.3lf\n”,money);

}

return 0;

}

然后这样就很水很水了。。  只用从1月开始一直到12月,找出最大的利润,如果这时候利润是< 0的,那就不理财,  然后结果就是输出最终的利润。 签到题。。题意略坑。

B

题意: 给出n 个数字,求出存在多少个组连续的t个数字,满足这t个数字每个数字的值都小于c.

Solution :

注意下是保证单个数字的值小于c即可,只需要从前向后模拟下,扫描到val>c 时将扫描长度清零即可。

C 水题

把k=10^n代进去k*(k+1)/2就看出来了

D

这题很水的。 看起来吓人。 因为每次操作,只会操作1-10的倍数

所以每次操作的时候只用一个 sum 数组来存储加的数是多少就可以了。。

然后就输出区间 (1 , r) – (1 , l-1) 的和就OK了。

输出的时候,只用判断1到 l中,有多少个数是 1的倍数,2的倍数,3的倍数,。。。10的倍数。。然后累加就好了。。是不是特别简单… 专为不懂数据结构者设计。

int CASE;

int n;

char s[10];

int a,b;

long long sum[20];

long long QUERY(int l){

if(l == 0)return 0;

long long ans = 0;

for(int i = 1;i <= 10;i++){

ans += sum[i] * (l / i);

}

return ans;

}

long long Answer(int l,int r){

return QUERY(r) – QUERY(l-1);

}

int main(){

scanf(“%d”,&CASE);

while(CASE–){

scanf(“%d”,&n);

for(int i = 0;i < 20;i++) sum[i] = 0;

int q;

scanf(“%d”,&q);

while(q–){

scanf(“%s %d %d”,s,&a,&b);

if(s[0] == ‘P’){

sum[a] += b;

}else{

printf(“%lld\n”,Answer(a,b));

}

}

}

return 0;

}

数据比较水,只卡掉了运行超时

2333333

E

题意: 给出n个数的随机排列,求最少交换多少步能变成递增序列。

Solution : 考虑每个置换,假设存在一个置换的循环节为n , 要想把每个置换内的数字交换到自己的位置至少需要n-1 次,因此只需要分解出这个序列每个置换的循环节求和即可。

比如 :

1 2 3 4 5 6 7

2 3 4 1 6 5 7

分解完之后就是 (1,2,3,4) (5,6) (7) 那么最后的总是就是 3+1+0 =4。

此题存在很多的变形,比如说每次交换的代价是两个数的和(两个数的最大值),求变成递增序列最少代价。但是这些都是通过求置换得出来的。

const int MAX = 1e7+10;
int a[MAX],c[MAX];
bool vis[MAX];
int main() {
freopen(“in.txt”,”r”,stdin);
freopen(“out.txt”,”w”,stdout);
int n,res,cnt;
while(scanf(“%d”,&n)==1) {
for(int i=1;i<=n;i++) {
scanf(“%d”,&a[i]);
}
memset(vis,false,sizeof(vis));
res=0;
for(int i=1;i<=n;i++) {
if(!vis[i]) {
cnt=1;
int pos=a[i];
vis[i]=true;
while(!vis[pos]) {
vis[pos]=true;
pos=a[pos];
cnt++;
}
res+=cnt-1;
}
}
printf(“%d\n”,res);
}
return 0;
}

F

题意: n颗子弹扫射,前k颗以1cm 的速度弹道上扬 ,后(n-k) 发子弹保持在最高点,问最多能达到多少个靶子 。

Solution :

考虑的到靶子的最大高度,可以直接采用枚举的方法。 可以先枚举第一发子弹的位置pos,那么第k发子弹的位置就是在 pos+k-1 处, 只要求出pos ,pos+1,…..pos+k-1 这一段连续的序列中有多少个位置是靶子就好。可以利用前缀和预处理下,然后最后 (n-k)发由于是保持在同一个高度,可以直接算出当前的高度有多少个靶子。

注意 : 不能直接去枚举靶子的位置,还有就是要把数组开大一点。

int main() {
// freopen(“in.txt”,”r”,stdin);
// freopen(“out.txt”,”w”,stdout);
int n,k,m;
while(scanf(“%d %d %d”,&n,&m,&k)==3) {
memset(sum,0,sizeof(sum));
memset(vis,0,sizeof(vis));
int Max=0;
for(int i=1;i<=n;++i) {
scanf(“%d”,&H[i]);
Max=max(Max,H[i]);
if(!vis[H[i]]) {
add(H[i],1);
}
vis[H[i]]++;
}
int res=0,tot;
for(int i=1;i<=Max;i++) {
tot=0;
int R=i+k-1,L=i;
tot+=Query(R)-Query(L-1);
if(vis[R]>m-k) {
tot+=m-k;
}
else {
tot+=max(vis[R]-1,0);
}
res=max(res,tot);
}
printf(“%d\n”,res);
}
return 0;
}

G 数学题

打个表就看成规律了,然后数比较大要用高精度。

如果用递推形式的话弄高精度比较麻烦,所以可以将结果化简一下再用。

如果n和m不同奇偶,那么答案是0,否则答案是2^((n-1)*(m-1))

(用数学归纳法可以证)

H

一个水题,几何题, 就是需要处理下凹边型的情况跟 1个点的情况。

int n;

struct point{

double x,y;

}P[1010],C;

double dis(const point &a,const point &b){

return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

double D_dis(const point &a,const point &b){

return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

double getArea(const point &x, const point &y, const point & z){

double a = dis(x,y);

double b = dis(y,z);

double c = dis(z,x);

double p = (a+b+c)/2;

return sqrt(p*(p-a)*(p-b)*(p-c)) * 2;

}

double GET(point p,point q){

double mm ,h;

mm = min( dis(C,q), dis(C ,p));

h = getArea(p,q,C) / dis(p,q);

if(D_dis(p,C) > (D_dis(p,q) + D_dis(q,C)) || D_dis(C,q) > (D_dis(p,C) + D_dis(p,q)) ){

return mm;

}else{

return min(mm,h);

}

}

int main(){

int CASE;

scanf(“%d”,&CASE);

while(CASE–){

scanf(“%d”,&n);

for(int i = 0;i < n;i++){

scanf(“%lf %lf”,&P[i].x,&P[i].y);

}

P[n] = P[0];

scanf(“%lf %lf”,&C.x,&C.y);

if(n == 1){

printf(“%.3lf\n”,dis(C,P[0]));

continue;

}

double ret = 0x3f3f3f3f;

for(int i = 0;i < n;i++){

double tmp = GET(P[i],P[i+1]);

ret = ret < tmp ? ret : tmp;

}

printf(“%.3lf\n”,ret);

}

return 0;

}

I 数学期望

做法很多,我的做法是n只蚂蚁中每两只蚂蚁碰面的机会是1/4,而这样的蚂蚁对数是C(n,2)

所以答案就是C(n,2)/4.

J 签到题

去后一半数就达到最大值,它们之间的最小公约数为1,所以满足要求,所以答案是n-[n/2]

 出题人

2015-1-31