讨论详情 - 挖土机

zby_dd 多看一眼就会爆炸 LV 9 (1600/20988) @ 2026-9-13 11:19:57

那个单 log 线段树树剖有人会写吗，帮我调一下这个题

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
int n,m,k,P[70];
vector<int>G[maxn];
int tot,dfn[maxn],rnk[maxn],L[maxn],R[maxn],top[maxn],siz[maxn],fa[maxn],dep[maxn],hson[maxn],cnt,lid[maxn],idl[maxn];
void dfs_build(int u,int F){
	siz[u]=1;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v==F)continue;
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs_build(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[hson[u]])hson[u]=v;
	}
}
void dfs(int u,int F){
	dfn[u]=++tot;
	rnk[tot]=u;
	if(hson[u]){
		top[hson[u]]=top[u];
		dfs(hson[u],u);
	}
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v==F||v==hson[u])continue;
		top[v]=v;
		dfs(v,u);
	}
}
int opt[maxn],a[maxn];
struct SGT{
	vector<int>val[65][2];
	vector<int>opt,ls,rs,mid;
}st;
vector<SGT>tr;
int trid;
void pushup(int rt){
	for(int i=0;i<k;i++){
		tr[trid].val[i][0][rt]=tr[trid].val[i][tr[trid].rs[rt]][tr[trid].val[i][0][tr[trid].ls[rt]]];
		tr[trid].val[i][1][rt]=tr[trid].val[i][tr[trid].rs[rt]][tr[trid].val[i][1][tr[trid].ls[rt]]];
	}
}
int newnode(){
	for(int i=0;i<64;i++){
		tr[trid].val[i][0].push_back(0);
		tr[trid].val[i][1].push_back(0);
	}
	tr[trid].ls.push_back(0);
	tr[trid].rs.push_back(0);
	tr[trid].mid.push_back(0);
	tr[trid].opt.push_back(0);
	return tr[trid].mid.size()-1;
}
bool calc(bool val,int op,bool xx){
	if(op==1)return (val&xx);
	if(op==2)return (val|xx);
	if(op==3)return (val^xx);
}
void buildcnt(int l,int r,int rt){
	if(l==r)return;
	int sum=0;
	for(int i=l;i<=r;i++)sum+=siz[rnk[i+dfn[lid[trid]]-1]]-siz[hson[rnk[i+dfn[lid[trid]]-1]]];
	sum/=2;
	int now=0;
	for(int i=l;i<=r;i++){
		if(now+siz[rnk[i+dfn[lid[trid]]-1]]-siz[hson[rnk[i+dfn[lid[trid]]-1]]]>=sum){
			tr[trid].mid[rt]=i;
			break;
		}
		now+=siz[rnk[i+dfn[lid[trid]]-1]]-siz[hson[rnk[i+dfn[lid[trid]]-1]]];
	}
	if(tr[trid].mid[rt]==r)tr[trid].mid[rt]--;
	tr[trid].ls[rt]=newnode();
	buildcnt(l,tr[trid].mid[rt],tr[trid].ls[rt]);
	tr[trid].rs[rt]=newnode();
	buildcnt(tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
}
void build(int l,int r,int rt){
	if(l==r){
		tr[trid].opt[rt]=opt[rnk[l+dfn[lid[trid]]-1]];
		for(int i=0;i<k;i++){
			tr[trid].val[i][0][rt]=calc(0,tr[trid].opt[i],((a[rnk[l+dfn[lid[trid]]-1]]>>i)&1));
			tr[trid].val[i][1][rt]=calc(1,tr[trid].opt[i],((a[rnk[l+dfn[lid[trid]]-1]]>>i)&1));
		}
		return;
	}
	build(l,tr[trid].mid[rt],tr[trid].ls[rt]);
	build(tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
	pushup(rt);
}
void init(int l,int r){
	tr.push_back(st);
	newnode();
	buildcnt(1,r-l+1,1);
	build(1,r-l+1,1);
}
void update(int X,int opc,int vc,int l,int r,int rt){
	if(l==r){
		tr[trid].opt[rt]=opc;
		for(int i=0;i<k;i++){
			tr[trid].val[i][0][rt]=calc(0,tr[trid].opt[i],((vc>>i)&1));
			tr[trid].val[i][1][rt]=calc(1,tr[trid].opt[i],((vc>>i)&1));
		}
		return;
	}
	if(X<=tr[trid].mid[rt])update(X,opc,vc,l,tr[trid].mid[rt],tr[trid].ls[rt]);
	else update(X,opc,vc,tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
	pushup(rt);
}
struct Val{
	bool val[65][2];
	Val(){for(int i=0;i<65;i++)val[i][0]=val[i][1]=0;}
};
Val query(int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R){
		Val res;
		for(int i=0;i<k;i++)res.val[i][0]=tr[trid].val[i][0][rt],res.val[i][1]=tr[trid].val[i][1][rt];
		return res;
	}
	if(L<=tr[trid].mid[rt]&&tr[trid].mid[rt]+1<=R){
		Val res;
		Val ls=query(L,R,l,tr[trid].mid[rt],tr[trid].ls[rt]);
		Val rs=query(L,R,tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
		for(int i=0;i<k;i++){
			res.val[i][0]=rs.val[i][ls.val[i][0]];
			res.val[i][1]=rs.val[i][ls.val[i][1]];
		}
		return res;
	}else if(L<=tr[trid].mid[rt])return query(L,R,l,tr[trid].mid[rt],tr[trid].ls[rt]);
	else return query(L,R,tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
}
Val getans(int u,int v){
	Val res;
	bool flag=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		trid=idl[top[u]];
		Val now=query(dfn[top[u]],dfn[u],1,R[trid]-L[trid]+1,1);
		if(!flag){
			res=now;
			flag=1;
		}else for(int i=0;i<k;i++)res.val[i][0]=now.val[i][res.val[i][0]],res.val[i][1]=now.val[i][res.val[i][1]];
		u=top[u];
	}
	if(dep[u]<dep[v])swap(u,v);
	trid=idl[top[u]];
	Val now=query(dfn[top[u]],dfn[u],1,R[trid]-L[trid]+1,1);
	if(!flag){
		res=now;
		flag=1;
	}else for(int i=0;i<k;i++)res.val[i][0]=now.val[i][res.val[i][0]],res.val[i][1]=now.val[i][res.val[i][1]];
	return res;
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)cin>>opt[i]>>a[i];
	P[0]=1;
	for(int i=1;i<=63;i++)P[i]=P[i-1]*2;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dep[1]=1;
	fa[1]=1;
	dfs_build(1,0);
	top[1]=1;
	dfs(1,0);
	for(int i=1;i<=n;i++){
		L[i]=n+1;
		if(!idl[top[i]]){
			idl[top[i]]=++cnt;
			lid[cnt]=top[i];
		}
	}
	for(int i=1;i<=n;i++)L[idl[top[i]]]=min(L[idl[top[i]]],dfn[i]),R[idl[top[i]]]=max(R[idl[top[i]]],dfn[i]);
	tr.push_back(st);
	for(int i=1;i<=cnt;i++){
		trid=cnt;
		init(L[lid[i]],R[lid[i]]);
	}
	while(m--){
		int OP,x,y,z;
		cin>>OP>>x>>y>>z;
		if(OP==1){
			Val res=getans(x,y);
			int now=0,ans=0;
			for(int i=k-1;i>=0;i--){
				if(res.val[i][0])ans+=P[i];
				else{
					if(res.val[i][1]){
						if(now+P[i]<=z){
							now+=P[i];
							ans+=P[i];
						}
					}
				}
			}
			cout<<ans<<'\n';
		}else{
			trid=idl[top[x]];
			update(x,y,z,1,R[trid]-L[trid]+1,1);
		}
	}
	return 0;
}

骗分大逝骗分大逝 LV 7 (1330/3230) @ 2026-9-14 21:35:38

说实话，我一年半没碰过树这个OI概念了

zby_dd 多看一眼就会爆炸 LV 9 (1600/20988) @ 2026-9-16 22:53:26

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int maxn=1e5+5;
int n,m,k;
ull P[70],a[maxn],mp;
vector<int>G[maxn];
int tot,dfn[maxn],rnk[maxn],L[maxn],R[maxn],top[maxn],siz[maxn],fa[maxn],dep[maxn],hson[maxn],cnt,lid[maxn],idl[maxn];
void dfs_build(int u,int F){
	siz[u]=1;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v==F)continue;
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs_build(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[hson[u]])hson[u]=v;
	}
}
void dfs(int u,int F){
	dfn[u]=++tot;
	rnk[tot]=u;
	if(hson[u]){
		top[hson[u]]=top[u];
		dfs(hson[u],u);
	}
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v==F||v==hson[u])continue;
		top[v]=v;
		dfs(v,u);
	}
}
int opt[maxn];
struct SGT{
	vector<ull>val[2],nval[2];
	vector<int>ls,rs,mid;
}st;
vector<SGT>tr;
int trid;
void pushup(int rt){
	tr[trid].val[0][rt]=(tr[trid].val[0][tr[trid].ls[rt]]&tr[trid].val[1][tr[trid].rs[rt]])
						+(~tr[trid].val[0][tr[trid].ls[rt]]&tr[trid].val[0][tr[trid].rs[rt]]);
	tr[trid].val[1][rt]=(tr[trid].val[1][tr[trid].ls[rt]]&tr[trid].val[1][tr[trid].rs[rt]])
						+(~tr[trid].val[1][tr[trid].ls[rt]]&tr[trid].val[0][tr[trid].rs[rt]]);
	tr[trid].nval[0][rt]=(tr[trid].nval[0][tr[trid].rs[rt]]&tr[trid].nval[1][tr[trid].ls[rt]])
						+(~tr[trid].nval[0][tr[trid].rs[rt]]&tr[trid].nval[0][tr[trid].ls[rt]]);
	tr[trid].nval[1][rt]=(tr[trid].nval[1][tr[trid].rs[rt]]&tr[trid].nval[1][tr[trid].ls[rt]])
						+(~tr[trid].nval[1][tr[trid].rs[rt]]&tr[trid].nval[0][tr[trid].ls[rt]]);
//	for(int i=0;i<k;i++){
//		tr[trid].val[0][rt]+=tr[trid].val[(tr[trid].val[0][tr[trid].ls[rt]]>>i)&1][tr[trid].rs[rt]]&P[i];
//		tr[trid].val[1][rt]+=tr[trid].val[(tr[trid].val[1][tr[trid].ls[rt]]>>i)&1][tr[trid].rs[rt]]&P[i];
//		tr[trid].nval[0][rt]+=tr[trid].nval[(tr[trid].nval[0][tr[trid].rs[rt]]>>i)&1][tr[trid].ls[rt]]&P[i];
//		tr[trid].nval[1][rt]+=tr[trid].nval[(tr[trid].nval[1][tr[trid].rs[rt]]>>i)&1][tr[trid].ls[rt]]&P[i];
//	}
}
int newnode(){
	tr[trid].val[0].push_back(0);
	tr[trid].val[1].push_back(0);
	tr[trid].nval[0].push_back(0);
	tr[trid].nval[1].push_back(0);
	tr[trid].ls.push_back(0);
	tr[trid].rs.push_back(0);
	tr[trid].mid.push_back(0);
	int t=tr[trid].mid.size();
	return t-1;
}
ull calc(ull val,int op,ull xx){
	if(op==1)return (val&xx);
	if(op==2)return (val|xx);
	if(op==3)return (val^xx);
}
void buildcnt(int l,int r,int rt){
//	cout<<l<<' '<<r<<' '<<rt<<'\n';
	if(l==r)return;
	int sum=0;
	for(int i=l;i<=r;i++)sum+=siz[rnk[i+dfn[lid[trid]]-1]]-siz[hson[rnk[i+dfn[lid[trid]]-1]]];
	sum/=2;
	int now=0;
	for(int i=l;i<=r;i++){
		if(now+siz[rnk[i+dfn[lid[trid]]-1]]-siz[hson[rnk[i+dfn[lid[trid]]-1]]]>=sum){
			tr[trid].mid[rt]=i;
			break;
		}
		now+=siz[rnk[i+dfn[lid[trid]]-1]]-siz[hson[rnk[i+dfn[lid[trid]]-1]]];
	}
	if(tr[trid].mid[rt]==r)tr[trid].mid[rt]--;
	int t=newnode();
	tr[trid].ls[rt]=t;
	buildcnt(l,tr[trid].mid[rt],tr[trid].ls[rt]);
	t=newnode();
	tr[trid].rs[rt]=t;
	buildcnt(tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
}
void build(int l,int r,int rt){
	if(l==r){
//		cout<<l<<' '<<a[rnk[l+dfn[lid[trid]]-1]]<<'\n';
		tr[trid].val[0][rt]=tr[trid].nval[0][rt]=calc(0,opt[rnk[l+dfn[lid[trid]]-1]],a[rnk[l+dfn[lid[trid]]-1]]);
		tr[trid].val[1][rt]=tr[trid].nval[1][rt]=calc(mp,opt[rnk[l+dfn[lid[trid]]-1]],a[rnk[l+dfn[lid[trid]]-1]]);
		return;
	}
	build(l,tr[trid].mid[rt],tr[trid].ls[rt]);
	build(tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
	pushup(rt);
}
void init(int l,int r){
//	cout<<l<<' '<<r<<'\n';
	tr.push_back(st);
	newnode();
	newnode();
	buildcnt(1,r-l+1,1);
	build(1,r-l+1,1);
//	cout<<1111<<'\n';
}
void update(int X,int opc,ull vc,int l,int r,int rt){
	if(l==r){
		tr[trid].val[0][rt]=tr[trid].nval[0][rt]=calc(0,opc,vc);
		tr[trid].val[1][rt]=tr[trid].nval[1][rt]=calc(mp,opc,vc);
		return;
	}
	if(X<=tr[trid].mid[rt])update(X,opc,vc,l,tr[trid].mid[rt],tr[trid].ls[rt]);
	else update(X,opc,vc,tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
	pushup(rt);
}
struct Val{
	ull val[2];
	void init(){val[0]=val[1]=0;}
};
Val query(int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R){
		Val res;
		res.val[0]=tr[trid].val[0][rt],res.val[1]=tr[trid].val[1][rt];
		return res;
	}
	if(L<=tr[trid].mid[rt]&&tr[trid].mid[rt]+1<=R){
		Val res;
		Val ls=query(L,R,l,tr[trid].mid[rt],tr[trid].ls[rt]);
		Val rs=query(L,R,tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
		res.val[0]=(ls.val[0]&rs.val[1])
				 +(~ls.val[0]&rs.val[0]);
		res.val[1]=(ls.val[1]&rs.val[1])
				 +(~ls.val[1]&rs.val[0]);
		return res;
	}else if(L<=tr[trid].mid[rt])return query(L,R,l,tr[trid].mid[rt],tr[trid].ls[rt]);
	else return query(L,R,tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
}
Val queryn(int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R){
		Val res;
		res.val[0]=tr[trid].nval[0][rt],res.val[1]=tr[trid].nval[1][rt];
		return res;
	}
	if(L<=tr[trid].mid[rt]&&tr[trid].mid[rt]+1<=R){
		Val res;
		Val rs=queryn(L,R,l,tr[trid].mid[rt],tr[trid].ls[rt]);
		Val ls=queryn(L,R,tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
		res.val[0]=(ls.val[0]&rs.val[1])
				 +(~ls.val[0]&rs.val[0]);
		res.val[1]=(ls.val[1]&rs.val[1])
				 +(~ls.val[1]&rs.val[0]);
		return res;
	}else if(L<=tr[trid].mid[rt])return queryn(L,R,l,tr[trid].mid[rt],tr[trid].ls[rt]);
	else return queryn(L,R,tr[trid].mid[rt]+1,r,tr[trid].rs[rt]);
}
vector<pair<int,int> >lu,lv;
vector<int>ru,rv;
Val getans(int u,int v){
	Val res;
	bool flag=0;
	int tu=u,tv=v;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])rv.push_back(v),lv.push_back({dfn[top[v]],dfn[v]}),v=fa[top[v]];
		else ru.push_back(u),lu.push_back({dfn[top[u]],dfn[u]}),u=fa[top[u]];
	}
	if(dep[u]>dep[v])ru.push_back(u),lu.push_back({dfn[v],dfn[u]});
	else rv.push_back(v),lv.push_back({dfn[u],dfn[v]});
	u=tu,v=tv;
	for(int i=0;i<lu.size();i++){
		trid=idl[top[ru[i]]];
//		cout<<trid<<' '<<lu[i].first-L[trid]+1<<' '<<lu[i].second-L[trid]+1<<'\n';
		Val now=queryn(lu[i].first-L[trid]+1,lu[i].second-L[trid]+1,1,R[trid]-L[trid]+1,1);
		if(!flag){
			res=now;
			flag=1;
		}else{
			res.val[0]=(res.val[0]&now.val[1])
					 +(~res.val[0]&now.val[0]);
			res.val[1]=(res.val[1]&now.val[1])
					 +(~res.val[1]&now.val[0]);
		}
//		put(res);
	}
//	cout<<1111;
	for(int i=rv.size()-1;i>=0;i--){
		trid=idl[top[rv[i]]];
//		cout<<trid<<' '<<lv[i].first<<' '<<lv[i].second<<'\n';
		Val now=query(lv[i].first-L[trid]+1,lv[i].second-L[trid]+1,1,R[trid]-L[trid]+1,1);
		if(!flag){
			res=now;
			flag=1;
		}else{
			res.val[0]=(res.val[0]&now.val[1])
					 +(~res.val[0]&now.val[0]);
			res.val[1]=(res.val[1]&now.val[1])
					 +(~res.val[1]&now.val[0]);
		}
//		put(res);
	}
	ru.clear();
	lu.clear();
	rv.clear();
	lv.clear();
	return res;
}
signed main(){
//	freopen("data.txt","r",stdin);
//	freopen("std.txt","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)cin>>opt[i]>>a[i];
	P[0]=1;
	for(int i=1;i<=63;i++)P[i]=P[i-1]*2;
	for(int i=0;i<k;i++)mp+=P[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dep[1]=1;
	fa[1]=1;
	dfs_build(1,0);
	top[1]=1;
	dfs(1,0);
	for(int i=1;i<=n;i++){
		L[i]=n+1;
		if(!idl[top[i]]){
			idl[top[i]]=++cnt;
			lid[cnt]=top[i];
		}
//		cout<<top[i]<<' ';
	}
//	cout<<'\n';
	for(int i=1;i<=n;i++)L[idl[top[i]]]=min(L[idl[top[i]]],dfn[i]),R[idl[top[i]]]=max(R[idl[top[i]]],dfn[i]);
	tr.push_back(st);
	for(int i=1;i<=cnt;i++){
		trid=i;
		init(L[i],R[i]);
//		for(int j=1;j<tr[trid].mid.size();j++){
//			cout<<j<<' '<<tr[trid].ls[j]<<' '<<tr[trid].rs[j]<<' '<<tr[trid].mid[j]<<'\n';
//			for(int K=k-1;K>=0;K--)cout<<tr[trid].val[K][0][j]<<' '<<tr[trid].val[K][1][j]<<'\n';
//			cout<<'\n';
//			for(int K=k-1;K>=0;K--)cout<<tr[trid].nval[K][0][j]<<' '<<tr[trid].nval[K][1][j]<<'\n';
//			cout<<'\n';
//		}
//		cout<<'\n';
	}
	while(m--){
		int OP,x,y;
		ull z;
		cin>>OP>>x>>y>>z;
		if(OP==1){
			Val res=getans(x,y);
//			put(res);
			ull now=0,ans=0;
			for(int i=k-1;i>=0;i--){
				if((res.val[0]>>i)&1)ans+=P[i];
				else{
					if((res.val[1]>>i)&1){
						if(now+P[i]<=z){
							now+=P[i];
							ans+=P[i];
						}
					}
				}
			}
			cout<<ans<<'\n';
		}else{
			trid=idl[top[x]];
			update(dfn[x]-L[trid]+1,y,z,1,R[trid]-L[trid]+1,1);
//			for(int i=1;i<=cnt;i++){
//				trid=i;
//				for(int j=1;j<tr[trid].mid.size();j++){
//					cout<<j<<' '<<tr[trid].ls[j]<<' '<<tr[trid].rs[j]<<' '<<tr[trid].mid[j]<<'\n';
//					for(int K=k-1;K>=0;K--)cout<<tr[trid].val[K][0][j]<<' '<<tr[trid].val[K][1][j]<<'\n';
//					cout<<'\n';
//					for(int K=k-1;K>=0;K--)cout<<tr[trid].nval[K][0][j]<<' '<<tr[trid].nval[K][1][j]<<'\n';
//					cout<<'\n';
//				}
//				cout<<'\n';
//			}
		}
	}
	return 0;
}

zby_dd 多看一眼就会爆炸 LV 9 (1600/20988) @ 2026-9-16 22:53:35

@ 我过了
骗分大逝骗分大逝 LV 7 (1330/3230) @ 2026-9-18 20:32:02

@ ~~我能抄代码吗~~

骗分大逝骗分大逝 LV 7 (1330/3230) @ 2026-9-10 22:43:03

已修改

@zby_dd 你现在是我同桌了，你作何感想

骗分大逝骗分大逝 LV 7 (1330/3230) @ 2026-9-11 23:25:21

@
zby_dd 多看一眼就会爆炸 LV 9 (1600/20988) @ 2026-9-13 11:17:49

@ 请输入文本

weixianrong LV 10 (17767/21855) @ 2026-9-1 19:53:17

xianrong补题团

15929423264 LV 6 (350/950) @ 2026-8-25 17:56:38

1

15929423264 LV 6 (350/950) @ 2026-8-25 17:01:04

k

15929423264 LV 6 (350/950) @ 2026-8-25 17:00:43

f

liujiarui LV 7 (7620/7820) @ 2026-8-23 16:21:40

已修改

TooY0ung 没硬币了,已感动

zengqianhui 破防画手 LV 8 (4653/6653) @ 2026-8-23 16:24:42
已修改
- 神了

tangjiarong LV 10 (23330/26818) @ 2026-8-23 14:21:10

已修改

P3718虬跳(92WA)。

#include<bits/stdc++.h>
using namespace std;
int n,k,ans;
char a[100005];
bool check(int mid){
	int num=1,sum=0;
	char last=a[1];
	for(int i=2;i<=n;i++){
		if(a[i]!=last){
			last=a[i],num=1;
		}
		else{
			num++;
			if(num>mid){
				num=1;
				if(last=='F')	last='N';
				else	last='F';
				sum++;
			}
		}
	}
	if(sum<=k)	return 1;
	else	return 0;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)	cin>>a[i];
	int l=1,r=n;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}
		else	l=mid+1;
	}
	cout<<ans;
}

