挑战赛#20全题解（不是占位）

userId_undefined

AAA水泥批發白哥

出道萌新尊贵铂金时空双修者I/O·IO入门者

2025-07-13 22:01:13

发布于：北京

253阅读
0回复
0点赞

T4只吃了一发罚时（喜）
T1两罚、T3一发（怒）
T6一发（悲）

T1

思路

因为 10x=2x5x10^x=2^x5^x，且 22 与 55 互质，故有 10x10^x 有 xx 个 22 因子，然后把开头再分解一下就行。

代码

string s;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
	n=s[0]-'0';
	while(n%2==0)
	{
		cnt++;
		n/=2;
	}
	cout<<cnt+s.size()-1;
	return 0;
}

T2

思路

直接暴力即可，时间复杂度等于 DFS 的复杂度，为 O(n+m)O(n+m)。

代码

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<n;i++)
	{
		cin>>u>>v;
		E[u].push_back(v);
		E[v].push_back(u);
	}
	for(i=1;i<=n;i++)
	{
		bool f=1;
		for(auto& it:E[i])
		{
			if(a[it]==a[i])
			{
				f=0;
				break;
			}
		}
		cnt+=f;
	}
	cout<<cnt;
	return 0;
}

T3

思路

01 背包 模板题，不必多说。

代码

signed main()
{
	cin>>n>>W;
	for(i=1;i<=n;i++)cin>>w[i]>>v[i];
	for(i=1;i<=n;i++)
    {
    	for(j=W;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+v[i]);
	}
	cout<<f[W];
	return 0;
}

T4

思路

明显的，我们要尽可能地把 11 块合并到另一个 11 块里。那么在 0⋯1⋯0\cdots1\cdots 这样的反转后，就变成了 1⋯0⋯1\cdots0\cdots，刚好能在左边连上 11 块。

注意，合并有两种情况：合并到最左边（度小 11），合并到第一个（不是最左边的）11 块。求最小即可。

代码

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	for(i=1;i<n;i++)
	{
		if(s[i]!=s[i-1])
		{
			v.push_back({{l,i-1},s[i-1]});
			if(s[i-1]=='1')
			{
				cnt++;
			}
			l=i;
		}
	}
	if(v.empty())v.push_back({{0,n-1},s[n-1]});
	if((*v.rbegin()).first.second!=n-1)
	{  
		v.push_back({{(*v.rbegin()).first.second+1,n-1},s[n-1]});
		if(s[n-1]==d)cnt++;
	}
	if(v.size()==1)
	{
		cout<<0;
		return 0;
	}
	for(i=1;i<v.size();i++)
	{
		if(v[i].second=='0')continue;
		use++;
		vis[i]=1;
		if(use==m)break;
	}
	for(i=1;i<v.size();i++)
	{
		if(v[i].second=='0')continue;
		if(vis[i]==0)
		{
			d+=2;
			if(i==v.size()-1)d--;
		}
	}
	ans=d+1;//111···000···1···1···，统计的时候没统计第一个快，所以得加一
	use=d=0;
	memset(vis,0,sizeof(vis));
	int f1=v.size();
	for(i=1;i<v.size();i++)
	{
		if(v[i].second=='1')
		{
			f1=i;
			break;
		}
	}
	for(i=f1+1;i<v.size();i++)
	{
		if(v[i].second=='0')continue;
		use++;
		vis[i]=1;
		if(use==m)break;
	}
	for(i=0;i<v.size();i++)
	{
		if(v[i].second=='0')continue;
		if(vis[i]==0)
		{
			d+=2;
			if(i==v.size()-1||i==0)d--;
		} 
	}
	ans=min(ans,d);
	cout<<ans;
	return 0;
}

T5

思路

将入场和退场时间排序，亦个处理。

使用 multiset 维护能力值，如果有人入场，那么检查它是否大于等于最小能力的人（贪心选择），如果这都不行就能力值 00，否则计算。将能力放入 multiset 中。退场就从 multiset 中移除对应人的能力值。最后输出就行。

代码

