Logo __vector__ 的博客

博客

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

...
__vector__
2025-12-01 12:56:00

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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），区间求和。

#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;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

中文 English

鲁ICP备2025150228号

Server Time: 2026-03-15 06:17:07 | OpenSource Project