论如何 AK WFYZ【78edu周测】-7

__vector__ · 2024-04-08 19:59:11 · 题解

contest url

本场比赛题目来源是 Codeforces Educational round#3 的 B,C,D,E,F 题

难度分别为 1100，1500，2000,2100,2500，被 lxn 出到了 OI 赛制比赛，直接复制 CF 样例。

很遗憾，本场比赛每道题都写了正解，然而因为愚蠢的错误挂了一堆分。

A

枚举每一种书，计算这种书能与其他种类的书组成多少种，最后求和。

然后注意到每一对答案算了两边，答案要除以 2。

B

设 \bar a 是 a 的平均值。
那么最后最小极差显然是 \lceil \bar a \rceil - \lfloor \bar a \rfloor 。

显然，优先用比 \lceil \bar a \rceil 大的数去补充比 \lfloor \bar a \rfloor 小的数，然后再用恰好是 \lceil \bar a \rceil 的位置去补。如果比 \lceil \bar a \rceil 大的数补完后还有剩余，那么剩下的多余总和也要进行操作。

感觉上面说的不清楚，代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
const int maxn=2e5+5;
int n;
int m[maxn];
void solve(){
    scanf("%d",&n);
    int sum=0;
    FOR(i,1,n){
        scanf("%d",&m[i]);
        sum+=m[i];
    }
    //printf("sum = %d n = %d\n",sum,n);
    int adj=sum/n;
    int mx=adj+(sum%n!=0);
    int mn=adj;
    ll tot=0;
    // 比 adj 小的，必须到达 adj
    // 由 比 adj 大的提供援助
    // 但是可能比 adj 大的存在剩余
    // 此时需要计算剩余多少，然后
    ll rest=0;
  //  printf("mx = %d\n",mx);
    FOR(i,1,n){
        if(m[i]>mx){
            rest+=m[i]-mx;
        }
    }
    FOR(i,1,n){
        if(m[i]<mn){
            tot+=mn-m[i];
            rest-=(mn-m[i]);
        }
    }
    printf("%lld\n",tot+max(0ll,rest));
}
int main(){
    solve();
    return 0;
}

C

显然随着天数增加，花费始终是不增的。

于是就有了单调性，可以二分天数。

对于一个固定的天数，我们可以知道美元/欧元付款的物品价格哪天最便宜。

然后在最便宜的那天付款就 ok 了。

