2022 HDU多校5

本文主要是介绍2022 HDU多校5，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Pandaemonium Asphodelos: The First Circle (Savage)(数据结构)

Problem

有一行长度为\(n\)个格子，一开始每个格子的颜色都是\(0\)，并且权值都也是\(0\)，现在有\(q\)次操作，每次操作有\(4\)种类型

• 1 x c：把与第\(x\)格子和距离最近第\(x\)格子最近的\(2c\)个格子染上一种新的颜色
• 2 x y：把第\(y\)个格子所在连通块(颜色相同的连通块)染成了第\(x\)格子相同的颜色
• 3 x v：把和第\(x\)个格子的颜色相同的所有格子的权值加\(v\)
• 4 x：查询第\(x\)个格子的权值

\(1\le n\le 10^8\)，\(1\le q\le 10^5\)

Solve

把一段区间改成相同的颜色，可以想到利用珂朵莉树。

然后用一个动态开点线段树维护每个格子与现在颜色不同的以前染过的颜色的权值。记录每个颜色的当前的权值是多少

ODT的模板大概是这样的

struct ODT{
    map<int,T>seg;
    void init(int st,int ed){
        seg[st-1]=seg[ed+1]=null;
        seg[st]=init_state;
    }
    auto find(int p){
        return prev(seg.upper_bound(p));
    }
    typedef map<int,T>::interator iter;
    void op(iter l,iter r,T data){

    }
    void split(int l,int r,T new_data){
        auto i=find(l),j=find(r+1);
        seg[l]=i->second;
        seg[r+1]=j->second;
        for(auto it=find(l);it->second!=r+1;it=odt.erase(i)){
            op(it->first,next(it)->first-1,it->second);
        }
        seg[l]=new_data;
    }
}

其中data是区间维护的数据，op是删除区间的时候需要对区间数据进行的操作

更加具体的细节看代码注释，数据结构只可意会不可言传

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
struct node{
    int ls,rs;
    ll sum;
}tr[N*40];
int idx,root;
//动态开点线段树维护每个点与现在颜色不同的以前染过的颜色的权值
void update(int &rt,int L,int R,int l,int r,ll x){
      if(!rt){
        rt=++idx;
        tr[rt].ls=tr[rt].rs=tr[rt].sum=0;
      }
      if(l<=L&&R<=r){
        tr[rt].sum+=x;
        return;
      }
      int mid=(L+R)>>1;
      if(l<=mid) update(tr[rt].ls,L,mid,l,r,x);
      if(r>mid) update(tr[rt].rs,mid+1,R,l,r,x);
}
ll query(int rt,int L,int R,int pos){
    if(!rt) return 0;
    int mid=(L+R)>>1;
    ll ans=tr[rt].sum;
    if(pos<=mid) ans+=query(tr[rt].ls,L,mid,pos);
    else ans+=query(tr[rt].rs,mid+1,R,pos);
    return ans;
}
//ODT进行推平操作
struct ODT{
    map<int,int>odt; //<左端点，区间颜色>
    //只记录左端点，右端点可以由下一个左端点-1取定
    map<int,int>::iterator find(int pos){
       return prev(odt.upper_bound(pos)); 
       //返回的区间位置是[prev(upper_bound(pos))->first,upper_bound(pos)->first-1]
       //然后需要分裂成[prev(upper_bound(pos))->first,pos-1],[pos,upper_bound(pos)->first-1]
    }
    void split(int pos){
        auto it=find(pos);
        odt[pos]=it->second;
        //插入pos区间，并且颜色相同
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        idx=root=0;
        int n,q;
        cin>>n>>q;
        ll last=0;
        ODT t;
        vector<ll>w(q+1,0);//记录每一种颜色的权值
        t.odt[0]=t.odt[n+1]=-1;
        t.odt[1]=0;
        for(int k=1;k<=q;k++){
            int op;
            cin>>op;
            if(op==1){
               int x,c;
               cin>>x>>c;
               x=((x-1)^last)%n+1,c=((c-1)^last)%((n-1)/2)+1;
               int l=max(1,x-c),r=l+2*c;
               if(r>n) l=n-2*c,r=n;
               //把[l,r]内的格子染上一种新的颜色
               t.split(l),t.split(r+1);
               //先找到区间位置并插入
               //删除[l,r]之间之前的区间
               //map的erase一个元素之后返回这个元素下一个的迭代器
               for(auto i=t.find(l);i->first!=r+1;i=t.odt.erase(i)){
                 update(root,1,n,i->first,next(i)->first-1,w[i->second]);
                 //更改区间颜色
               }
               t.odt[l]=k;//染上新的颜色
            }else if(op==2){
                int x,y;
                cin>>x>>y;
                x=((x-1)^last)%n+1,y=((y-1)^last)%n+1;
                auto i=t.find(x),j=t.find(y);
                if(i->second==j->second){
                    continue;
                }
                //对于y所在的连通块来说，本来的颜色变成了过去的颜色，i的颜色变成了新的颜色，但y可能过去染上过i的颜色
                update(root,1,n,j->first,next(j)->first-1,w[j->second]-w[i->second]);
                j->second=i->second;
                //y向后合并颜色相同的
                while(j->second==next(j)->second) t.odt.erase(next(j));
                //y向前合并颜色相同的
                while(j->second==prev(j)->second){
                    j=prev(j);
                    t.odt.erase(next(j));
                }
            }else if(op==3){
                int x,v;
                cin>>x>>v;
                x=((x-1)^last)%n+1;
                w[t.find(x)->second]+=v;
            }else{
                int x;
                cin>>x;
                x=((x-1)^last)%n+1;
                //x以前颜色产生的权值+现在颜色的权值
                ll ans=query(root,1,n,x)+w[t.find(x)->second];
                cout<<ans<<'\n';
                last=ans&1073741823;
            }
        }
    }
    return 0;
}

