526互联

CF1197 Educational Codeforces Round 69 (Rated for Div. 2)

发布时间 2023-09-27 22:28:34作者: Zhou_JK

CF1197A DIY Wooden Ladder

答案为 \(\min(a_{n-1},n-2)\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int T;
int n;
int a[N];
void solve()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	printf("%d\n",min(a[n-1]-1,n-2));
}
int main()
{
	scanf("%d",&T);
	while(T--)
		solve();
	return 0;
}

CF1197B Pillars

最后肯定将所有的盘子移到最大的那个盘子上面，判断一下每个盘子到最大的那个中间是否有盘子小于当前盘子即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
int n;
int a[N];
int pos[N];
int Min[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		pos[a[i]]=i;
	int u=pos[n];
	Min[u]=a[u];
	for(int i=u-1;i>=1;i--)
		Min[i]=min(Min[i+1],a[i]);
	for(int i=u+1;i<=n;i++)
		Min[i]=min(Min[i-1],a[i]);
	for(int i=1;i<=n;i++)
		if(Min[i]<a[i])
		{
			printf("NO");
			return 0;
		}
	printf("YES");
	return 0;
}

CF1197C Array Splitting

可以发现，上一个段最大值跟下一段的最小值肯定是相邻的，选 \(i\) 作为分界点贡献为 \(a_i-a_{i+1}\)，选贡献最小的 \(k-1\) 个位置就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=300005;
int n,k;
int a[N];
int b[N];
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<n;i++)
		b[i]=a[i]-a[i+1];
	sort(b+1,b+n);
	long long ans=a[n]-a[1];
	for(int i=1;i<=k-1;i++)
		ans+=b[i];
	printf("%lld",ans);
	return 0;
}

CF1197D Yet Another Subarray Problem

令 \(f_{i,j}\) 表示强制以第 \(i\) 个数结尾，长度模 \(m\) 为 \(j\) 的最大权值。

转移为：

\[f_{i,j}=\begin{cases} \max(f_{i-1}{m-1}+a_i,0) &(j=0) \\ f_{i-1,j-1}-k+a_i &(j=1) \\ f_{i-1}{j-1} &(2\leq j\leq m-1)\end{cases} \]

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=300005;
const long long INF=4557430888798830399;
int n,m,k;
int a[N];
long long dp[N][10];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	memset(dp,-63,sizeof(dp));
	dp[0][0]=0;
	long long ans=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<m&&j<=i;j++)
		{
			if(m==1&&j==0) dp[i][j]=max(dp[i-1][m-1]-k+a[i],0LL);
			else if(j==0) dp[i][j]=max(dp[i-1][m-1]+a[i],0LL);
			else if(j==1) dp[i][j]=dp[i-1][0]-k+a[i];
			else dp[i][j]=dp[i-1][j-1]+a[i];
			ans=max(ans,dp[i][j]);
		}
	printf("%lld",ans);
	return 0;
}

CF1197E Culture Code

首先有一个简单的 DP，令 \(f_{i}\) 表示前 \(i\) 个套娃能套出最小值，有转移：

\[f_{i}=\min\limits_{out_j\leq in_i}\{f_{j}+in_i-out_j\} \]

DP 的同时记录一下方案数就可以了，按照 \(out_i\) 排序后前缀和优化即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200005;
const int MOD=1000000007;
const long long INF=4557430888798830399;
int n;
struct Doll
{
	int in,out;
	bool operator<(const Doll &b)const
	{
		return out<b.out;
	}
}d[N];
long long dp[N],f[N];
long long Min[N],sum[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&d[i].out,&d[i].in);
	sort(d+1,d+n+1);
	int Max=0;
	for(int i=1;i<=n;i++)
		Max=max(Max,d[i].in);
	memset(dp,63,sizeof(dp));
	long long m=INF,ans=0;
	Min[0]=INF;
	for(int i=1;i<=n;i++)
	{
		if(i==1||d[1].out>d[i].in) dp[i]=d[i].in,f[i]=1;
		int j=upper_bound(d+1,d+i,(Doll){0,d[i].in})-d-1;
		if(j<=i-1)
		{
			if(Min[j]+d[i].in<dp[i]) dp[i]=Min[j]+d[i].in,f[i]=sum[j];
			else if(Min[j]+d[i].in==dp[i]) f[i]=(f[i]+sum[j])%MOD;
		}
		if(d[i].out>Max)
		{
			if(dp[i]<m) m=dp[i],ans=f[i];
			else if(dp[i]==m) ans=(ans+f[i])%MOD;
		}
		Min[i]=Min[i-1],sum[i]=sum[i-1];
		if(dp[i]-d[i].out<Min[i]) Min[i]=dp[i]-d[i].out,sum[i]=f[i];
		else if(dp[i]-d[i].out==Min[i]) sum[i]=(sum[i]+f[i])%MOD;
	}
	printf("%lld",ans);
	return 0;
}

