当前位置:编程学习 > C/C++ >>

CF 241C Mirror Box

Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements

好悲剧的CF啊,怒拿#105,结果前100有T-shirt。

不过还是涨了rate,什么时候也能黄一次啊。

题目:给出一个矩形,两边有两个洞,上下有一些镜子,从一个洞发射一个球,经过两边的镜子会反射,最后到达另外一个洞。每个镜子最多经过一次,每个镜子有一定的价值。问最大价值


由于每个镜子最多一次,而且起点终点是固定的,那么枚举碰撞次数,可以求出每次的反射距离

其中这又分为两种情况,即起点处向下发射,以及向上发射,那么根据碰撞次数的奇偶性,可以得到终点处的情况。

而中间刚好是(i-1)个长度 。

有了这个,就可以从发射开始模拟

代码很矬


[cpp]
#include<iostream>  
#include<cstdio>  
#include<map>  
#include<cstring>  
#include<cmath>  
#include<vector>  
#include<algorithm>  
#include<set>  
#include<string>  
#include<queue>  
#define inf 1<<30  
#define M 200005  
#define N 200005  
#define maxn 300005  
#define eps 1e-10  
#define zero(a) fabs(a)<eps  
#define Min(a,b) ((a)<(b)?(a):(b))  
#define Max(a,b) ((a)>(b)?(a):(b))  
#define pb(a) push_back(a)  
#define mp(a,b) make_pair(a,b)  
#define mem(a,b) memset(a,b,sizeof(a))  
#define LL long long  
#define lson step<<1  
#define rson step<<1|1  
#define MOD 1000000009  
#define sqr(a) ((a)*(a))  
#define Key_value ch[ch[root][1]][0]  
//#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std; 
int t[100005],f[100005]; 
int L=100000; 
double H=100.0; 
bool flag[105]; 
int main() 

    int hl,hr,n,val[105]; 
    while(scanf("%d%d%d",&hl,&hr,&n)!=EOF) 
    { 
        mem(t,0);mem(f,0); 
        for(int i=1;i<=n;i++) 
        { 
            int l,r;char str[10]; 
            scanf("%d%s%d%d",&val[i],str,&l,&r); 
            if(str[0]=='F')  for(int j=l;j<=r;j++) f[j]=i; 
            else for(int j=l;j<=r;j++) t[j]=i; 
        } 
        int ans=0; 
        for(int i=1;i<=n;i++) 
        { 
            double tmp=0; 
            if(i&1) tmp+=hl/H+(i-1)+hr/H; 
            else tmp+=hl/H+(i-1)+(H-hr)/H; 
            double l=L/tmp; 
            double pos=l*hl/H; 
            int des=1; 
            int test=0; 
            mem(flag,false); 
            for(int j=1;j<=i;j++) 
            { 
                if(des) 
                { 
                    if(f[(int)floor(pos)]==0&&f[(int)ceil(pos)]==0){test=-1;break;} 
                    int id=f[(int)floor(pos)]; 
                    if(flag[id]) {test=-1;break;} 
                    flag[id]=true;test+=val[id]; 
                } 
                else 
                { 
                    if(t[(int)floor(pos)]==0&&t[(int)ceil(pos)]==0){test=-1;break;} 
                    int id=t[(int)floor(pos)]; 
                    if(flag[id]) {test=-1;break;} 
                    flag[id]=true;test+=val[id]; 
                } 
                pos+=l; 
                des=1-des; 
            } 
            ans=max(ans,test); 
            tmp=0; 
            if(i&1) tmp+=(H-hl)/H+(i-1)+(H-hr)/H; 
            else tmp+=(H-hl)/H+(i-1)+hr/H; 
            l=L/tmp; 
            pos=l*(H-hl)/H;des=0; 
            test=0; 
            mem(flag,false); 
            for(int j=1;j<=i;j++) 
            { 
                if(des) 
                { 
                    if(f[(int)floor(pos)]==0&&f[(int)ceil(pos)]==0){test=-1;break;} 
                

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,