multiset<int> ms;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>w[i]>>s[i]>>t[i];
		p[++tot]={{s[i]*10,0},i};//*10不用double
		p[++tot]={{t[i]*10+1,1},i};//*10不用double
	}
	sort(p+1,p+tot+1);
	for(i=1;i<=tot;i++)
	{
		int tp=p[i].first.second,id=p[i].second;
		if(tp==1)
		{
			auto it=ms.find(w[id]);
			if(it!=ms.end())ms.erase(it);
		}
		else
		{
			if(!ms.empty())
			{
				if((*ms.begin())<=w[id])ans[id]=w[id]-(*ms.begin());
			}
			ms.insert(w[id]);
		}
	}
	for(i=1;i<=n;i++)cout<<ans[i]<<" ";
	return 0;
}

T6

@AAA混泥土批发ppl哥fvv

思路

考虑序列之王 FHQ-Treap（对，不是 Splay 因为我不会），排名分裂和懒标记平衡树的练习。

操作 22 只要把前 n−xn-x 个裂成 LL，剩下后 xx 就是 RR，合并 RR 和 LL 就行。

操作 11 给每个节点加个懒标记（偏移），分裂合并的时候 pushdown（下发） 和 pushup（更新大小） 就行。

代码

struct Node
{
	int ls,rs,pri,sz,off;
	char val;
}t[2000005];
int build(char x)
{
	t[++cnt].sz=1;
	t[cnt].ls=t[cnt].rs=t[cnt].off=0;
	t[cnt].val=x;
	t[cnt].pri=rand()*rand();
	return cnt;
}
void update(int u)//pushup
{
	t[u].sz=t[t[u].ls].sz+t[t[u].rs].sz+1;
}
void pushdown(int u)
{
	if(!u)return;
	if(t[u].off)
	{
		if(t[u].ls)t[t[u].ls].off=(t[u].off+t[t[u].ls].off)%26;
		if(t[u].rs)t[t[u].rs].off=(t[u].off+t[t[u].rs].off)%26;
		int add=(t[u].off+26)%26;
		char newc='a'+(t[u].val-'a'+add)%26;
		if(newc>'z')newc-=26;
		else if(newc<'a')newc+=26;
		t[u].val=newc;
		t[u].off=0;
	}
}
void split(int u,int x,int& L,int& R)
{
	if(!u)
	{
		L=R=0;
		return ;
	}
	pushdown(u);
	if(t[t[u].ls].sz+1<=x)
	{
		L=u;
		split(t[u].rs,x-t[t[u].ls].sz-1,t[u].rs,R);
	}
	else
	{
		R=u;
		split(t[u].ls,x,L,t[u].ls);
	}
	update(u);
}
int merge(int L,int R)
{
	if(L==0||R==0)return L+R;
	if(t[L].pri>t[R].pri)
	{
		pushdown(L);
		t[L].rs=merge(t[L].rs,R);
		update(L);
		return L;
	}
	pushdown(R);
	t[R].ls=merge(L,t[R].ls);
	update(R);
	return R;
}
void output(int u)
{
	if(!u)return ;
	pushdown(u);
	output(t[u].ls);
	cout<<t[u].val;
	output(t[u].rs); 
}
string s;
signed main()
{
	srand(time(NULL));
	cin>>n>>s>>q;
	for(i=0;i<n;i++)root=merge(root,build(s[i]));
	while(q--)
	{
		cin>>op;
		if(op==1)
		{
			cin>>l>>r>>x;
			split(root,l-1,L,R);
			split(R,r-l+1,p,R);
			if(p)
			{
				t[p].off=(t[p].off+(x%26))%26;
				if(t[p].off<0)t[p].off+=26;
			}
			root=merge(merge(L,p),R);
		}
		else
		{
			cin>>x;
			x%=n;
			if(x==0)continue;
			split(root,n-x,L,R);
			root=merge(R,L);
		}
	}
	output(root);
	return 0;
}

彩蛋


最终：

userId_undefined
去预览
0/2000

全部评论 16

热门讨论