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;
}
