Daily Archives: 2015年1月31日

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