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;}
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];
}
des=1-des;
pos+=l;
}
ans=max(ans,test);
}
printf("%d/n",ans);
}
return 0;
}
#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;}
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];
}
des=1-des;
pos+=l;
}
ans=max(ans,test);
}
printf("%d/n",ans);
}
return 0;
}