Jo loves counting(数论、PN 筛)

Problem

计算

\[\frac{1}{M}\sum_{i=1}^M\frac{i}{\prod_{j=1}^{m_i}\alpha_j}，其中i=\prod_{j=1}^{m_i}p_j^{\alpha_j} \]

\(1\le M\le 10^{12}\)

Solve

利用这个题学会了\(\text{PN}\)筛

令\(f(i)=\frac{i}{\prod_{j=1}^{m_i}\alpha_j}\)，容易知道\(f\)是一个积性函数，并且\(f(1)=1\)。因此要求\(\frac{1}{M}\sum_{i=1}^Mf(i)\)

考虑\(\text{PN}\)筛计算\(f\)的前缀和

由于\(f(i)=\frac{i}{\prod_{j=1}^{m_i}\alpha_j}\)，所以不妨令\(g(i)=i\)，则\(f(p)=p=g(p)\)，并且\(G(n)=\frac{n(n+1)}{2}\)非常好计算。令\(f=h*g\)，现在考虑怎么计算\(h\)，更具体，我们考虑怎么计算\(h(p^k)\)

\[f(p^k)=\frac{p^k}{k}=\sum_{i=0}^kh(p^i)g(p^{k-i})=\sum_{i=0}^kh(p^i)p^{k-i}\\ \frac{1}{k}=\sum_{i=0}^k\frac{h(p^i)}{p^i}\\ \frac{h(p^k)}{p^k}=\frac{1}{k}-\frac{1}{k-1}=\frac{1}{k(k-1)}\\ h(p^k)=\frac{p^k}{\frac{k}{k-1}} \]

所以\(h(p^k)\)表示成了之与\(p,k\)有关的公式了，可以直接计算

\[\sum_{i=1}^Mf(i)=\sum_{i=1}^M\sum_{d|i}h(d)g(\frac{i}{d})\\ =\sum_{d=1}^M\sum_{i=1}^{\lfloor \frac{M}{d} \rfloor} h(d)g(i)\\ =\sum_{d=1}^Mh(d)\frac{\lfloor \frac{M}{d} \rfloor (\lfloor \frac{M}{d} \rfloor +1)}{2} \]

变成了范式的形式，就可以计算了

具体就类似于二进制枚举，当前用到了哪些素因数，并且素因数的幂次是多少，就这样一个一个枚举。

类似于分组，我们先把所有具有因子\(p_i^{k_i}\)的\(PN\)数贡献计算，显然我们可以先提出\(h(p_i^{k_i})\)，这个直接用公式计算，然后根据积性函数，计算剩下的除去因子\(p_i^{k_i}\)的\(PN\)数，这里计算也是递归地分组，最后算完后乘上\(h(p_i^{k_i})\)就可以了。

Code

注意可能会爆long long，要用__int128_t