tangjiarong LV 10 (23330/26818) @ 2026-8-22 20:20:40

已修改

细节，注意看输出格式的第二行写的模数

十年OI一场空，不看模数见祖宗。

xukeran twe too Y0ung LV 7 (15394/17094) @ 2026-9-12 0:52:50

33DAI还是太细节了，放csp能被他阴死80%（20%记不住998244353）

15929423264 LV 6 (350/950) @ 2026-8-21 16:33:20

c

xukeran twe too Y0ung LV 7 (15394/17094) @ 2026-8-18 15:33:26

已修改

这是啥啊

huzhexuan LV 7 (700/700) @ 2026-8-18 18:43:45

正常
zengqianhui 破防画手 LV 8 (4653/6653) @ 2026-8-18 20:30:18

正常。（笑）
zengqianhui 破防画手 LV 8 (4653/6653) @ 2026-8-18 20:33:20

（😍）

zengqianhui 破防画手 LV 8 (4653/6653) @ 2026-8-17 16:47:54

已修改

217083,TooY0ung洛谷号。（笑）

zhangjiarui 菜就多练 LV 9 (4303/5803) @ 2026-8-17 14:33:47

诈尸

tangjiarong LV 10 (23330/26818) @ 2026-8-16 13:58:52

第一次...

huzhexuan LV 7 (700/700) @ 2026-8-14 13:58:01

