AtCoder Beginner Contest 288 解题报告

\(\text{By DaiRuiChen007}\)

A. Many A+B Problems

直接模拟即可

时间复杂度 \(\Theta(n)\)

#include<bits/stdc++.h>
using namespace std;
signed main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		int a,b;
		scanf("%d%d",&a,&b);
		printf("%d\n",a+b);
	}
	return 0;
}

B. Qualification Contest

直接 std::sort 一遍即可

时间复杂度 \(\Theta(k|S|\log k)\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=101;
string str[MAXN];
signed main() {
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;++i) cin>>str[i];
	sort(str+1,str+k+1);
	for(int i=1;i<=k;++i) cout<<str[i]<<"\n";
	return 0;
}

C. Don’t be cycle

用并查集维护生成森林的连通性即可

时间复杂度 \(\Theta(m\alpha(n))\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;
int dsu[MAXN];
inline int find(int x) {
	if(dsu[x]==x) return x;
	return dsu[x]=find(dsu[x]);
}
signed main() {
	int n,m,ans=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) dsu[i]=i;
	for(int i=1;i<=m;++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		int x=find(u),y=find(v);
		if(x==y) ++ans;
		else dsu[x]=y;
	}
	printf("%d\n",ans);
	return 0;
}

D. Range Add Query

区间加显然想到差分，将原序列 \((a_1,a_2,a_3,\dots,a_n)\) 转成差分序列 \((b_1=a_1,b_2=a_2-a_1,b_3=a_3-a_2,\dots,b_n=a_n-a_{n-1})\)，同样只需将 \(b_1\sim b_n\) 全部变成 \(0\)

此时区间加 \(\delta\) 等价于找两个距离为 \(k\) 的点分别 \(+\delta\) 和 \(-\delta\)

可以发现我们可以把整个差分数组按下标 \(\bmod k\) 的余数分成 \(k\) 个类，可以证明当且仅当每个类中的 \(b_i\) 的和为 \(0\) 时有解，不过 \(n+1\bmod k\) 对应类不需要判断，应为总是可以把这个类的 \(b_i\) 都转移到 \(b_{n+1}\) 上

用前缀和快速维护即可