#include <bits/stdc++.h>
#define int128 __int128_t
#define int64 long long
using namespace std;
const int N=1e6+10;
const int64 mod=4179340454199820289;
int primes[N],st[N],cnt;
int64 inv[64];
void get_primes(){
    for(int i=2;i<=1000000;i++){
        if(!st[i]) primes[++cnt]=i;
        for(int j=1;j<=cnt&&primes[j]*i<=1000000;j++){
           st[primes[j]*i]=1;
           if(i%primes[j]==0) break;
        }
    }
}
int64 power(int64 x,int64 y){
    int64 res=1;
    while(y){
        if(y&1) res=(int128)res*x%mod;
        x=(int128)x*x%mod;
        y>>=1;
    }
    return res;
}
int64 h(int64 p,int64 k,int64 pk){
    return mod-(int128)pk*inv[k]%mod*inv[k-1]%mod;
}
int64 PN(int pos,int64 m,int64 preh){
    //每一次枚举的m都是一个PN数，都要累加到答案里面，并且base是(m)，然后不断再从m中找PN数
    int64 ans=(int128)m*(m+1)%mod*inv[2]%mod*preh%mod;
    for(int i=pos;i<=cnt;i++){
        int k=1;
        int64 x=m/primes[i];
        int64 pk=primes[i];
        if(x<primes[i]) break;
        while(x>=primes[i]){
            k++;
            x/=primes[i];
            pk*=primes[i];
            ans=(ans+PN(i+1,x,(int128)preh*h(primes[i],k,pk)%mod))%mod;
        }
    }
    return ans;
}
int main(){
    get_primes();
    for(int64 i=1;i<=63;i++) inv[i]=power(i,mod-2);
    int T;
    cin>>T;
    while(T--){
        int64 m;
        cin>>m;
        int64 ans=PN(1,m,1)*(int128)power(m,mod-2)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

Slipper(图论、建图)

Problem

给定给一个\(n\)个点的树，以\(1\)为根，数边有边权\(w_i\)，现在要从\(u\)总到\(v\)，你可以使用若干次传送，花费\(p\)元，从一个点\(x\)传送到另一个点\(y\)需要满足\(|dep_x-dep_y|=k\)，问最小需要的花费是多少

Solve

假设最大深度是\(m\)，对每个深度额外建立\(m\)个点，同一深度\(i\)的树上的点都向表示深度\(i-k\)和深度\(i+k\)的点连边权为\(p\)的点，然后每个表示深度的点都向树上所有在这个深度上的点连边权为\(0\)的边，表示深度的点之间深度相差为\(k\)的点也连边权为\(p\)的边，然后跑一次最短路即可

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        vector<vector<pair<int,int>>> E(2*n+1);
        for(int i=1;i<n;i++){
            int u,v,w;
            cin>>u>>v>>w;
            E[u].emplace_back(v,w);
            E[v].emplace_back(u,w);
        }
        int p,k;
        cin>>k>>p;
        int s,t;
        cin>>s>>t;
        vector<int>dep(n+1);
        int m=0;
        auto get_dep=[&](auto self,int u,int fa)->void{
            dep[u]=dep[fa]+1;
            m=max(m,dep[u]);
            for(auto t:E[u]){
               int v=t.first;
               if(v==fa) continue;
               self(self,v,u);
            }
        };
        get_dep(get_dep,1,0);
        for(int u=1;u<=n;u++){
            if(dep[u]>k) E[u].emplace_back(n+dep[u]-k,p);
            if(dep[u]+k<=m) E[u].emplace_back(n+dep[u]+k,p);
            E[n+dep[u]].emplace_back(u,0);
        }
        for(int i=n+1;i<=n+m-k;i++)
            E[i].emplace_back(i+k,p),E[i+k].emplace_back(i,p);
        priority_queue<pair<ll,int>>q;
        vector<ll>dist(m+n+1,inf);
        vector<bool>vis(m+n+1);
        dist[s]=0;
        q.push({0,s});
        while(q.size()){
            int u=q.top().second;
            q.pop();
            if(vis[u]) continue;
            vis[u]=1;
            for(auto t:E[u]){
                int v=t.first;
                ll w=t.second;
                if(dist[v]>dist[u]+w){
                    dist[v]=dist[u]+w;
                    q.push({-dist[v],v});
                }
            }
        }
        cout<<dist[t]<<'\n';
    }
}

The Surveying(计算几何、暴力判断、状态压缩、)

Problem

二维平面给出\(m\)个矩形和和\(n\)个观测点，从中选出最少的观测点，使得在这几个观测点可以看到所有矩形的 4 个顶点，并且每个观测点至少要可以被另外一个观测点观测到.

\(1\le n\le 20\)，\(1\le m\le 100\)

