ABC235题解

2023-10-17 16:58:22

ABC235 A - Rotate

给你一个三位数 $ abc $，求 $ abc+bca+cab $。

分析：

\[abc+bca+cab \]

\[=(100a+10b+c)+(100b+10c+a)+(100c+10a+b) \]

\[=111a+111b+111c \]

\[=111(a+b+c) \]

输出即可。

时间复杂度 $ O(1) $。

代码：

#include<cstdio>
using namespace std;
int a,b,c;
int main()
{
  	a=getchar()-'0',b=getchar()-'0',c=getchar()-'0';
  	printf("%d\n",111*(a+b+c));
	return 0;
}

ABC235 B - Climbing Takahashi

现在有 $ N $ 个平台从左到右排成一行，第 $ i $ 个平台高度为 $ H_i $。有一个人现在站在第一个平台上，他将要重复执行以下动作。

如果现在他所在的平台不是最右边的平台，且下一个平台比自己所在的这个平台高，那么他将走到下一个平台。

问他最后停留在的平台的高度。

$ 2\le N\le10^5 $

$ 1\le H_i\le10^9 $

分析：直接模拟即可。

时间复杂度 $ O(n) $。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int a[100001];
int n;
int main()
{
	cin>>n>>a[1];
	for(int i=2;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]<=a[i-1]){ cout<<a[i-1];return 0;}
	}
	cout<<a[n];
	return 0;
}

ABC235 C - The Kth Time Query

给定一个长度为 $ N $ 的序列 $ a $。

现在有 $ Q $ 次询问，第 $ i $ 次询问给定 $ x_i $ 和 $ k_i $，输出 $ x_i $ 这个数字第 $ k_i $ 次在 $ a $ 出现时的下标。没有出现过 $ k_i $ 次输出 $ -1 $。

$ 1\le N,Q\le 2\times10^5 $

$ 1\le k_i\le N(1\le i\le Q) $

$ 0\le x_i\le 10^9(1\le i\le Q) $

$ 0\le a_i\le 10^9(1\le i\le N) $

对 $ a $ 与 $ x $ 一起进行离散化，然后从左到右对于每一个位置 $ i $，将 $ i $ 加入一个 $ a_i $ 对应的 vector 中。查询直接进行回答即可。

时间复杂度 $ O((n+q)\log (n+q)) $

代码：

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
vector<int>g[400001];
int num[400001];
int a[200001];
int x[200001];
int k[200001];
int n,q;
int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i],num[i]=a[i];
	for(int i=1;i<=q;i++) cin>>x[i]>>k[i],num[i+n]=x[i];
	sort(num+1,num+n+q+1);int len=unique(num+1,num+n+q+1)-num-1;
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(num+1,num+len+1,a[i])-num;
		g[a[i]].push_back(i);
	}
	for(int i=1;i<=q;i++)
	{
		x[i]=lower_bound(num+1,num+len+1,x[i])-num;
		if((int)g[x[i]].size()<k[i]){ cout<<-1<<endl;continue;}
		cout<<g[x[i]][k[i]-1]<<endl;
	}
	return 0;
}

ABC235 D - Multiply and Rotate

给定一个数字 $ a $ 与 $ N $，现有一个初始为 $ 1 $ 的数字 $ x $，你可以对 $ x $ 执行以下操作无数次：

  1. 令 $ x\gets x\times a $；

  2. 当 $ x\ge 10 $ 且 $ x\nmid10 $ 时，设 $ y $ 为将 $ x $ 的末位提到最前面所得的数字，令 $ x\gets y $。

求 $ x=N $ 时，操作最小次数。如果无法令 $ x=N $，输出 $ -1 $。

$ 2\le a,N<10^6 $

分析：从数字 $ 1 $ 出发，直接进行 bfs 即可。

时间复杂度 $ O(10^6) $