P1019 67分求调

#include <bits/stdc++.h>
using namespace std;
int n;
string word[25];
int used[25];
int ans=0;
char startch;
int op(string A,string B) 
{
    int la=A.size(),lb =B.size();
    int maxk = 0;
    for (int k=1;k<min(la,lb);k++)
    {
        bool match=true;
        for (int i=0;i<k;i++) 
        {
            if(A[la-k+i]!=B[i]) 
            {
                match=false;
                break;
            }
        }
        if(match)maxk=k; 
    }
    return maxk;
}
void dfs(int last,int len)
{
    ans=max(ans,len);
    for(int i=1;i<=n;i++)
    {
        if(used[i]>=2)continue;
        int k=op(word[last],word[i]);
        if(k==0)continue;
        used[i]++;
        dfs(i,len+word[i].size()-k);
        used[i]--;
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>word[i];
    }
    cin>>startch;
    for(int i=1;i<=n;i++)
    {
        if(word[i][0]==startch)
        {
            used[i]++;
            dfs(i,word[i].size());
            used[i]--;
        }
    }
    cout<<ans<<endl;
    return 0;
}

欧阳宁佑西安地铁6号线，蓝紫让你辨一辨，请更换深浅再看一次 LV 10 (15932/18232) @ 2026-8-14 17:57:39

