D
2024-10-06 15:59:07
发布于:浙江
#include<bits/stdc++.h>
using namespace std;
int T,C;
bool ini_v[200100];
set<int>se[10];
int cnt[10][200100];
char s[100100];
int ans;
/*
1 l->r 将后面所有的射击位置移 2 位
2 l->f 将后面所有的射击位置移 1 位,并增加一个射击位
3 r->l 将后面所有的射击位置移 -2位
4 r->f 将后面所有的射击位置移 -1位,并增加一个射击位
4 f->l 将后面所有的射击位置移 -1位,并减少一个射击位
2 f->r 将后面所有的射击位置移 1位,并减少一个射击位
位置变化其实一共只有2,1,-2,-1四种情况s
*/
int main(){
cin>>T>>C;
for(int i=1;i<=T;i++){
int x;
cin>>x;
x+=100010;
ini_v[x]=1;//标记所有的靶子
}
cin>>(s+1);
int loc=100010;//用来表示张三所处的位置
//整体移动2,1,-2,-1并将其对应的射击位置保存到set中
for(int i=1;i<=C;i++){
if(s[i]=='L') loc--;//向左移动
else if(s[i]=='R') loc++;//向右移动
else if(s[i]=='F'){//射击
if(ini_v[loc]==1) se[0].insert(loc),cnt[0][loc]++;//不做修改的情况,如果当前位置有靶子,则保存该位置
if(ini_v[loc+2]==1) se[1].insert(loc+2),cnt[1][loc+2]++;// 整体+2
if(ini_v[loc+1]==1) se[2].insert(loc+1),cnt[2][loc+1]++;// 整体+1
if(ini_v[loc-2]==1) se[3].insert(loc-2),cnt[3][loc-2]++;// 整体-2
if(ini_v[loc-1]==1) se[4].insert(loc-1),cnt[4][loc-1]++;// 整体-1
}
}
//枚举答案
loc=100010;//张三初始位置
ans=se[0].size();//不做修改的情况作为初始ans
se[0].clear();//枚
for(int i=1;i<=C;i++){
if(s[i]=='L'){//当前字符为L,有两种修改方式。
//L->R
ans=max(ans,(int)(se[0].size()+se[1].size()));//左边+右边
//L->F
int tmp=0;
//修改成F,增加一个射击位置
// (当前位置有靶子 并且 左右两边都没有射击过该靶子 才可以)
if(ini_v[loc]&&!se[0].count(loc)&&!se[2].count(loc)) tmp=1;
ans=max(ans,(int)(se[0].size()+tmp+se[2].size()));//左边+新靶子+右边
loc--;
}
else if(s[i]=='R'){// 当前字符为R(基本同字符为L的情况)
//R->L
ans=max(ans,(int)(se[0].size()+se[3].size()));
//R->F
int tmp=0;
if(ini_v[loc]&&!se[0].count(loc)&&!se[4].count(loc)) tmp=1;//修改成F,增加一个射击位置
ans=max(ans,(int)(se[0].size()+tmp+se[4].size()));
loc++;
}
else if(s[i]=='F'){
//因为要将F修改为L或R,所以会减少一个射击位置
if(--cnt[1][loc+2]<=0) se[1].erase(loc+2); //如果loc+2这个位置只出现过一次,则在se[1]中将其删除
if(--cnt[2][loc+1]<=0) se[2].erase(loc+1); //如果loc+1这个位置只出现过一次,则在se[2]中将其删除
if(--cnt[3][loc-2]<=0) se[3].erase(loc-2); //如果loc-2这个位置只出现过一次,则在se[3]中将其删除
if(--cnt[4][loc-1]<=0) se[4].erase(loc-1); //如果loc-1这个位置只出现过一次,则在se[4]中将其删除
ans=max(ans,(int)(se[0].size()+se[4].size())); //修改成L,左边+右边
ans=max(ans,(int)(se[0].size()+se[2].size())); //修改成R,左边+右边
if(ini_v[loc]==1) se[0].insert(loc);
//当前这个loc位置如果有靶子,一定会在se[0]里面 ,所以需要将其他几个集合中的loc删掉,避免重复计算
se[1].erase(loc);
se[2].erase(loc);
se[3].erase(loc);
se[4].erase(loc);
}
}
cout<<ans<<endl;
return 0;
}
// 1.对于每一个点的边按照加入飞机的时间从大到小排序,当前这条边对于飞机已经进不去了
// 后面的飞机更加不行
// 2.对于一个航线,如果已经走过,这一条航线就不需要走第二次
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edge{
int c,r,d,s,id;//航线编号
};
bool cmp(edge a,edge b){
return a.r>b.r;
}
vector<edge> ve[200100];//邻接表存图,ve[x]存的是所有从x出发的航线
int a[200100];//停泊时间
int dis[200100];//dis[i]表示起点到达点i的最早时间
int start[200100];//标记每个点从哪条航线开始搜索
bool vis[200100];
void dfs(int x){//当前搜索点x
int t = dis[x];
/*
必须要用变量t保存一下时间;
如果后面直接用dis[x]的话,有可能在之后的搜索过程中
再回到x点并修改dis[x]的值,从而导致代码超时
*/
for(int i=0;i<ve[x].size();i++){//for(int i=start[x];i<ve[x].size();i++){
int y=ve[x][i].d,r=ve[x][i].r,s=ve[x][i].s,id=ve[x][i].id;
//if(vis[id]) continue;
//start[x]=i;
int wait=0;
if(x!=1) wait=a[x];//x==1时在起点位置,不需要停泊
if(t+wait>r) break;
if(t+wait<=r&&dis[y]>s){
//可以在规定时间前进入飞机 并且 到达城市y的时间更早
vis[id]=1;
dis[y]=s;
dfs(y);
}
}
}
int main(){
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int c,r,d,s;
cin>>c>>r>>d>>s;
ve[c].push_back((edge){c,r,d,s,i});//存图
}
for(int i=1;i<=n;i++){
cin>>a[i];
sort(ve[i].begin(),ve[i].end(),cmp);
}
memset(dis,0x3f,sizeof(dis));//将所有dis初始化为极大值
dis[1]=0;//0时刻就在城市1
dfs(1);
for(int i=1;i<=n;i++){//for循环输出到达时间
if(dis[i]==dis[0]) cout<<-1<<endl;//无法到达输出-1
else cout<<dis[i]<<endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}
这里空空如也
有帮助,赞一个