代码：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
using ll=long long;
bool vis[1000001];
int dis[1000001];
int a,n;
int yi(int num)
{
	for(int i=0,j=1;;i++,j*=10)
	{
		if(j<=num&&num<10*j)
			return j*(num%10)+num/10;
	}
}
int main()
{
	cin>>a>>n;
	queue<int>que;que.push(1);
	while(!que.empty()&&!vis[n])
	{
		int p=que.front();
		que.pop();
		if((ll)p*a<=1000000&&!vis[p*a])
		{
			dis[p*a]=dis[p]+1;
			vis[p*a]=1;
			que.push(p*a);
		}
		if(p>10&&p%10)
		{
			int q=yi(p);
			if(!vis[q])
			{
				vis[q]=1;
				dis[q]=dis[p]+1;
				que.push(q);
			}
		}
	}
	if(vis[n]) cout<<dis[n];
	else cout<<-1;
	return 0;
}

ABC235 E - MST + 1

给定一个有 $ N $ 个顶点 $ M $ 条边的无向联通图，以及 $ Q $ 个询问。

每个询问 $ i $ 给定 $ u_i,v_i,w_i $ 询问，假如有一条连接顶点 $ u_i $ 与 $ v_i $ 且边权为 $ w_i $ 的边，他会不会在新图的最小生成树中。

$ 1\le N,M,Q\le 2\times 10^5 $

保证 $ w_i $ 不和原图中任何一条边的边权相等。

分析：首先对于输入的所有边进行排序，然后跑双指针即可。

双指针过程中假如原图中边的边权更小，则将这条边加入最小生成树中，如果询问的边权更小，通过并查集判断连通性回答询问。

最后按照顺序输出询问的答案即可。

时间复杂度 $ O(M\log M+Q\log Q) $。

代码：

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
struct edge
{
	int u,v,w;
	bool ans;
	int i;
}qu[200001],a[200001];
bool qans[200001];
int fa[200001];
int n,m,q;
int find(int num){
	if(fa[num]==num) return num;
	return fa[num]=find(fa[num]);
}
signed main()
{
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++) cin>>a[i].u>>a[i].v>>a[i].w;
	for(int i=1;i<=q;i++) cin>>qu[i].u>>qu[i].v>>qu[i].w,qu[i].i=i;
	sort(a+1,a+m+1,[](edge a,edge b){ return a.w<b.w;});
	sort(qu+1,qu+q+1,[](edge a,edge b){ return a.w<b.w;});
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1,j=1;i<=m&&j<=q;)
	{
		if(a[i].w<qu[j].w)
		{
			if(find(a[i].u)==find(a[i].v)){ i++;continue;}
			fa[find(a[i].u)]=find(a[i].v);
		}
		else
		{
			if(find(qu[j].u)!=find(qu[j].v)){ qans[qu[j].i]=1;}
			j++;
		}
	}
	for(int i=1;i<=q;i++)
		if(qans[i]) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

ABC235 F - Variety of Digits

给两个数 $ N $ 与 $ M $，以及长度为 $ M $ 的序列 $ C $，保证 $ C $ 中任何数为一位数。

求出所有小于等于 $ N $ 且数位中出现过所有 $ C $ 的数字之和。

$ N\le10{104} $
$ 1\le M\le10 $
$ 0\le C_1<\dots<C_M\le9 $

分析：很明显的数位状压 dp，没什么好说的。

细节非常多，具体见代码。

我用的是二维的 dp[i][j][0\1][0\1]，表示的是当前在第 $ i $ 位，已经出现的数字集合为 $ j $，前面是否全为 $ 0 $，前面是否与 $ n $ 的这些位全部相等的数字之和。

fp[i][j][0/1][0/1]的含义基本一样，只不过记录的是方案数。