已修改

因为你的op函数从小到大，所以你的返回值会是最大的公共段，但是如果出现小的公共段，肯定更优（重复的较少），所以找到第一个match的，就break掉。

#include <bits/stdc++.h>
using namespace std;
int n;
string word[25];
int used[25];
int ans=0;
char startch;
int op(string A,string B) 
{
	int la=A.size(),lb =B.size();
	int maxk = 0;
	for (int k=1;k<min(la,lb);k++)
	{
		bool match=true;
		for (int i=0;i<k;i++) 
		{
			if(A[la-k+i]!=B[i]) 
			{
				match=false;
				break;
			}
		}
		if(match){maxk=k; break;}
	}
	return maxk;
}
void dfs(int last,int len)
{
	ans=max(ans,len);
	for(int i=1;i<=n;i++)
	{
		if(used[i]>=2)continue;
		int k=op(word[last],word[i]);
		if(k==0)continue;
		used[i]++;
		dfs(i,len+word[i].size()-k);
		used[i]--;
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>word[i];
	}
	cin>>startch;
	for(int i=1;i<=n;i++)
	{
		if(word[i][0]==startch)
		{
			used[i]++;
			dfs(i,word[i].size());
			used[i]--;
		}
	}
	cout<<ans<<endl;
	return 0;
}