时间复杂度 \(\Theta(nk)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+1,MAXK=11;
int sum[MAXN][MAXK],a[MAXN],tmp[MAXK];
signed main() {
	int n,k,q;
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	for(int i=1;i<=n;++i) {
		for(int j=0;j<k;++j) sum[i][j]=sum[i-1][j];
		sum[i][i%k]+=a[i]-a[i-1];
	}
	scanf("%lld",&q);
	while(q--) {
		int l,r;
		scanf("%lld%lld",&l,&r);
		for(int i=0;i<k;++i) tmp[i]=sum[r][i]-sum[l-1][i];
		tmp[l%k]+=a[l-1];
		bool ok=true;
		for(int i=0;i<k;++i) if(i!=(r+1)%k) ok&=(!tmp[i]);
		puts(ok?"Yes":"No");
	}
	return 0;
}

E. Wish List

首先考虑如何以最小代价买若干件商品 \(i_1,i_2,\dots,i_k\)

显然从标号最小的商品 \(i_1\) 开始，显然购买 \(a_{i_1}\) 的额外代价一定是 \(c_{i_1}\)，接下来考虑 \(i_2\)，发现购买 \(a_{i_2}\) 的额外代价是 \(c_{i_2}\) 或 \(c_{i_2-1}\)，同理，我们可以证明购买第 \(k\) 件商品的额外代价可以是 \(c_{i_k}\sim c_{i_k-k+1}\) 中的任何一个，根据贪心，其额外代价一定是 \(c\) 中某一段的 rmq，可以直接预处理出来

因此我们能计算出每个商品在第几件被购买时的代价，因此可以直接设计一个简单的 dp，用 \(dp_{i,j}\) 表示前 \(i\) 件商品中买了 \(j\) 件（必选的保证买了）的最小代价，转移方程显然：

当 \(a_i\) 必选，那么 \(dp_{i,j}\gets dp_{i-1,j-1}+a_i+cost_{i,j}\)
当 \(a_i\) 非必选，那么 \(dp_{i,j}\gets \min(dp_{i-1,j-1}+a_i+cost_{i,j},dp_{i-1,j})\)

直接暴力转移即可，答案为 \(\min\{dp_{n,i}\}\)

时间复杂度 \(\Theta(n^2)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5001,INF=1e18;
int a[MAXN],c[MAXN],item[MAXN];
int f[MAXN][MAXN],dp[MAXN][MAXN];
bool inq[MAXN];
signed main() {
	int n,m;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	for(int i=1;i<=n;++i) scanf("%lld",&c[i]);
	for(int i=1;i<=m;++i) {
		scanf("%lld",&item[i]);
		inq[item[i]]=true;
	}
	for(int i=1;i<=n;++i) {
		f[i][0]=c[i];
		for(int j=1;j<i;++j) f[i][j]=min(c[i-j],f[i][j-1]);
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=i;++j) {
			dp[i][j]=dp[i-1][j-1]+f[i][j-1]+a[i];
		}
		if(!inq[i]) {
			for(int j=0;j<=i;++j) {
				dp[i][j]=min(dp[i][j],dp[i-1][j]);
			}
		}
	}
	int ans=INF;
	for(int i=m;i<=n;++i) ans=min(ans,dp[n][i]);
	printf("%lld\n",ans);
	return 0;
}

F. Integer Division

有一个显然的 dp 设计：\(dp_i\) 表示 \(S[1,i]\) 的答案，转移方程如下：

\[dp_{i}=\sum_{0\le j<i} dp_j+2^{j-1}\times S[j+1,i]
\]

其中 \(S[j+1,i]\) 表示这一段子串的十进制实际值，用前缀和 \(f_i=S[1,i]\) 维护可以得到 \(S[j+1,i]=f_i-f_j\times 10^{i-j}\)，带入化简可得：

\[\begin{aligned}
dp_{i}
&=\sum_{0\le j<i} dp_j+2^{j-1}S[j+1,i]\\
&=\sum_{0\le j<i} dp_j+2^{j-1}(f_i-f_j\times 10^{i-j})\\
\end{aligned}
\]

显然可以把所有和 \(j\) 有关的式子分离出来用前缀和优化即可

时间复杂度 \(\Theta(n\log n)\)，预处理快速幂可以优化到 \(\Theta(n)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+1,MOD=998244353,INV=299473306;
inline int ksm(int a,int b,int m=MOD) {
	int ret=1;
	while(b) {
		if(b&1) ret=ret*a%m;
		a=a*a%m;
		b=b>>1;
	}
	return ret;
}
int dp[MAXN],sum[MAXN][2],val[MAXN];
char str[MAXN];
signed main() {
	int n;
	scanf("%lld%s",&n,str+1);
	for(int i=1;i<=n;++i) val[i]=(val[i-1]*10+str[i]-'0')%MOD;
	dp[0]=1,sum[0][0]=1,sum[0][1]=0;
	for(int i=1;i<=n;++i) {
		dp[i]=(sum[i-1][0]*val[i]%MOD+MOD-sum[i-1][1]*ksm(10,i)%MOD)%MOD;
		sum[i][0]=(sum[i-1][0]+dp[i])%MOD;
		sum[i][1]=(sum[i-1][1]+dp[i]*val[i]%MOD*ksm(INV,i)%MOD)%MOD;
	}
	printf("%lld\n",dp[n]);
	return 0;
}

G. 3^N Minesweeper

考虑 \(n=1\) 的情况，显然有如下转化：

\[\begin{cases}
A_0=B_0+B_1\\
A_1=B_0+B_1+B_2\\
A_2=B_2+B_2
\end{cases}
\iff
\begin{cases}
B_0=A_1-A_2\\
B_1=A_0+A_2-A_1\\
B_2=A_1-A_0
\end{cases}
\]

对于 \(n>1\) 的情况，用 FWT 的思想，分别枚举每一位并逐位容斥即可

时间复杂度 \(\Theta(n3^n)\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=6e5+1;
int a[MAXN];
signed main() {
	int n,m=1;
	scanf("%d",&n);
	for(int i=0;i<n;++i) m*=3;
	for(int i=0;i<m;++i) scanf("%d",&a[i]);
	for(int k=1;k<m;k*=3) {
		for(int st=0;st<m;st+=k*3) {
			for(int i=st;i<st+k;++i) {
				int b[3]={a[i],a[i+k],a[i+k*2]};
				a[i]=b[1]-b[2],a[i+k]=b[0]+b[2]-b[1],a[i+k*2]=b[1]-b[0];
			}
		}
	}
	for(int i=0;i<m;++i) printf("%d ",a[i]); puts("");
	return 0;
}