// LUOGU_RID: 154894943
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
const int maxn=2e5+5;
int n,m,k,s;
ll bro3_to_us[maxn];
ll bro3_to_uk[maxn];
ll preminus[maxn],preminuk[maxn];
ll preidus[maxn],preiduk[maxn];// 前 i 个最小值位置 
struct Seller{
    int id;
    int tag;
    ll money;
    ll finalmoney;
}seller[maxn];
vector<pair<ll,ll> > chk(int day){
    FOR(i,1,m){
        if(seller[i].tag==1){
            seller[i].finalmoney=seller[i].money*preminus[day];
        }else{
            seller[i].finalmoney=seller[i].money*preminuk[day];
        }   
    }
    sort(seller+1,seller+m+1,[&](Seller& a,Seller& b){
        return a.finalmoney<b.finalmoney;
    });
    ll sum=0;
    FOR(i,1,k){
        sum+=seller[i].finalmoney;
    }
    vector<pair<ll,ll> > ans;
    if(sum>s){
        return ans;
    }else{
        FOR(i,1,k){
            int id;
            if(seller[i].tag==1)id=preidus[day];
            else id=preiduk[day];
            ans.emplace_back(make_pair(seller[i].id,id));
        }
        return ans;
    }
}
void solve(){
    scanf("%d%d%d%d",&n,&m,&k,&s);
    preminus[0]=preminuk[0]=1e18;
    FOR(i,1,n){
        scanf("%lld",&bro3_to_us[i]);
        preminus[i]=min(preminus[i-1],bro3_to_us[i]);
        if(bro3_to_us[i]<preminus[i-1]){
            preidus[i]=i;
        }else{
            preidus[i]=preidus[i-1];
        }
    //  printf("preminus[%d] = %lld\n",i,preminus[i]);
    //  printf("preidus[%d] = %lld\n",i,preidus[i]);
    }
    FOR(i,1,n){
        scanf("%lld",&bro3_to_uk[i]);
        preminuk[i]=min(preminuk[i-1],bro3_to_uk[i]);
        if(bro3_to_uk[i]<preminuk[i-1]){
            preiduk[i]=i;
        }else{
            preiduk[i]=preiduk[i-1];
        }
    }
    FOR(i,1,m){
        seller[i].id=i;
        scanf("%d%lld",&seller[i].tag,&seller[i].money);
    }
    int l=1,r=n;
    int day=-1;
    vector<pair<ll,ll> >  ans;
    while(l<=r){
        int mid=(l+r)/2;
        auto tmp=chk(mid);
        if(!tmp.empty()){
            ans=tmp;
            day=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    printf("%d\n",day);
    for(int i=0;i<ans.size();i++){
        printf("%lld %lld\n",ans[i].first,ans[i].second);
    }
}
int main(){
    solve();
    return 0;
}

D

考虑先求出 MST。
然后对于每一次固定一条边，分两种情况：

• 这条边在 MST 里面
  相当于没有固定。
• 这条边不属于 MST
  可以看成加上这条边，可以注意到原来的最小生成树出现了一个环，那么我们需要在这个环上删除权值最大的边（当然，除了加上的这条边）。
  这个东西倍增就可以做。

  
  #include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  #define FOR(i,a,b) for(int i=a;i<=b;i++)
  #define REP(i,a,b) for(int i=a;i>=b;i--)
  typedef long long ll;
  template<class T>
  void ckmx(T& a,T b){
  a=max(a,b);
  }
  template<class T>
  void ckmn(T& a,T b){
  a=min(a,b);
  }
  const int maxn=2e5+5;
  int n;
  int m;
  vector<pair<int,ll> > g[maxn];
  struct EDGE{
  int id;
  int u,to;
  ll w;
  }edge[maxn];
  int cnt;
  void add(int u,int to,ll w,int id){
  edge[++cnt].to=to;
  edge[cnt].id=id;
  edge[cnt].u=u;
  edge[cnt].w=w;
  }
  struct MS{
  int fa[maxn];
  void init(){
      FOR(i,1,n)fa[i]=i;
  }
  int get(int x){
      return (x==fa[x])?x:fa[x]=get(fa[x]);
  }
  void ms(int a,int b){
      if(get(a)!=get(b)){
          fa[get(a)]=get(b);
      }
  }
  }ms;
  int fa[21][maxn];
  int dep[maxn];
  int val[21][maxn];// 每个节点向上的边的权值就是这个点的值

// fa[i][u] 是 u 的 2^i 次向上 // val[i][u] 是 u 开始，共 2^i 条边，到达 fa[i][u] 的最大值。 void dfs(int u,int _fa,ll lstweight){ val[0][u]=lstweight; fa[0][u]=_fa; dep[u]=dep[_fa]+1; FOR(i,1,20){ fa[i][u]=fa[i-1][fa[i-1][u]]; } FOR(i,1,20){ val[i][u]=max(val[i-1][u],val[i-1][fa[i-1][u]]); } for(int i=0;i<g[u].size();i++){ int v=g[u][i].first,w=g[u][i].second; if(v!=_fa){ dfs(v,u,w); } } } int query(int a,int b){ if(dep[a]<dep[b])swap(a,b); int ans=0; REP(i,20,0){ if(dep[fa[i][a]]>=dep[b]){ ckmx(ans,val[i][a]); a=fa[i][a]; } } if(a==b)return ans; REP(i,20,0){ if(fa[i][a]!=fa[i][b]){ ckmx(ans,val[i][a]); ckmx(ans,val[i][b]); a=fa[i][a]; b=fa[i][b]; } } ckmx(ans,max(val[0][a],val[0][b])); return ans; } bool ismst[maxn]; void solve(){ scanf("%d%d",&n,&m); FOR(i,1,m){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w,i); } ms.init(); sort(edge+1,edge+m+1,[&](EDGE& a,EDGE& b){ return a.w<b.w; }); int rest=n-1; ll mstval=0; FOR(i,1,m){ if(ms.get(edge[i].u)!=ms.get(edge[i].to)){ rest--; ms.ms(edge[i].u,edge[i].to); ismst[edge[i].id]=1; mstval+=edge[i].w; int u=edge[i].u,to=edge[i].to,w=edge[i].w; g[u].emplace_back(make_pair(to,w)); g[to].emplace_back(make_pair(u,w)); if(rest==0)break; } } dfs(1,0,1e9); sort(edge+1,edge+m+1,[&](EDGE& a,EDGE& b){ return a.id<b.id; }); FOR(i,1,m){ if(ismst[i]){ printf("%lld\n",mstval); }else{ ll mx=query(edge[i].u,edge[i].to); printf("%lld\n",mstval+edge[i].w-mx); } } } int main(){ solve(); return 0; }

## E  
考虑依次模拟。   
1. 加入一个新的苍蝇，将其记录下来，我们先看看哪只青蛙会吃掉它。  
2. 如果没有青蛙能吃掉它，跳到步骤 1
3. 对于能吃掉它的青蛙，我们首先需要知道它的编号。  
4. 随后我们计算出这只青蛙本次**单次**能吃掉的苍蝇总数，以及以此获得的奖励  
5. 将这只青蛙本次单次吃掉的苍蝇算进这只青蛙最后的答案，并更新这只青蛙的捕食范围  
6. 如果这只青蛙能再吃一些新的苍蝇，跳到步骤 4。否则退出，跳到步骤 1。  

注意到本过程中，我们关心每个位置对应的青蛙，另外，青蛙会增加捕食范围。注意到每个位置会尽可能对应位置最小的青蛙，同时所有青蛙位置不同，所以我们可以用线段树记录每个位置对应的最小的青蛙**的位置**，并用 map 将每个青蛙的位置映射到对应的青蛙编号。这时候，青蛙捕食范围增加对应了区间取 min，也就是说，我们需要维护一个线段树，支持区间取 min，单点查询。    

另外，还需要计算单次捕食吃了多少苍蝇，以及对应的奖励，同时捕食结束后被吃掉的苍蝇会消失，可以得出我们需要维护另一个线段树，支持区间总苍蝇数，区间总奖励，区间删除所有苍蝇，本质对应区间修改（设置为 0），区间求和。  

```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
/*
离散化，计算每个位置被覆盖的最小编号，用 sgt1 存储 
依次枚举每只蚊子，并将其加入 sgt2 
每加入一只蚊子，就判断是否被覆盖  
如果被覆盖，那么看是哪个位置开头的青蛙将其覆盖，然后根据 sgt2 进行修改 
 
sgt1 维护单点最小值，支持区间 min 
sgt2 维护区间和，支持区间重置为 0 
 
另外维护每个位置的大小和长度 
 
 具体的，每次枚举到一个蚊子，查看覆盖它的青蛙编号  
从那个青蛙开始，查询对应影响区间在 sgt2 的区间和，记为 sum，然后这只青蛙吞食长度增加 sum， sgt1 对应修改，并再次查询区间和，以此类推 
*/
const int maxn=2e5+5;
int n,m;
struct Disc{
    ll lsh[maxn*3];
    int top;
    void add(ll x){
        lsh[++top]=x;
    }
    void init(){
        sort(lsh+1,lsh+top+1);
        top=unique(lsh+1,lsh+top+1)-lsh-1;
    }
    int pre(int x){
        // 小于等于 x 的最后一个位置 
        return upper_bound(lsh+1,lsh+top+1,x)-lsh-1; 
    }
    int suf(int x){
        return lower_bound(lsh+1,lsh+top+1,x)-lsh;// 大于等于 x 的第一个位置 
    }
}disc;
struct QWQ{
    ll pos,len;
}qwq[maxn];
struct WZ{
    ll pos,reward;
}wz[maxn];
struct SGT1{
    int L[maxn*3*4],R[maxn*3*4];
    int lazy[maxn*12];
    void build(int pos,int l,int r){
        L[pos]=l,R[pos]=r;
        lazy[pos]=1e9+7;
        if(l==r)return;
        int mid=(l+r)/2;
        build(pos<<1,l,mid);
        build(pos<<1|1,mid+1,r);
    }
    void chg(int pos,int l,int r,int _val){
        if(L[pos]>=l&&R[pos]<=r){
            ckmn(lazy[pos],_val);
            return;
        }
        if(R[pos]<l||L[pos]>r)return;
        int mid=(L[pos]+R[pos])/2;
        if(mid>=l)chg(pos<<1,l,r,_val);
        if(mid<r)chg(pos<<1|1,l,r,_val);
    }
    int query(int pos,int x,int mn){
        if(L[pos]==x&&R[pos]==x){
            return min(mn,lazy[pos]);
        }
        if(R[pos]<x||L[pos]>x)return 1e9+7;
        int mid=(L[pos]+R[pos])/2;
        int ans=1e9+7;
        if(mid>=x)ans=query(pos<<1,x,min(mn,lazy[pos]));
        if(mid<x)ckmn(ans,query(pos<<1|1,x,min(mn,lazy[pos])));
        return ans;
    } 
}sgt1;
struct SGT2{
    int L[maxn*3*4],R[maxn*3*4];
    ll val[maxn*3*4];
    bool lazy[maxn*12];
    int cnt[maxn*12];
    void build(int pos,int l,int r){
        L[pos]=l,R[pos]=r;
        if(l==r)return;
        int mid=(l+r)/2;
        build(pos<<1,l,mid);
        build(pos<<1|1,mid+1,r);
    }
    inline int len(int pos){
        return R[pos]-L[pos]+1;
    }
    void pushup(int pos){
        val[pos]=val[pos<<1]+val[pos<<1|1];
        cnt[pos]=cnt[pos<<1]+cnt[pos<<1|1];
    }
    void pushdown(int pos){
        if(lazy[pos]){
            lazy[pos]=0;
            cnt[pos<<1]=cnt[pos<<1|1]=0;
            val[pos<<1]=val[pos<<1|1]=0;
            lazy[pos<<1]=lazy[pos<<1|1]=1;
        }
    }
    void chg(int pos,int x,int _val){
        if(L[pos]==x&&R[pos]==x){
            val[pos]+=_val;
            cnt[pos]++;
            return;
        }
        if(R[pos]<x||L[pos]>x)return;
        pushdown(pos);
        int mid=(L[pos]+R[pos])/2;
        if(mid>=x)chg(pos<<1,x,_val);
        if(mid<x)chg(pos<<1|1,x,_val);
        pushup(pos);
    }
    void reset(int pos,int l,int r){
        if(L[pos]>=l&&R[pos]<=r){
            lazy[pos]=1;
            val[pos]=0;
            cnt[pos]=0;
            return;
        }
        if(R[pos]<l||L[pos]>r)return;
        pushdown(pos);
        int mid=(L[pos]+R[pos])/2;
        if(mid>=l)reset(pos<<1,l,r);
        if(mid<r)reset(pos<<1|1,l,r);
        pushup(pos);
    }
    ll query(int pos,int l,int r){
        if(L[pos]>=l&&R[pos]<=r){
            return val[pos];
        }
        if(R[pos]<l||L[pos]>r)return 0;
        pushdown(pos);
        int mid=(L[pos]+R[pos])/2;
        ll ans=0;
        if(mid>=l)ans+=query(pos<<1,l,r);
        if(mid<r)ans+=query(pos<<1|1,l,r);
        return ans;
    }
    ll count(int pos,int l,int r){
        if(L[pos]>=l&&R[pos]<=r){
            return cnt[pos];
        }
        if(R[pos]<l||L[pos]>r)return 0;
        pushdown(pos);
        int mid=(L[pos]+R[pos])/2;
        ll ans=0;
        if(mid>=l)ans+=count(pos<<1,l,r);
        if(mid<r)ans+=count(pos<<1|1,l,r);
        return ans;
    }
}sgt2;
int ans[maxn];
map<int,int> qwql_to_qwqid;// 根据 qwq 的 l，找回 qwq 的下标
void solve(){
    scanf("%d%d",&n,&m);
    FOR(i,1,n){
        scanf("%lld%lld",&qwq[i].pos,&qwq[i].len);
        disc.add(qwq[i].pos);
        disc.add(qwq[i].pos+qwq[i].len);
    }
    FOR(i,1,m){
        scanf("%lld%lld",&wz[i].pos,&wz[i].reward);
        disc.add(wz[i].pos);
    }
    disc.init();
    sgt1.build(1,1,disc.top);
    sgt2.build(1,1,disc.top);
    FOR(i,1,n){
        qwql_to_qwqid[qwq[i].pos]=i;
        sgt1.chg(1,disc.pre(qwq[i].pos),disc.pre(qwq[i].pos+qwq[i].len),qwq[i].pos);
    //  printf("i = %d : %d %d\n",i,disc.pre(qwq[i].pos),disc.pre(qwq[i].pos+qwq[i].len));
    }
    FOR(i,1,m){
        sgt2.chg(1,disc.pre(wz[i].pos),wz[i].reward);
    //  printf("wz[%d].pos.disc = %d\n",i,disc.pre(wz[i].pos));
        int id=sgt1.query(1,disc.pre(wz[i].pos),1e9+7);
    //  printf("preid = %d\n",id);
        id=qwql_to_qwqid[id];
    //    printf("i = %d disc = %d id = %d\n",i,disc.pre(wz[i].pos),id);
        if(id>=1&&id<=n){
            int l=qwq[id].pos,r=qwq[id].pos+qwq[id].len;
            // l,r 是 qwq[id] 对应的捕食区间
            ll sum=sgt2.query(1,disc.suf(l),disc.pre(r));
            ll tmp=sgt2.count(1,disc.suf(l),disc.pre(r));
        //  printf("rew = %lld\n",sum);
    //      printf("l = %d r = %d fir sum = %lld\n",disc.suf(l),disc.pre(r),sum);
            while(tmp!=0){
        //      printf("now l = %d r = %d\n",l,r);
                ans[id]+=tmp;
                sgt2.reset(1,disc.suf(l),disc.pre(r));
                qwq[id].len+=sum;
                r=qwq[id].pos+qwq[id].len;
             //   printf("new: %d %d sum = %lld upd: %d %d %lld\n",l,r,sum,disc.suf(l),disc.pre(r),qwq[i].pos);
                sum=sgt2.query(1,disc.suf(l),disc.pre(r));
                tmp=sgt2.count(1,disc.suf(l),disc.pre(r));
                sgt1.chg(1,disc.suf(l),disc.pre(r),qwq[id].pos);

            }
        }
    }
    FOR(i,1,n){
        printf("%d %lld\n",ans[i],qwq[i].len);
    }
}
int main(){
    solve();
    return 0;
}