CSP202206_4
目录题目
思路
最初对整体分析了一下，因为反射点都是整数，而反射的性质典型而有限，一开始莫名想着是不是可以推规律，结果白白浪费半小时.......
最终还是确定直接模拟.......
第一遍读题时就在想\(|x_1 - x_2| < 3 \times 10^5\)这个条件肯定有用处，结果经过半小时的zz推规律后成功把这个关键条件忘了。
第一遍模拟时，考虑的是把每一面镜子用直线表示，然后对每一个光源边走边判断，写起来特别麻烦，而且估计着时间复杂度就肯定过不了。增增改改过了样例一交40pts，估计不是超时而是写炸了。
找了半天毛病也没找到，睡了一觉后又读了一边题，终于想起上面那个忘记的条件了。
下面才是重点：
- 考虑直接将每面镜子上的反射点存下来，根据光线走的路径判断是否有反射点，
- 如果使用结构体之类的存点坐标以及反射系数等，每次判断反射点直接遍历，时间复杂度不一定具体多少，但肯定TLE。
- 采用 map 维护关系，key 存储某行或某列，val 同样选用 map，分别存储对应 key 行/列上的点信息。
- 对光线的路径进行模拟时，就可以根据运动方向，直接查询对应运动的行或列上的最近反射点，将\(O(n)\)的操作直接降到\(O(logk)\)，成果解决超时问题。
其实优化思路主要还是借鉴了这位的博客，要我自己想肯定是想不到用 map。
这题反映的个人不足之一就是对STL的应用还有不足。对vector等的使用还较好，但对于set、map等一方面是想不起来用，另一方面是用的时候也不熟练。在本题中即使看过别人博客思路知道了用 map，自己在写的时候还是十分慢，并且一些语法额外又去查阅后才正确使用。
代码能力也要提升。
Code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x*f;
}
struct MIRROR
{
int x1, y1;
int x2, y2;
} mir[100010];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
map < int, map<int, int> > mx; // < y, map<x, id> >
map < int, map<int, int> > my; // < x, map<y, id> >
int m;
int mDir[100010];
double mLos[100010];
int get_dir(int m_dir, int d)
{
if(m_dir == 1)
{
if(d == 0) return 1;
if(d == 1) return 0;
if(d == 2) return 3;
if(d == 3) return 2;
}
else
{
if(d == 0) return 3;
if(d == 1) return 2;
if(d == 2) return 1;
if(d == 3) return 0;
}
}
void Build(int x, int y, int id)
{
map <int, map<int, int> > :: iterator it = mx.find(y);
if(it != mx.end())
{
it->second.insert(make_pair(x, id));
}
else
{
map <int, int> tmp;
tmp.insert(make_pair(x, id));
mx.insert(make_pair(y, tmp));
}
it = my.find(x);
if(it != my.end())
{
it->second.insert(make_pair(y, id));
}
else
{
map <int, int> tmp;
tmp.insert(make_pair(y, id));
my.insert(make_pair(x, tmp));
}
//cout << "Build Finish" << endl;
return;
}
void Remove(int x, int y)
{
//if(mx[y].count(x))
mx[y].erase(x);
//if(my[x].count(y))
my[x].erase(y);
//cout << "Remove Finish" << endl;
return;
}
void Cal(int x, int y, int d, double I, int t)
{
bool flag = false;
int nx = x, ny = y, id = 0;
while(t > 0)
{
if(d == 0 || d == 2)
{
map < int, map<int, int> > :: iterator it = mx.find(y);
if(it == mx.end())
{
flag = true;
break;
}
map <int, int> :: iterator p;
if(d == 0)
{
p = it->second.upper_bound(x);
if(p == it->second.end())
{
flag = true;
break;
}
nx = p->first;
id = p->second;
}
else
{
p = it->second.lower_bound(x);
if(p == it->second.begin())
{
flag = true;
break;
}
nx = (--p)->first;
id = p->second;
}
}
else
{
map < int, map<int, int> > ::iterator it = my.find(x);
if(it == my.end())
{
flag = true;
break;
}
map <int, int> ::iterator p;
if(d == 1)
{
p = it->second.upper_bound(y);
if(p == it->second.end())
{
flag = true;
break;
}
ny = p->first;
id = p->second;
}
else
{
p = it->second.lower_bound(y);
if(p == it->second.begin())
{
flag = true;
break;
}
ny = (--p)->first;
id = p->second;
}
}
int dis = abs(nx - x) + abs(ny - y);
if(dis > t || I < 1.0)
{
x += dx[d]*t;
y += dy[d]*t;
break;
}
x = nx;
y = ny;
d = get_dir(mDir[id], d);
I *= mLos[id];
t -= dis;
if(I < 1.0) break; //到达镜子但是耗散了
}
if(flag)
{
x += dx[d]*t;
y += dy[d]*t;
}
if(I < 1.0)
{
cout << 0 << " " << 0 << " " << 0 << endl;
}
else
{
cout << x << " " << y << " " << (int)I << endl;
}
//cout << "Cal Finish" << endl;
return;
}
int main()
{
m = read();
for(int k = 1;k <= m;k++)
{
int sig = read();
if(sig == 1)
{
int x1 = read(), y1 = read(), x2 = read(), y2 = read();
double a;
cin >> a;
//cout << a << endl;
mir[k] = {x1, y1, x2, y2};
mLos[k] = a;
int dir = (x1 - x2) / (y1 - y2); // 1 -> \; -1 -> /
mDir[k] = dir;
int sx = min(x1, x2), sy, fx, fy;
if(sx == x1)
{
sy = y1;
fx = x2;
fy = y2;
}
else
{
sy = y2;
fx = x1;
fy = y1;
}
if(dir == 1)
{
int i = sx + 1, j = sy + 1;
while(i < fx && j < fy)
{
Build(i, j, k);
i++;
j++;
}
}
else
{
int i = sx + 1, j = sy - 1;
while(i < fx && j > fy)
{
Build(i, j, k);
i++;
j--;
}
}
}
else
if(sig == 2)
{
int id = read();
int x1 = mir[id].x1, y1 = mir[id].y1;
int x2 = mir[id].x2, y2 = mir[id].y2;
int dir = mDir[id];
int sx = min(x1, x2), sy, fx, fy;
if(sx == x1)
{
sy = y1;
fx = x2;
fy = y2;
}
else
{
sy = y2;
fx = x1;
fy = y1;
}
if(dir == 1)
{
int i = sx + 1, j = sy + 1;
while(i < fx && j < fy)
{
Remove(i, j);
i++;
j++;
}
}
else
{
int i = sx + 1, j = sy - 1;
while(i < fx && j > fy)
{
Remove(i, j);
i++;
j--;
}
}
}
else
if(sig == 3)
{
int x = read(), y = read(), d = read();
double I;
cin >> I;
int t = read();
Cal(x, y, d, I, t);
}
//cout << k << endl;
}
return 0;
}
/*
7
1 0 4 2 2 0.4
1 2 2 0 0 0.45
3 -1 3 0 6 5
3 1 5 3 2.4 5
3 0 2 0 3 4
2 1
3 1 5 3 2.4 5
*/