CCF-CSP认证202206-4
官网100分但是acwing提交wrong answer难过…
用到的一些存储结构
1.镜子结构体struct
包括:
镜子的id(这个id是为了对应每个点所属于哪个镜子)
镜子的起始坐标x1,y1,x2,y2
镜子的方向(有两种,左下到右上,左上到右下)
镜子的初始化(添加一个镜子)
镜子的删除(删除一个镜子)
2.点到镜子的映射map
map< pair[HTML_REMOVED],int >一个点x1,y1对应一个所属的镜子id
3.点的存储,两个map
map< int, set[HTML_REMOVED] > setX;//表示在x这条线上有镜子的纵坐标
map< int, set[HTML_REMOVED] > setY;//表示在y这条线上有镜子的横坐标
我的知识点积累
1.set中的upper_bound和lower_bound
首先要明确:set中的元素是有序的
lower_bound(key)会返回set中不小于key的第一个数,如果set中没有小于key的数,那么会返回set.begin()
upper_bound(key)会返回set中大于key的第一个数,如果set中没有大于key的数,那么会返回set.end()
2.用scanf读入double类型,%lf
3.注意:要用scanf读,用cin会超时,只能得90分
#include<iostream>
#include<cstdio>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int N = 100010;
map< int, set<int> > setX;//表示在每个x,当前y轴有镜子的点
map< int, set<int> > setY;
map<pair<int, int>, int> ptom;//point_to_mirror,表示pair这个点对应镜子的编号
//镜子结构体
struct mirror{
int id;
int x1,x2,y1,y2;
double a;
int direction;//左下到右上是1,左上到右下是0
//新加入一个镜子,第id个操作
void init(int ID,int a1,int b1,int a2,int b2,double A){
id=ID;
x1=a1,y1=b1,x2=a2,y2=b2;
a=A;
int minx=min(x1,x2),maxx=max(x1,x2),miny=min(y1,y2),maxy=max(y1,y2);
if((x1<x2 && y1<y2)||(x1>x2 && y1>y2)){
direction=1;
for(int i=minx+1,j=miny+1;i<maxx;i++,j++){
setX[i].insert(j);
setY[j].insert(i);
ptom[{i,j}]=id;//将点对应到镜子
}
}
else if((x1<x2 && y1>y2)||(x1>x2 && y1<y2)){
direction=0;
for(int i=minx+1,j=maxy-1;i<maxx;i++,j--){
setX[i].insert(j);
setY[j].insert(i);
ptom[{i,j}]=id;//将点对应到镜子
}
}
}
//删除镜子
void clr(){
int minx=min(x1,x2),maxx=max(x1,x2),miny=min(y1,y2),maxy=max(y1,y2);
if(direction==1){
for(int i=minx+1,j=miny+1;i<maxx;i++,j++){
setX[i].erase(j);
if(setX[i].size()==0) setX.erase(i);
setY[j].erase(i);
if(setY[j].size()==0) setY.erase(j);
ptom.erase({i,j});
}
}
else if(direction==0){
for(int i=minx+1,j=maxy-1;i<maxx;i++,j--){
setX[i].erase(j);
if(setX[i].size()==0) setX.erase(i);
setY[j].erase(i);
if(setY[j].size()==0) setY.erase(j);
ptom.erase({i,j});
}
}
}
};
mirror mirrorlist[N];
int m;//操作总数量
void reflect(int x,int y,int d,double I,int t){
if(I<1.0){//强度完全耗散了
printf("0 0 0\n");
return;
}
//d=0表示沿x坐标增加的方向,
//d=1表示沿y坐标增加的方向,
//d=2表示沿x坐标减小的方向,
//d=3表示沿y坐标减小的方向。
if(d==0){
if(setY.find(y)==setY.end())//当前行没有镜子
{
cout<<x+t<<' '<<y<<' '<<(int)I<<endl;//强度向下取整,直接转化为int即可
return;
}
set<int>::iterator it=setY[y].upper_bound(x);//找到第一个大于x的数
if(it==setY[y].end())//没有比x大的镜子,相当于后面不能反射了
{
cout<<x+t<<' '<<y<<' '<<(int)I<<endl;
return;
}
else{
int nextx=*it;
if(nextx-x>t){//剩余时间不能够到达这个镜子了
cout<<x+t<<' '<<y<<' '<<(int)I<<endl;
return;
}
else{//剩余时间能到达
int m_id=ptom[{nextx,y}];
I*=mirrorlist[m_id].a;
t-=(nextx-x);
if(mirrorlist[m_id].direction==1)//左下到右上
{
d=1;
}
else if(mirrorlist[m_id].direction==0){
d=3;
}
x=nextx;
}
}
}
else if(d==1){
if(setX.find(x)==setX.end()){
cout<<x<<' '<<y+t<<' '<<(int)I<<endl;
return;
}
auto it=setX[x].upper_bound(y);
if(it==setX[x].end()){
cout<<x<<' '<<y+t<<' '<<(int)I<<endl;
return;
}
else{
int nexty=*it;
if(nexty-y>t){
cout<<x<<' '<<y+t<<' '<<(int)I<<endl;
return;
}
else{
int m_id=ptom[{x,nexty}];
I*=mirrorlist[m_id].a;
t-=(nexty-y);
if(mirrorlist[m_id].direction==1){
d=0;
}
else{
d=2;
}
y=nexty;
}
}
}
else if(d==2){//沿x坐标减小的方向
if(setY.find(y)==setY.end())//当前行没有镜子
{
cout<<x-t<<' '<<y<<' '<<(int)I<<endl;//强度向下取整,直接转化为int即可
return;
}
auto it=setY[y].lower_bound(x);//返回不小于x的第一个数
if(it==setY[y].begin())//如果set中没有比y小的数
{
cout<<x-t<<' '<<y<<' '<<(int)I<<endl;
return;
}
else{//有比y小的数,找到离它最近的也就是排在它前面的一个
it--;
int nextx=*it;
if(x-nextx>t){
cout<<x-t<<' '<<y<<' '<<(int)I<<endl;
return;
}
else{
int m_id=ptom[{nextx,y}];
t-=(x-nextx);
I*=mirrorlist[m_id].a;
if(mirrorlist[m_id].direction==1){
d=3;
}
else d=1;
x=nextx;
}
}
}
else if(d==3){//沿y坐标减小的方向
if(setX.find(x)==setX.end()){
cout<<x<<' '<<y-t<<' '<<(int)I<<endl;
return;
}
auto it=setX[x].lower_bound(y);
if(it==setX[x].begin()){
cout<<x<<' '<<y-t<<' '<<(int)I<<endl;
return;
}
else{
it--;
int nexty=*it;
if(y-nexty>t){
cout<<x<<' '<<y-t<<' '<<(int)I<<endl;
return ;
}
else{
int m_id=ptom[{x,nexty}];
t-=(y-nexty);
I*=mirrorlist[m_id].a;
if(mirrorlist[m_id].direction==1) d=2;
else d=0;
y=nexty;
}
}
}
reflect(x,y,d,I,t);
}
int main(){
cin>>m;
int op,x1,y1,x2,y2,k,d,t;
double a,I;
int tot=0;//用来记录操作序列
while(m--){
tot+=1;
scanf("%d",&op);
if(op==1){
scanf("%d%d%d%d%lf",&x1,&y1,&x2,&y2,&a);
mirrorlist[tot].init(tot,x1,y1,x2,y2,a);
}
else if(op==2){
scanf("%d",&k);
mirrorlist[k].clr();
}
else{
scanf("%d%d%d%lf%d",&x1,&y1,&d,&I,&t);
// cout<<x1<<' '<<y1<<' '<<d<<' '<<(int)I<<' '<<t<<endl;
reflect(x1,y1,d,I,t);
}
}
return 0;
}
代码块用
``
的格式就更好了,否则
<>
会变成<>[HTML_REMOVED]
<>
中间有字母并且不是代码块就会变成如上啊?我这边代码块显示是正常的呀
2.点到镜子的映射map
map< pair[HTML_REMOVED],int >一个点x1,y1对应一个所属的镜子id
题解里,代码里没问题
嗷嗷好的 我下次注意 谢谢~