Problem - E - Codeforces

思路:最短路变种，每个点都有两种状态。分别是从不骑马到达的状态，和骑马到达的状态。要注意的是，如果当前点是有马的，而前一个点是不骑马过来的，那么更新也直接更新为当前骑马的状态，可以直接舍去当前点不骑马的状态。因为当前点不骑马的状态已经没有意义了，既然当前点可以骑马，那么后面肯定全部骑马。如果一个点可以由骑马的到达，也可以由不骑马的到达，那么两个状态都要保留，不一定骑马的就是更优的。因此vis要有两种状态，pq要存三个值，这样的话每个点最多遍历两次，不会超时。记录每个点由不骑马的到达和骑马的到达需要的最短时间后。枚举相遇点，取两种状态的最小值，再取最大值就是当前点最小的相遇时间。

int n,m,h;
vector<pair<int,int>> vct[200005];
bool mark[200005];
priority_queue<pair<int,pair<int,int>>> pq;
int dis1[200005][2],dis2[200005][2];   0为没有骑马,1为骑马
map<pair<int,int>,int> vis;  <from,状态>
void dijkstra(int s,int typ){vis.clear();if(typ==1) for(int i=1;i<=n;i++) dis1[i][0]=dis1[i][1]=LONG_LONG_MAX/2;if(typ==2) for(int i=1;i<=n;i++) dis2[i][0]=dis2[i][1]=LONG_LONG_MAX/2;typ==1?dis1[s][0]=0:dis2[s][0]=0;if(mark[s]&&typ==1) dis1[s][1]=0;if(mark[s]&&typ==2) dis2[s][1]=0;pq.push({0,{s,mark[s]}});   <权重,<from,状态>>while(pq.size()){int from=pq.top().second.first,sta=pq.top().second.second;pq.pop();if(vis[{from,sta}]) continue;vis[{from,sta}]=1;for(auto v:vct[from]){int to=v.first,w=v.second;if(typ==1){if(sta){if(dis1[to][1]>dis1[from][1]+w/2){dis1[to][1]=dis1[from][1]+w/2;pq.push({-dis1[to][1],{to,1}});}}else if(mark[to]){if(dis1[to][1]>dis1[from][0]+w){dis1[to][1]=dis1[from][0]+w;pq.push({-dis1[to][1],{to,1}});}}else{if(dis1[to][0]>dis1[from][0]+w){dis1[to][0]=dis1[from][0]+w;pq.push({-dis1[to][0],{to,0}});}}}if(typ==2){if(sta){if(dis2[to][1]>dis2[from][1]+w/2){dis2[to][1]=dis2[from][1]+w/2;pq.push({-dis2[to][1],{to,1}});}}else if(mark[to]){if(dis2[to][1]>dis2[from][0]+w){dis2[to][1]=dis2[from][0]+w;pq.push({-dis2[to][1],{to,1}});}}else{if(dis2[to][0]>dis2[from][0]+w){dis2[to][0]=dis2[from][0]+w;pq.push({-dis2[to][0],{to,0}});}}}}}
}
void solve(){           Ecin>>n>>m>>h;for(int i=1;i<=n;i++) vct[i].clear(),mark[i]=false;for(int i=1;i<=h;i++){int x; cin>>x;mark[x]=true;}for(int i=1;i<=m;i++){int u,v,w; cin>>u>>v>>w;vct[u].emplace_back(v,w);vct[v].emplace_back(u,w);}dijkstra(1,1);dijkstra(n,2);if(dis1[n][0]==LONG_LONG_MAX/2&&dis1[n][1]==LONG_LONG_MAX/2){cout<<"-1"<<endl;return;}else{int ans=LONG_LONG_MAX;for(int i=1;i<=n;i++) ans=min(ans,max(min(dis1[i][0],dis1[i][1]),min(dis2[i][0],dis2[i][1])));cout<<ans<<endl;}
}

Problem - H - Codeforces

思路:莫队的模板题,直接从洛谷上面复制之前写的代码,改一下就行了.

int n,m,B;
int arr[250004],p[250004];
typedef struct Q{int l,r,idx;
}Q;
Q q[250004];
//bool cmp(Q a,Q b){     普通分块排序
//    if(a.l/B!=b.l/B) return a.l<b.l;
//    return a.r<b.r;
//}
bool cmp(Q a,Q b){   玄学奇偶性排序if (p[a.l] ^ p[b.l]) return a.l/B < b.l/B ;else{if (p[a.l] & 1) return a.r < b.r;else return a.r > b.r;}
}
int l=0,r=0,cnt[1000006],ans[250004];
P2709 小B的询问
https://www.luogu.com.cn/problem/P2709
void solve(){                       H    莫队轻松过cin>>n>>m;B=sqrt(n);for(int i=1;i<=n;i++) cin>>arr[i],cnt[arr[i]]=0;for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].idx=i,p[q[i].l]=q[i].l/B,p[q[i].r]=q[i].r/B;sort(q+1,q+m+1,cmp);l=q[1].l+1,r=q[1].l;int cnt1=0;for(int i=1;i<=m;i++){while(l>q[i].l) {--l;cnt[arr[l]]^=1;if(cnt[arr[l]]==1) cnt1++;else cnt1--;}while(r<q[i].r) {++r;cnt[arr[r]]^=1;if(cnt[arr[r]]==1) cnt1++;else cnt1--;}while(l<q[i].l) {cnt[arr[l]]^=1;if(cnt[arr[l]]==1) cnt1++;else cnt1--;l++;}while(r>q[i].r) {cnt[arr[r]]^=1;if(cnt[arr[r]]==1) cnt1++;else cnt1--;r--;}ans[q[i].idx]=(cnt1==0);}for(int i=1;i<=m;i++){if(ans[i]==1) cout<<"YES\n";else cout<<"NO\n";}
}