huzhexuan LV 7 (700/700) @ 2026-8-14 18:34:07

@ 谢谢

luojinfan LV 6 (7482/7932) @ 2026-8-9 21:58:31

谢谢

luojinfan LV 6 (7482/7932) @ 2026-8-9 21:57:30

发代码如何有格式而不是一坨
力求！！！！！！好人一生平安

刘泽釴 LV 8 (18201/20301) @ 2026-8-9 22:15:40

前面加“```cpp”
周净知 LV 8 (5590/5590) @ 2026-8-10 20:34:30

@ 你竟然盗我头像!!!
刘泽釴 LV 8 (18201/20301) @ 2026-8-11 8:57:13

有入把窝的头像盗了喵
周净知 LV 8 (5590/5590) @ 2026-8-11 21:51:37

@ 啊?!

18109163562 LV 5 (2286/3816) @ 2026-8-9 18:59:29

tangjiarong LV 10 (23330/26818) @ 2026-8-6 13:31:09

zhangruichen 和平小辣条 LV 6 (10154/15654) @ 2026-8-6 8:33:07

为什么不给我发硬币和徽章

高子煜 LV 7 (6870/7870) @ 2026-8-4 15:53:19

不会写高精度如何骗更多分

double的范围是可以到正负pow(10,308)

huzhexuan LV 7 (700/700) @ 2026-8-4 15:54:55

111111111111111111
huzhexuan LV 7 (700/700) @ 2026-8-4 15:55:10

1
weixianrong LV 10 (17767/21855) @ 2026-8-5 15:15:49

@

不会就别乱说，真像你那样的话学高精度有什么用？

double的范围是可以到pow(10,308)，但精度只有pow(10,16），后面的位数会丢失
高子煜 LV 7 (6870/7870) @ 2026-8-6 8:12:37

@ 好感谢指正

李思辰 LV 6 (4900/4950) @ 2026-8-4 10:12:07

1

15929423264 LV 6 (350/950) @ 2026-8-4 10:11:30

1

高子煜 LV 7 (6870/7870) @ 2026-8-3 21:08:40

这代码会超时你敢信 n最大pow(10,5);

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n,w;
int score[100005];
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    cin>>n>>w;
    for(int i=1;i<=n;i++)
    {
        cin>>score[i];
        if(score[i]>score[i-1]) sort(score+1,score+1+i,cmp);
        int plan=max(1,i*w/100);
        cout<<score[plan]<<" ";
    }
    return 0;
}

xukeran twe too Y0ung LV 7 (15394/17094) @ 2026-9-12 0:56:50

以后可以直接打 $10^5$ 不必那么麻烦pow（10,5）之类的

高子煜 LV 7 (6870/7870) @ 2026-8-3 15:46:23

P5661公交换乘洛谷45挖土机55 洛谷样例全对，错误测试点均TLE求调

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n;
ll sum;
int way,price,tim;
int cnt;//统计优惠票数量
struct youhui
{
    int time;
    int money;
}yh[100005];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>way>>price>>tim;
        if(way==0)//地铁
        {
            cnt++;
            yh[cnt].time=tim;
            yh[cnt].money=price;
            sum+=price;
        }
        else//公交
        {
            if(cnt>0)
            {
                int flag=0;
                for(int i=1;i<=cnt;i++)
                {
                    if(yh[i].time==-1) continue;
                    if(tim-yh[i].time<=45&&yh[i].money>=price)
                    {
                        flag=1;
                        yh[i].time=-1;
                        break;
                    }
                }
                if(flag==0) sum+=price;
            }
            else sum+=price;
        }
    }
    cout<<sum;
    return 0;
}

huzhexuan LV 7 (700/700) @ 2026-8-3 15:46:50

using namespace std;
struct shi_jian
{
    int money,time;
}arr[100005];
int used[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,head=1;
    cin>>n;
    int xia_biao=1,sum=0;
    while(n--)
    {
        int num,piece,t;
        cin>>num>>piece>>t;
        if(num==0)
        {
            sum+=piece;
            arr[xia_biao].money=piece;
            arr[xia_biao].time=t;
            xia_biao++;
        }
        else
        {
            while(head <= xia_biao && t - arr[head].time > 45) {
                head++;
            }
            int cnt=0;
            for(int i=head;i<=xia_biao;i++)
            {
                if(arr[i].money>=piece&&t-arr[i].time<=45&&used[i]==0)
                {
                    used[i]=1;
                    cnt++;
                    break;
                }
            }
            if(cnt==0)sum+=piece;
        }
    }
    cout<<sum;
}

高子煜 LV 7 (6870/7870) @ 2026-8-3 15:51:06

@ 不要把自己的代码发给我
xukeran twe too Y0ung LV 7 (15394/17094) @ 2026-8-3 16:55:22

@ 要说错哪了
huzhexuan LV 7 (700/700) @ 2026-8-12 15:00:38

@ 你是不是@错人了
xukeran twe too Y0ung LV 7 (15394/17094) @ 2026-8-18 15:35:46

@ 是

xukeran twe too Y0ung LV 7 (15394/17094) @ 2026-9-12 1:21:38

已修改

我大概看了下你的代码

1.核心错误：变量名冲突

  for(int i=1;i<=n;i++) {// 外层 i
      ...
      for(int i=1;i<=cnt;i++) {// 内层 i，冲突！

内层 i 会覆盖外层 i，导致外层循环错乱。

2.其次优惠票使用策略错误—应该优先使用最早过期的，而不是随便找一个

3.不太重要的小毛病

  yh[i].time=-1

标记已用,可以，但数组不会清理，越往后越慢

改正代码（45TLE未优化）：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n;
ll sum;
int way,price,tim;
int cnt;
struct youhui {
    int time;
    int money;
} yh[100005];

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>way>>price>>tim;
        if(way==0) {  // 地铁
            cnt++;
            yh[cnt].time=tim;
            yh[cnt].money=price;
            sum+=price;
        } else {  // 公交
            int flag=0;
            // 找最早过期的可用优惠票（FIFO）
            for(int j=1;j<=cnt;j++) {
                if(yh[j].time==-1) continue;
                if(tim-yh[j].time<=45 && yh[j].money>=price) {
                    flag=1;
                    yh[j].time=-1;
                    break;
                }
            }
            if(!flag) sum+=price;
        }
    }
    cout<<sum;
    return 0;
}

但是该代码任会超时注意到对于100%的数据， n≤ $10^5$ , $t_i$ ≤ $10^9$ 1≤ $price_i$ ≤1000

n≤ $10^5$ 会TLE

优化：用队列按时间维护票，每次坐公交：弹出过期票（时间差>45）在剩余票中找票价≥公交票价的如果有，用掉一张（标记或删除）

优化代码：（会RE，没时间了，以后会修改）

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    ll sum = 0;
    // 队列按时间存票，multiset按票价存可用票
    queue<pair<int,int>> q;  // {时间, 票价}
    multiset<int> s;  // 可用票的票价
    
    for (int i = 1; i <= n; i++) {
        int way, price, tim;
        cin >> way >> price >> tim;
        
        if (way == 0) {  // 地铁
            sum += price;
            q.push({tim, price});
            s.insert(price);
        } else {  // 公交
            // 弹出过期票
            while (!q.empty() && tim - q.front().first > 45) {
                s.erase(s.find(q.front().second));
                q.pop();
            }
            // 找票价≥公交票价的票
            auto it = s.lower_bound(price);
            if (it != s.end()) {
                // 用掉这张票
                s.erase(it);
                // 从队列中删除对应票（需要知道是哪个，但队列不方便删中间）
                // 问题：multiset删了，队列里还有，但后面会过期自动弹出
                // 但队列里的票和multiset不同步！
            } else {
                sum += price;
            }
        }
    }
    
    cout << sum;
    return 0;
}

创作不易，不喜勿喷

xukeran twe too Y0ung LV 7 (15394/17094) @ 2026-8-3 14:50:03

-3148？！

贾小目 LV 6 (11813/11833) @ 2026-8-3 14:40:22

wanjiaming LV 6 (6291/6291) @ 2026-8-3 14:39:01

1.千问 2.元宝

xukeran twe too Y0ung LV 7 (15394/17094) @ 2026-8-3 14:41:49

高德地图头上绿绿的

海上生明月 LV 6 (7600/8600) @ 2026-8-3 14:35:39

贾小目 LV 6 (11813/11833) @ 2026-8-3 14:35:25

wanjiaming LV 6 (6291/6291) @ 2026-8-3 14:30:41

weixianrong LV 10 (17767/21855) @ 2026-8-3 11:34:44

tangjiarong LV 10 (23330/26818) @ 2026-8-3 11:30:01

haoyichen LV 6 (16098/16498) @ 2026-8-3 11:31:16

看懂的人已经笑了

haoyichen LV 6 (16098/16498) @ 2026-8-3 11:22:17

这人有病吧

wanjiaming LV 6 (6291/6291) @ 2026-8-3 14:28:07
haoyichen LV 6 (16098/16498) @ 2026-8-3 14:35:12

不是，你怎魔能盗我的头像

胡宇泽一路生花 LV 8 (24478/29866) @ 2026-8-3 11:18:05

…………………………

weixianrong LV 10 (17767/21855) @ 2026-8-3 9:55:50

GAY吧

胡宇泽一路生花 LV 8 (24478/29866) @ 2026-8-3 9:55:28

这又给我干哪来了

xukeran twe too Y0ung LV 7 (15394/17094) @ 2026-8-3 9:52:49

xukeran twe too Y0ung LV 7 (15394/17094) @ 2026-8-3 9:52:59

？？？

胡宇泽一路生花 LV 8 (24478/29866) @ 2026-8-3 9:52:02

看来我真的穿越了

胡宇泽一路生花 LV 8 (24478/29866) @ 2026-8-3 9:47:49

我穿越了吗

weixianrong LV 10 (17767/21855) @ 2026-8-3 9:47:41

这人-ay吧

15929423264 LV 6 (350/950) @ 2026-8-3 8:59:00

423r35

haoyichen LV 6 (16098/16498) @ 2026-8-2 17:48:21

?????

wanjiaming LV 6 (6291/6291) @ 2026-8-2 17:50:58

???

贾小目 LV 6 (11813/11833) @ 2026-8-2 17:44:01

观后感 be like 后两个字

weixianrong LV 10 (17767/21855) @ 2026-8-2 16:29:03

fengyubo LV 10 (-2747/21053) @ 2026-8-2 16:25:58

何意味

？？？

fengyubo LV 10 (-2747/21053) @ 2026-8-2 16:28:29
haoyichen LV 6 (16098/16498) @ 2026-8-2 16:31:36

???
刘泽釴 LV 8 (18201/20301) @ 2026-8-2 17:51:22

常数是怎么赋为1的，这么说每一个式子都能推出

haoyichen LV 6 (16098/16498) @ 2026-8-2 15:21:56

？？，何意味

weixianrong LV 10 (17767/21855) @ 2026-8-2 15:19:00

weixianrong LV 10 (17767/21855) @ 2026-8-2 15:19:13

这人gay吧

fengyubo LV 10 (-2747/21053) @ 2026-8-2 15:17:26

周净知 LV 8 (5590/5590) @ 2026-8-2 15:14:47

从百草园训到三味书屋

作者 akakal 发布时间 2025-11-19 10:55 分类休闲·娱乐我家的后面有一个很大的机房，。现在是早已并屋子一起卖给学校的教练了，连那最末次的相见也已经隔了几年，其中似乎确凿只有一些电脑和桌凳；但那时却是我的乐园。

不必说绿色的 AC，红色的 WA，深色的 MLE TLE，黄色的 CE；也不必说 LCA 拎着俩节点在树上乱跑，验题人拿着鞭子追着出题人，一个 Au✌️突然疯疯癫癫地向外省跑去了。单是周围的一车算法书，就有无限趣味。

学长曾经讲给我一个故事听：先前，有一个 OIer 住在机房里加训，晚间，在看算法学习的时候，突然听到有人在叫他打游戏。答应着，四面看时，却见同学都在敲代码，向他一笑，关掉 dev-c++ 和 Edge 了。他很高兴地准备打游戏；但竟给那走来找他讲算法的学长识破了机关。说他同学有问题，一定遇见 faker 了；这是天天说 p 话和装不努力的同学，教你打游戏，倘一答应，晚些正赛的时候你就被他们拉的十万八千里远！他自然吓得要死，而那学长却道无妨，给他一个做题热度统计图，说只要挂主页，便可安心打游戏。他虽然照样办，却总是玩不进去，——当然玩不进去。到第二天，果然出猫腻了！翻开那主页，绿的蓝的紫的黑的；深的浅的不深不浅的，那同学们做了好多题！打开模拟赛成绩一看，rank1 还在哭嚎说自己打的依托，真乃过分！

结末的教训是：所以同学叫你的去打游戏，你万万不可答应他。

这故事很使我觉得做人之险，打游戏时，往往有些担心。打模拟赛时，也常常这样想。但直到现在，总还没有遇见过。叫我打游戏的声音自然是常有的，然而都不是在机房训练的时候罢。

我不知道为什么家里的人要将我送进集训里去了，而且还是全城中称为最强的集训。也许是因为周末喜欢窝床上打游戏罢，也许是因为写树剖重儿子的重儿子是自己罢，也许是因为写完正解然后 MLE 罢……都无从知道。总而言之：我将不能常到机房了。

……

不知从哪里听来的，教练也很渊博，他认识一种算法，名曰“树上背包套线段树套重链剖分套基环树套平衡树套红黑树拌水泥钢筋混凝土套树状数组套后缀自动机套拌最好吃的意大利面”，我很想详细地知道这故事，但 OI-wiki 是不知道的，因为它很多都模糊不清。现在得到机会了，可以问先生。

“先生，‘树上背包套线段树套重链剖分套基环树套平衡树套红黑树拌水泥钢筋混凝土套树状数组套后缀自动机凉咔久久套拌最好吃的意大利面’这算法，是怎么一回事？”我交完代码，将要退下来的时候，赶忙问。

“不知道！”他似乎很不高兴，脸上还有怒色了。

我才知道做学生是不应该问这些事的，只要加训，因为他是渊博的顶级教练，决不至于不知道，所谓不知道者，乃是不愿意说。比我牛的人，往往如此，我遇见过好几回了。

我就只加训，上午打模拟赛，正午补题，晚上练算法。教练最初这几天对我很严厉，后来却好起来了，不过给我训的题越来越多，难度也渐渐地加上字去，从绿题到蓝题，终于到黑题了。

电脑里面有个网页唤做 OI 教练模拟器，虽然简洁，但也十分好玩。然而同学们玩的太多，太久，

“人都在看什么呢！”

便一个个赶忙关掉电脑；一同打开 www.luogu.com.cn 和题目，也不行的。他有一个极域软件，但是不常用，也有看浏览记录的规则。但也懒得全罚，便瞪几眼，大声道：

“加训！”

十一月十九日。

LGL0819 神に挑戦すること自体が... 陰謀を企てていない... LV 9 (4250/12450) @ 2026-8-2 20:57:53

呦吼你竟然还在挖土机上课📖
fengyubo LV 10 (-2747/21053) @ 2026-8-6 22:05:09

666

还仿写鲁某人的《某花夕拾》

【FAQ】问答&讨论贴

559 条评论

神了

P1019 67分求调

不会写高精度如何骗更多分

double的范围是可以到正负pow(10,308)

从百草园训到三味书屋

【FAQ】问答&讨论贴

559 条评论

神了

P1019 67分求调

不会写高精度如何骗更多分

double的范围是可以到正负pow(10,308)

从百草园训到三味书屋

还没有账户？

登录