CF1197F Coloring Game

考虑只有一根纸条的时候怎么做。

令 \(f_{i,x,y,z}\) 表示前 \(i\) 个格子，最后三个格子的 SG 函数值为 \(x,y,z\) 的方案数。枚举当前位置填什么数转移即可。把三个数压成一个数矩阵乘就好了，预处理出 \(2^k\) 的矩阵倍增即可。

考虑有多个纸条，先手必胜的条件为所有纸条的 SG 函数值异或和为 \(0\)。然后背包合并即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1005;
const int MOD=998244353;
int n,m;
int a[N];
int f[4][4];
vector<pair<int,int>>pos[N];
int tot;
struct Matrix
{
	static const int M=64;
	int n,m;
	long long mat[M][M];
	Matrix(int _n=0,int _m=0)
	{
		n=_n,m=_m;
		memset(mat,0,sizeof(mat));
		return;
	}
	void clear()
	{
		memset(mat,0,sizeof(mat));
		for(int i=0;i<=min(n,m);i++)
			mat[i][i]=1;
		return;
	}
	Matrix operator *(const Matrix &b)const
	{
		Matrix res(n,b.m);
		for(int i=0;i<=n;i++)
			for(int j=0;j<=b.m;j++)
				for(int k=0;k<=m;k++)
					res.mat[i][j]=(res.mat[i][j]+mat[i][k]*b.mat[k][j]%MOD)%MOD;
		return res;
	}
};
int getmex(const vector<int> &val)
{
	static bool vis[N];
	for(int u:val)
		vis[u]=true;
	int ans=0;
	for(int i=0;;i++)
		if(!vis[i])
		{
			ans=i;
			break;
		}
	for(int u:val)
		vis[u]=false;
	return ans;
}
int convert(int x,int y,int z)
{
	return x|(y<<2)|(z<<4);
}
long long dp[N][4];
long long g[N][4];
Matrix A[40];
Matrix vector_ksm(const Matrix &a,int b)
{
	Matrix res=a;
	for(int i=30;i>=0;i--)
		if(b&(1<<i)) res=res*A[i];
	return res;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		pos[x].emplace_back(y,c);
	}
	for(int i=1;i<=n;i++)
		sort(pos[i].begin(),pos[i].end());
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
			scanf("%d",&f[i][j]);
	tot=convert(3,3,3);
	A[0].n=A[0].m=tot;
	for(int x=0;x<=3;x++)
		for(int y=0;y<=3;y++)
			for(int z=0;z<=3;z++)
				for(int p=1;p<=3;p++)
				{
					vector<int>val;
					if(f[p][1]) val.emplace_back(x);
					if(f[p][2]) val.emplace_back(y);
					if(f[p][3]) val.emplace_back(z);
					int w=getmex(val);
					A[0].mat[convert(x,y,z)][convert(w,x,y)]++;
				}
	for(int i=1;i<=30;i++)
		A[i]=A[i-1]*A[i-1];
	for(int i=1;i<=n;i++)
	{
		Matrix T(0,tot);
		T.mat[0][convert(3,3,3)]=1;
		int pre=0;
		for(auto [now,p]:pos[i])
		{
			T=vector_ksm(T,now-1-(pre+1)+1);
			pre=now;
			Matrix G(tot,tot);
			for(int x=0;x<=3;x++)
				for(int y=0;y<=3;y++)
					for(int z=0;z<=3;z++)
					{
						vector<int>val;
						if(f[p][1]) val.emplace_back(x);
						if(f[p][2]) val.emplace_back(y);
						if(f[p][3]) val.emplace_back(z);
						int w=getmex(val);
						G.mat[convert(x,y,z)][convert(w,x,y)]++;
					}
			T=T*G;
		}
		T=vector_ksm(T,a[i]-(pre+1)+1);
		for(int j=0;j<=T.m;j++)
			g[i][j&3]=(g[i][j&3]+T.mat[0][j])%MOD;
	}
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int x=0;x<=3;x++)
			for(int y=0;y<=3;y++)
				dp[i][x^y]=(dp[i][x^y]+dp[i-1][x]*g[i][y]%MOD)%MOD;
	printf("%lld",dp[n][0]);
	return 0;
}