2021牛客暑期多校训练营#2:L-WeChat Walk

L-WeChat Walk

原题链接：https://ac.nowcoder.com/acm/contest/11253/L

题目大意

有$n(1\le n\le 2?10^5)$个人，他们的好友关系可以用有$n$个点，$m(1\le m\le 2?10^5)$的图来表示。

每个人会给出ta的微信步数，如果一个人的微信步数大于零，且严格大于他好友列表中任何一个人的步数，则称ta为“步数冠军”。

一天被分成$q$个时刻，求每个人是“步数冠军”的时间总合。每一时刻，编号为$u$的人，新走了$m$步。

任何人的总步数均不超过$10^4$。

解题思路

1

我们先考虑能否直接枚举每个点：

此图为完全图时：
在草稿纸上一算，$O(mq)$!tle是少不了了。

此图为菊花图时：

拿出万能的草稿纸，一算，可不得了，$O(m^{2}q)$,憋想了。

不对，加几个特判也还是一条好汉！那这可怎么办?:

所以说，不要妄想全部暴力了。

2

对于朋友比较少的人比如我，祭出我们的二分打法，来试试看吧！

将枚举的人用函数表示，如下图：

ta的朋友与ta的关系如下：

“步数冠军”是蓝线：

那么，求每个人获得的蓝线总量即可。

代码

for(int j=0;j<tm[i].size();j ++){
    int y=tm[i][j].second;int x=tm[i][j].first;int r=q;if(j<tm[i].size()-1)r=tm[i][j+1].second;for(auto v:e[i]){
    auto it=lower_bound(tm[v].begin(),tm[v].end(),(pair<int,int>){
    x,0});if(it!=tm[v].end())r=min(r,(*it).second);}ans+=max(0,r-y) ;} 

3

当一个人朋友很多时，显然不能直接枚举。

ta和ta的朋友表示如下：

“步数冠军”还是用蓝线表示：

每一时刻都对应一个步数，对应那一刻的“步数冠军”，把所有作为步数冠军的时间加起来，就得到了答案。

代码

vector<int>res(10010,q+10);for(auto v:e[i])for(auto x:tm[v])res[x.first]=min(res[x.first],x.second);for(int i=9999;i>=1;i--)res[i]=min(res[i],res[i+1]);for(int j=0;j<tm[i].size();j++){
    int y=tm[i][j].second;int x=tm[i][j].first;int r=q;if(j<tm[i].size()-1)r=tm[i][j+1].second;r=min(r,res[x]) ;ans+=max(0,r-y) ;}

4

由分块思想得出大小点判断应以$\sqrt{n}$为分界点此题完结。

代码实现

ac代码如下

#include<bits/stdc++.h>
using namespace std;
const int s=447;
int n,m,q;
int main()
{
    cin>>n>>m>>q;vector < vector< pair<int,int> > >tm(n+100); vector<vector<int> > e(n+100);for(int i=0;i<m;i++){
    int x,y,u;cin>>x>>y;e[x].push_back(y),e[y].push_back(x);}for(int i=1;i<=q;i++){
    int u,w;cin>>u>>w;tm[u].push_back({
    w,i});}for(int i=1;i<=n;i++)for(int j=1;j<tm[i].size();j++)tm[i][j].first+=tm[i][j-1].first;for(int i=1;i<=n;i++){
    int ans=0; if(e[i].size()<=s){
    for(int j=0;j<tm[i].size();j ++){
    int y=tm[i][j].second;int x=tm[i][j].first;int r=q;if(j<tm[i].size()-1)r=tm[i][j+1].second;for(auto v:e[i]){
    auto it=lower_bound(tm[v].begin(),tm[v].end(),(pair<int,int>){
    x,0});if(it!=tm[v].end())r=min(r,(*it).second);}ans+=max(0,r-y) ;} }else{
    vector<int>res(10010,q+10);for(auto v:e[i])for(auto x:tm[v])res[x.first]=min(res[x.first],x.second);for(int i=9999;i>=1;i--)res[i]=min(res[i],res[i+1]);for(int j=0;j<tm[i].size();j++){
    int y=tm[i][j].second;int x=tm[i][j].first;int r=q;if(j<tm[i].size()-1)r=tm[i][j+1].second;r=min(r,res[x]) ;ans+=max(0,r-y) ;}}cout<<ans;puts("");}}	

ps:

这是我的第八篇博客，也是我最长最详细的一篇。