时间复杂度 $ O(\log_{10}n\times2^{10}\times10) $。

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
using ll=long long;
const int mod=998244353;
ll dp[10001][1024][2][2];
ll fp[10001][1024][2][2];
char a[10002];
int need;
int n,m;
ll ans;
int main()
{
	cin>>(a+1)>>m;n=strlen(a+1);
	for(int i=1;i<=m;i++)
	{
		int c;
		cin>>c;
		need|=1<<c;
	}
	dp[0][0][1][0]=0;
	fp[0][0][1][0]=1;
	for(int i=0;i<n;i++)
	{
		dp[i+1][0][1][0]=0;
		fp[i+1][0][1][0]=1;
		for(int j=0;j<1024;j++)
		{
			dp[i+1][j|1][0][0]=(dp[i+1][j|1][0][0]+dp[i][j][0][0]*10)%mod;
			fp[i+1][j|1][0][0]=(fp[i+1][j|1][0][0]+fp[i][j][0][0])%mod;
			if(a[i+1]=='0')
			{
				dp[i+1][j|1][0][1]=(dp[i+1][j|1][0][1]+dp[i][j][0][1]*10)%mod;
				fp[i+1][j|1][0][1]=(fp[i+1][j|1][0][1]+fp[i][j][0][1])%mod;
			}
			else
			{
				dp[i+1][j|1][0][0]=(dp[i+1][j|1][0][0]+dp[i][j][0][1]*10)%mod;
				fp[i+1][j|1][0][0]=(fp[i+1][j|1][0][0]+fp[i][j][0][1])%mod;
			}
			for(int k=1;k<10;k++)
			{
				int jj=j|(1<<k);
				dp[i+1][jj][0][0]=(dp[i+1][jj][0][0]+dp[i][j][0][0]*10+fp[i][j][0][0]*k)%mod;
				fp[i+1][jj][0][0]=(fp[i+1][jj][0][0]+fp[i][j][0][0])%mod;
				if(k<a[i+1]-'0')
				{
					dp[i+1][jj][0][0]=(dp[i+1][jj][0][0]+dp[i][j][0][1]*10+fp[i][j][0][1]*k)%mod;
					fp[i+1][jj][0][0]=(fp[i+1][jj][0][0]+fp[i][j][0][1])%mod;
					if(i==0)
					{
						dp[i+1][jj][0][0]=(dp[i+1][jj][0][0]+fp[i][j][1][0]*k)%mod;
						fp[i+1][jj][0][0]=(fp[i+1][jj][0][0]+fp[i][j][1][0])%mod;
					}
				}
				if(k==a[i+1]-'0')
				{
					dp[i+1][jj][0][1]=(dp[i+1][jj][0][1]+dp[i][j][0][1]*10+fp[i][j][0][1]*k)%mod;
					fp[i+1][jj][0][1]=(fp[i+1][jj][0][1]+fp[i][j][0][1])%mod;
					if(i==0)
					{
						dp[i+1][jj][0][1]=(dp[i+1][jj][0][1]+fp[i][j][1][0]*k)%mod;
						fp[i+1][jj][0][1]=(fp[i+1][jj][0][1]+fp[i][j][1][0])%mod;
					}
				}
				if(i!=0)
				{
					dp[i+1][jj][0][0]=(dp[i+1][jj][0][0]+fp[i][j][1][0]*k)%mod;
					fp[i+1][jj][0][0]=(fp[i+1][jj][0][0]+fp[i][j][1][0])%mod;
				}
			}
		}
	}
	for(int i=0;i<1024;i++) if((need&i)==need)
		ans=(ans+dp[n][i][0][0]+dp[n][i][0][1]+dp[n][i][1][0]+dp[n][i][1][1])%mod;
	cout<<ans;
	return 0;
}

ABC235 G - Gardens

你现在有 $ N $ 个花园，以及 $ A $ 个苹果苗，$ B $ 个香蕉苗，$ C $ 个樱桃苗。你现在要将这些树苗种到花园中。

求出使得每个花园非空且任何一个花园不能种植两个同类树苗的方案。

$ 1\le N\le5\times 10^6 $
$ 0\le A,B,C\le N $

分析：

首先判断一下特殊情况，如果 $ A+B+C<N $ 答案为 $ 0 $。

下来我们来看，假如说我们不要求每个花园非空，该怎么做？

我们来考虑每种树苗的放置情况。

苹果苗可以不放，方案数为 $ C^0_n $；可以放一个，方案数为 $ C^1_n $...；可以放 $ A $ 个，方案数为 $ C^A_n $。

香蕉苗，樱桃苗也是一样的。