Solve

• 发现\(n\)很小，所以直接枚举所有矩形的点，对每个观测点，检查它可以看到哪些矩形的点，可以用bietst来记录，时间复杂度\(O(\frac{4nm}{w})\)
• 每个观测点要至少可以被另一个观测点看到，也是暴力预处理判断，时间复杂度是\(O(n^2)\)
• 最少二进制枚举选取的观测点集合，然后判断这些点是否可以看到所有的矩形顶点，并且至少可以被另外一个观测看看到，时间复杂度\(O(2^nn^2)\)

需要注意的是这里的非规范相交是允许的，即在端点出相交

Code

#include <bits/stdc++.h>
using namespace std;
const double eps=1e-8;
int sgn(double x){
    if(fabs(x)<eps) return 0;
    else if(x>0) return 1;
    else return -1;
}
int dcmp(double x,double y){
    if(fabs(x-y)<eps) return 0;
    else if(x<y) return -1;
    else return 1;
}
struct Point{
    double x,y;
    Point operator + (const Point &t)const{
        return {x+t.x,y+t.y};
    }
    Point operator - (const Point &t)const{
        return {x-t.x,y-t.y};
    }
    double operator * (const Point &t)const{
        return x*t.x+y*t.y;
    }
    double operator ^ (const Point &t)const{
        return x*t.y-y*t.x;
    }
    bool operator == (const Point &t)const{
        if(dcmp(x,t.x)==0 && dcmp(y,t.y)==0) return 1;
        else return 0;
    }
}p[25],a[405];
struct Line{
    Point s,e;
    int segcrossseg(Line v){
        int d1 = sgn((e-s)^(v.s-s));
        int d2 = sgn((e-s)^(v.e-s));
        int d3 = sgn((v.e-v.s)^(s-v.s));
        int d4 = sgn((v.e-v.s)^(e-v.s));
        if( (d1^d2)==-2 && (d3^d4)==-2 )return 1;
        return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) ||
            (d2==0 && sgn((v.e-s)*(v.e-e))<=0) ||
            (d3==0 && sgn((s-v.s)*(s-v.e))<=0) ||
            (d4==0 && sgn((e-v.s)*(e-v.e))<=0);
    }
}line[405];
typedef Point Vector;
bitset<401>f[25],t;
int g[25],cp[25];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
       int n,m;
       cin>>n>>m;
       t.reset();
       for(int i=0;i<n;i++) f[i].reset(),g[i]=0;
       for(int i=0;i<n;i++) cin>>p[i].x>>p[i].y;
       m*=4;
       for(int i=0;i<m;i+=4){
          for(int j=i;j<i+4;j++) cin>>a[j].x>>a[j].y;
          for(int j=i;j<i+3;j++) line[j]={a[j],a[j+1]};
          line[i+3]={a[i+3],a[i]};
       }
       auto check=[&](Line t)->bool{
         for(int i=0;i<m;i++){
            if(t.segcrossseg(line[i])!=0 && !(t.e==line[i].e || t.e==line[i].s)) return 0;
         }
         return 1;
       };
       for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            f[i][j]=check({p[i],a[j]});
        }

       for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(i!=j)
            g[i]|=check({p[i],p[j]})? 1<<j:0;

       int ans=n+1,id;

       for(int S=0;S<(1<<n);S++){
          t=0;
          id=0;
          for(int i=0;i<n;i++){
            if((S>>i)&1) t|=f[i],cp[id++]=i;
          }
          if(t.count()!=m) continue;
          int ok=1;
          for(int i=0;i<id;i++){
             bool flag=false;
             for(int j=0;j<id;j++){
                if((g[cp[j]]>>cp[i]&1)){
                    flag=true;
                    break;
                }
             }
             ok=ok&flag;
          }
          if(ok) ans=min(ans,__builtin_popcount(S));
       }
       if(ans==n+1) cout<<"No Solution!\n";
       else cout<<ans<<'\n';
    }
    return 0;
}

Count Set(分治 NTT、生成函数)

Problem

给定一个长度为\(n\)的排列\(p\)，给定一个集合\(S=\{1,2,\cdots,n\}\)，问\(S\)有几个子集满足\(|T|=k\)并且\(|P(T)\bigcap T|=0\)，其中\(P(T)=\{y|y=p_x,x\in T\}\)

\(1\le n\le 5\times 10^5\)

Solve

排列问题一般考虑置换环，发现对于一个置换环，不能选择环上相邻的数，所以现在考虑一个环选择\(i\)个不相邻数的方案

在大小为\(n\)的环中选择\(i\)个不相邻的数，假设环里面的数按照\(1\)到\(n\)重新标号，按照\(1\)号点选不选分成两种情况：

• \(1\)号点选，则左右两边的点不选，那么可以变成一个长度为\(n-3\)的链，就是在\(n-3\)个数中选择\(i-1\)个数
• \(1\)号点不选，则在\(1\)号点处断开称一条长度为\(n-1\)的链，就是在\(n-1\)个数里面选择\(i\)个数
• 考虑在\(n\)个数里面选择不相邻的\(i\)个数的方案，就是在\(n-i\)个数里面插空加入\(i\)个数的方案即\(\binom{n-i+1}{i}\)

于是总方案就是\(\binom{n-i-1}{i-1}+\binom{n-i}{i}\)

根据鸽笼原理，如果\(i\gt frac{n}{2}\)，那么一定会选到相邻的两个数，所以只考虑\(i\le frac{n}{2}\)

对于每一个环计算所有选择\(i\)个数的情况，然后即使卷积计算每个环选择数的方案组合成\(k\)个数的方案就可，使用分治 NTT 即可

Code

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

const int N = 1e6+10;
const int mod=998244353;
//const ll mod = 31525197391593473, G = 3;
ll qpow(ll a, int b)
{
    ll res = 1;
    while(b) {
        if(b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

namespace Poly
{
    #define mul(x, y) (1ll * x * y >= mod ? 1ll * x * y % mod : 1ll * x * y)
    #define minus(x, y) (1ll * x - y < 0 ? 1ll * x - y + mod : 1ll * x - y)
    #define plus(x, y) (1ll * x + y >= mod ? 1ll * x + y - mod : 1ll * x + y)
    #define ck(x) (x >= mod ? x - mod : x)//取模运算太慢了

    typedef vector<ll> poly;
    const int G = 3;//根据具体的模数而定，原根可不一定不一样！！！
    //一般模数的原根为 2 3 5 7 10 6
    const int inv_G = qpow(G, mod - 2);
    int RR[N], deer[2][20][N], inv[N];

    void init(const int t) {//预处理出来NTT里需要的w和wn，砍掉了一个log的时间
        for(int p = 1; p <= t; ++ p) {
            int buf1 = qpow(G, (mod - 1) / (1 << p));
            int buf0 = qpow(inv_G, (mod - 1) / (1 << p));
            deer[0][p][0] = deer[1][p][0] = 1;
            for(int i = 1; i < (1 << p); ++ i) {
                deer[0][p][i] = 1ll * deer[0][p][i - 1] * buf0 % mod;//逆
                deer[1][p][i] = 1ll * deer[1][p][i - 1] * buf1 % mod;
            }
        }
        inv[1] = 1;
        for(int i = 2; i <= (1 << t); ++ i)
            inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
    }

    int NTT_init(int n) {//快速数论变换预处理
        int limit = 1, L = 0;
        while(limit < n) limit <<= 1, L ++ ;
        for(int i = 0; i < limit; ++ i)
            RR[i] = (RR[i >> 1] >> 1) | ((i & 1) << (L - 1));
        return limit;
    }

    void NTT(poly &A, int type, int limit) {//快速数论变换
        A.resize(limit);
        for(int i = 0; i < limit; ++ i)
            if(i < RR[i])
                swap(A[i], A[RR[i]]);
        for(int mid = 2, j = 1; mid <= limit; mid <<= 1, ++ j) {
            int len = mid >> 1;
            for(int pos = 0; pos < limit; pos += mid) {
                int *wn = deer[type][j];
                for(int i = pos; i < pos + len; ++ i, ++ wn) {
                    int tmp = 1ll * (*wn) * A[i + len] % mod;
                    A[i + len] = ck(A[i] - tmp + mod);
                    A[i] = ck(A[i] + tmp);
                }
            }
        }
        if(type == 0) {
            for(int i = 0; i < limit; ++ i)
                A[i] = 1ll * A[i] * inv[limit] % mod;
        }
    }

    inline poly poly_mul(poly A, poly B) {//多项式乘法
        int deg = A.size() + B.size() - 1;
        int limit = NTT_init(deg);

        poly C(limit);
        NTT(A, 1, limit);
        NTT(B, 1, limit);
        for(int i = 0; i < limit; ++ i)
            C[i] = 1ll * A[i] * B[i] % mod;
        NTT(C, 0, limit);
        C.resize(deg);
        return C;
    }
}


const int M=5e5;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("gen.in","r",stdin);
    Poly::init(19);
    vector<ll>fac(M+1),infac(M+1);
    fac[0]=1;
    for(int i=1;i<=M;i++)  fac[i]=fac[i-1]*i%mod;
    infac[M]=qpow(fac[M],mod-2);
    for(int i=M;i>=1;i--) infac[i-1]=infac[i]*i%mod;
    auto C=[&](int x,int y)->ll{
        if(y>x || x<0 || y<0) return 0LL;
        return fac[x]*infac[y]%mod*infac[x-y]%mod;
    };
    int T;
    cin>>T;
    while(T--){
      int n,k;
      cin>>n>>k;
      vector<int>p(n+1);
      vector<int>pd(n+1);
      for(int i=1;i<=n;i++) cin>>p[i];
      if(k>n/2){
        cout<<0<<'\n';
        continue;
      }
      vector<Poly::poly>P;
      for(int i=1;i<=n;i++){
           if(pd[i]) continue;
           int u=i;
           int cnt=0;
           while(!pd[u]){
              pd[u]=1;
              u=p[u];
              cnt++;
           }
           Poly::poly F(cnt/2+1);
           for(int i=0;i<=cnt/2;i++) F[i]=(C(cnt-i,i)+C(cnt-i-1,i-1))%mod;
           P.push_back(F);
      }

      auto CDQ=[&](auto self,int l,int r)->Poly::poly{
        if(l==r){
            return P[l];
        }
        int mid=(l+r)>>1;
        return Poly::poly_mul(self(self,l,mid),self(self,mid+1,r));
      };
      Poly::poly res=CDQ(CDQ,0,int(P.size())-1);
      if(int(res.size())>k) cout<<res[k]<<'\n';
      else cout<<0<<'\n';
    }
}

Buy Figurines(线段树二分、优先队列、模拟)

有\(n\)个人要去排队买东西，并且有\(m\)个可以供排队的队列，按照从\(1\)到\(m\)从小到大编号。一个人有到达时间\(a_i\)和付款时间\(s_i\)，并且当他到达付款区的时候，会优先选择排队人数最少的并且编号也最小的，如果这个时间点有人离开，他会在其他人离开后再进行选择

\(1\le n,m\le 2\times 10^5\)

Problem

Solve

用优先队列维护当前所有队列的排队时间，比如当一个人进来，就把所有队列中排队时间小于当前人的到达时间的队列不断弹出。然后用线段树二分去维护人数最少的队列并且标号最小的队列

Code

#include <bits/stdc++.h>
#define ll long long
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int N=2e5+10;
struct P{
    int a,s;
    bool operator < (const P&t)const{
        return a<t.a;
    }
}p[N];
int tr[N*4],cnt[N];
ll endtime[N];
void build(int rt,int l,int r){
    if(l==r){
        tr[rt]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    tr[rt]=min(tr[ls],tr[rs]);
}
void modify(int rt,int l,int r,int x){
    if(l==x&&r==x){
        tr[rt]=cnt[l];
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(ls,l,mid,x);
    else modify(rs,mid+1,r,x);
    tr[rt]=min(tr[ls],tr[rs]);
}
int query(int rt,int L,int R,int mn){
    if(L==R) return L;
    int mid=(L+R)>>1;
    if(tr[ls]==mn) return query(ls,L,mid,mn);
    else return query(rs,mid+1,R,mn);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=m;i++) cnt[i]=endtime[i]=0;
        build(1,1,m);
        for(int i=1;i<=n;i++) cin>>p[i].a>>p[i].s;
        priority_queue<pair<ll,int>>q;
        sort(p+1,p+1+n);
        for(int i=1;i<=n;i++){
            ll a=p[i].a,s=p[i].s;
            while(q.size()>0){
                ll time=-q.top().first;
                int id=q.top().second;
                if(time<=a){
                    cnt[id]--;
                    modify(1,1,m,id);
                    q.pop();
                }
                else break;
            }
            int mn=tr[1];
            int t=query(1,1,m,mn); //选择人数最少的队列并且编号最小的
            cnt[t]++;
            modify(1,1,m,t);
            endtime[t]=max(endtime[t],a)+s;
            q.push({-endtime[t],t});
        }
        ll ans=0;
        for(int i=1;i<=m;i++) ans=max(ans,endtime[i]);
        cout<<ans<<'\n';
    }
}

这篇关于2022 HDU多校5的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！