所以总方案数为 $ (\sum\limits_{i=0}^A $$ C^i_n)\times $$ (\sum\limits_{i=0}^B $$ C^i_n) $$ \times(\sum\limits_{i=0}^C $$ C^i_n) $。

如果说要使得他非空，再加上一个容斥就可以了。

开开心心打完代码，发现 TLE 了。时间复杂度炸成 $ O(n^2) $。

考虑加速容斥的过程。想一想哪里复杂度最大？没错，求组合数的和的过程。

我们要对与每一个 $ i\le n $ 求出 $ \sum\limits_{j=0}^{\min(i,a)} $$ C_i^j $

显然，当 $ i\le a $ 时，上面的值为 $ 2^i $。

考虑 $ i>a $ 时的情况。

\[\sum\limits_{j=0}^{\min(i,a)}C_i^j \]

\[=\sum\limits_{j=0}^aC_i^j \]

利用杨辉三角可以知道上面的值为 $ =(\sum\limits_{j=0}^a $$ C_{i-1}^j)\times $$ 2-C_{i-1}^a $。

直接 $ O(1) $ 递推就行。

时间复杂度 $ O(n) $ 或 $ O(n\log mod) $

代码：

#include<iostream>
#include<cstdio>
using namespace std;
using ll=long long;
const int mod=998244353;
ll jc[5000001];
ll inv[5000001];
ll p[5000001];
ll numa,numb,numc;
int a,b,c;
int sum;
ll ans;
int n;
ll qow(ll a,int b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
ll C(int a,int b){ return jc[b]*inv[a]%mod*inv[b-a]%mod;}
ll run(ll numa,int a,int i)
{
	// printf("%lld %d %d\n",numa,a,i);
	if(a>=i) return p[i];
	numa=numa*2-C(a,i-1);
	return (numa%mod+mod)%mod;
}
int main()
{
	cin>>n>>a>>b>>c;sum=a+b+c;
	if(sum<n){ cout<<0;return 0;}
	inv[0]=jc[0]=p[0]=1;
	for(int i=1;i<=n;i++)
	{
		jc[i]=jc[i-1]*i%mod;
		inv[i]=inv[i-1]*qow(i,mod-2)%mod;
		p[i]=(p[i-1]*2)%mod;
	}
	for(int i=0;i<=n;i++)
	{
		numa=run(numa,a,i),numb=run(numb,b,i),numc=run(numc,c,i);
		ll num=numa*numb%mod*numc%mod;
		num=num*C(i,n)%mod;
		if((n-i)%2) ans=(ans-num+mod)%mod;
		else ans=(ans+num)%mod;
	}
	cout<<ans;
	return 0;
}

ABC235 Ex - Painting Weighted Graph

给定 $ N $ 个点与 $ M $ 条边的无向图，第 $ i $ 条边连接顶点 $ A_i $ 与 $ B_i $，边权为 $ C_i $。

你现在可以执行以下操作。

每次你可以任意指定一个节点 $ v $ 与整数 $ x $，将所有从节点 $ v $ 出发只经过边权不超过 $ x $ 的边就能到达的节点全部染成红色。

求经过不超过 $ K $ 次操作后节点变红的集合数量。

$ 2\le N\le 10^5 $
$ 0\le M\le 10^5 $
$ 1\le K \le 500 $
$ 1\le C_i \le 10^9 $

分析：

看到边权不超过 $ x $ 的边，你想到了什么？

没错！Kruskal 重构树！

我们把这个图的 Kruskal 重构树求出来，然后在重构树上跑树形 dp 就行了。

这里的 Kruskal 重构树还是有很多细节的，具体可以见代码。

时间复杂度 $ O(NK) $。

你可能会说：什么？这样做时间复杂度不是 $ O(NK^2) $ 吗？

是的，看起来确实是 $ O(NK^2) $ 的，但实际上，他真的是 $ O(NK) $。

时间复杂度证明：两个子树的合并可以分为三种情况，所以分类讨论

  1. 两个大小都大于等于 $ K $ 的子树合并；
    可以发现，大小大于等于 $ K $ 的子树最多只有 $ \dfrac{N}{K} $ 个，也就是说最多会合并 $ \dfrac{N}{K} $ 次。
    这部分时间复杂度 $ O(\dfrac{N}{K}\times K^2)=O(NK) $。

  2. 两个大小都小于 $ K $ 的子树合并；
    如果两个子树大小之和小于 $ K $，我们不考虑这种情况，归类到下面。
    如果两个子树大小之和大于等于 $ K $，设子树大小分别为 $ a,b $。
    时间复杂度 $ T(K)=T(a)+T(b)+a\times b $。
    在 $ a=b $ 时时间复杂度最大，此时：

\[T(K)=2T(\dfrac{K}{2})+K^2=O(K^2) \]

此时合并出一个大小大于等于 $ K $ 的子树时间复杂度为 $ O(K^2) $，且这个复杂度包含了第一类情况。
这种最多合并 $ \dfrac{N}{K} $ 次，时间复杂度 $ O(\dfrac{N}{K}\times K^2)=O(NK) $。

  1. 一个大小大于等于 $ K $ 和一个大小小于 $ K $ 的子树合并；
    一个大小为 $ a(a\ge K) $ 的子树与一个 $ b(b<K) $ 的子树
    合并起来时间复杂度为 $ O(Kb) $。

对于所有这种情况，$ \sum b\le N $。
所以这部分时间复杂度为 $ O(NK) $。

结合上面所有情况，时间复杂度为 $ O(NK) $。

代码：

#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
using ll=long long;
const int mod=998244353;
struct edge
{
	int u,v,w;
}a[100001];
basic_string<int>g[200001],num;
ll dp[200001][501];
int siz[200001];
int val[200001];
int fa[200001];
ll h[200001];
int n,m,k;
int tot;
int sum;
int find(int num)
{
	if(fa[num]==num) return num;
	return fa[num]=find(fa[num]);
}
void dfs(int num)
{
	if(num<=n){ siz[num]=1;return ;}
	dp[num][0]=1;
	for(int p:g[num])
	{
		dfs(p);
		for(int x=0;x<=siz[num]&&x<=k;x++)
			for(int y=0;x+y<=k&&y<=siz[p];y++)
				h[x+y]=(h[x+y]+dp[num][x]*dp[p][y])%mod;
		siz[num]+=siz[p];
		for(int x=0;x<=siz[num]&&x<=k;x++) dp[num][x]=h[x],h[x]=0;
	}
	if(num!=tot||sum==n-1)
	{
		dp[num][1]=(dp[num][1]+1)%mod;
		int s=(int)g[num].size();
		if(s<=k) dp[num][s]=(dp[num][s]-1+mod)%mod;
	}
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++) cin>>a[i].u>>a[i].v>>a[i].w;
	for(int i=1;i<=n;i++) fa[i]=i,dp[i][0]=dp[i][1]=1,g[i]+=i;
	sort(a+1,a+m+1,[](edge a,edge b){ return a.w<b.w;});tot=n;
	for(int i=1,j=1;i<=m;i=j)
	{
		int save=tot;
		for(;j<=m&&a[i].w==a[j].w;j++)
		{
			int u=find(a[j].u),v=find(a[j].v);
			if(u==v) continue;
			if(u>v) swap(u,v);sum++;
			if(v<=save)
			{
				tot++;val[tot]=a[j].w;
				fa[u]=fa[v]=fa[tot]=tot;
				g[tot]+=u,g[tot]+=v;
			}
			else
			{
				if(u<=save) g[v]+=u;
				else{ for(int i:g[u]) g[v]+=i;g[u].clear();}
				fa[u]=v;
			}
		}
	}
	for(int i=1;i<=tot;i++) if(find(i)==i) num+=i;
	if((int)num.size()>=2)
	{
		tot++;
		for(int i:num) fa[i]=tot,g[tot]+=i;
	}
	dfs(tot);
	ll ans=0;
	for(int i=0;i<=k;i++) ans=(ans+dp[tot][i])%mod;
	cout<<ans;
	return 0;
}

完结撒花！

上一篇：[HAOI2016]字符合并


下一篇：[loj2157]避雷针