526互联

Educational Codeforces Round 151 A~E

发布时间 2023-08-01 20:00:22作者: weakpyt

前言：F是个FFT，不想写。

A-Forbidden Integer

你需要构造一个正整数序列，满足：

  1. 对于 \(i\)，\(a_i\le k\) 且 \(a_i\not=x\)。
  2. \(\sum a_i=n\)。

如无法构造，输出 NO，否则输出 YES 后，输出序列长度与序列中的每一个数。
题解：
注意到顺序不重要，两个限制并不困难。考虑一种构造方案：整个序列有最少 \(len-1\) 个数相同，而剩下一个数用来凑 \(n\) 即可。

我们枚举这个相同的数 \(i(1\le i\le k)\)，此时凑数的那个有两个选择：\(n\bmod i\) 或 \(n\bmod i + i\)。这样两个不同的取值可以灭掉 \(m\) 的限制。当我们枚举到一个数可以满足条件，直接输出即可。否则无解。

		int tag=0;
		for(int i=1;i<=k;i++){
			int y=n%i;
			if(m==i)continue;
			if(y+i<=k&&m!=y+i){
				cout<<"Yes\n";
				cout<<n/i<<"\n"<<y+i<<" ";
				for(int j=2;j<=n/i;++j)cout<<i<<" ";
				cout<<"\n";tag=1;break;
			} 
			if(m==y)continue;
			cout<<"Yes\n";
			if(y==0){
				cout<<n/i<<"\n";
				for(int j=1;j<=n/i;++j)cout<<i<<" ";
			}
			else {
				cout<<n/i+1<<"\n";
				for(int j=1;j<=n/i;++j)cout<<i<<" ";cout<<y<<" ";
			}
			puts("");tag=1;break;
		}
		if(!tag)cout<<"No\n";

B-Come Together

给定无限大的网格图中 \(A\)，\(B\)，\(C\) 三点的横纵坐标，你需要求出，从 \(A\) 分别到 \(B\) 与 \(C\) 的最短路径(曼哈顿)最大有多少格点重合。

题解：考虑将横与纵分开看，我们实际要求的是线段 \((x_1,x_2),(x_1,x_3)\) 的交点(整点)，与 \((y_1,y_2),(y_1,y_3)\) 的交点(整点)，最后注意到有一个拐点被重复统计，减掉即可。

但是在代码实现中，我们直接通过做差的方式，这样会将拐点漏掉，加上就OK。

signed main(){
	t=r();
	while(t--){
		int x1=r(),y1=r(),x2=r(),y2=r(),x3=r(),y3=r();
		int a1=0,a2=0;
		if(x1==x2&&x3==x1)a1=0;
		else {
			if(x1>min(x2,x3)&&x1<max(x2,x3))a1=0;
			else a1=min(abs(x1-x2),abs(x1-x3));
		}
		if(y1==y2&&y3==y1)a2=0;
		else{
			if(y1>min(y2,y3)&&y1<max(y2,y3))a2=0;
			else a2=min(abs(y1-y2),abs(y1-y3));
		}
		cout<<a1+a2+1<<"\n"; 
	} 
}

C-Strong Password

题面：给定一个字符串 \(s\)，以及两个长度为 \(m\) 的字符串 \(l,r\)。你需要判断是否没有长度为 m 的字符串 \(t\) 满足以下要求：

  1. 对于 \(1\le i\le n\)，\(l_i\le t_i\le r_i\)。
  2. \(t\) 不是 \(s\) 的一个子序列。

这题目NM是真的拗口，我的语文老师我对不起你啊

对于这种判断满足某种限制的存在性的问题，有经典套路：尝试构造符合条件的。

在本题中，最关键的地方是：各位相对独立，没有前后位之间的奇怪关系。题意也即要我们判断是否所有符合条件1的字符串都是它的子序列。我们可以先判断长度为 \(1\) 的，再逐步扩展到长度为 \(m\) 的子序列。那么我们要填完了第 \(i\) 位再填第 \(i+1\) 位。(没填满就说明有不是的)。设 \(sur\) 表示当前位还剩下几个数没填，\(vis_i\) 表示这个数在当前位是否已经填过，而 \(j\) 表示正在填第几位。

我们依次扫描原序列，设扫描到了 \(i\)，若 \(s_i\in[l_j,r_j],vis[s_i]=0\)，则说明我们必须将这个数填上，否则会被噶掉。此时 \(sur\longleftarrow sur-1\)，\(vis[s_i]\longleftarrow 1\)。若此时 \(sur=0\)，则往下一位： \(j'\longleftarrow j+1,sur=r_{j'}-l_{j'}+1\)。若 \(j\) 已填满，则说明没办法了。只能输出NO退出。否则到最后也没有填满，输出YES。

        int j=0,sur=r[0]-l[0]+1;
		for(int i=0;i<10;++i)val[i]=0;
		for(int i=1;i<=n;i++){
			if(l[j]<=s[i]&&s[i]<=r[j]&&val[s[i]-'0']==0)--sur,val[s[i]-'0']=1;
			if(sur==0&&j==m-1){
				cout<<"No\n";break;	
			}
			if(!sur){
				++j;sur=r[j]-l[j]+1;for(int i=0;i<10;++i)val[i]=0;
			}
		}
		if(sur!=0||j!=m-1)cout<<"Yes\n";

D-Rating System

题面：给定一个长度为 \(n\) 数列 \(a\)，保证每项都不为 \(0\)。初始时 \(x=0\)，然后对于 \(1\le i\le n\)，按顺序进行如下操作：

  • 如果 \(x\ge k\)，则 \(x\rightarrow \max(k, x+a_i)\)，否则 \(x\rightarrow x+a_i\)。

你需要求出 \(k\)，使得 \(x\) 的值尽量大。

题解：容易发现，当 \(x\ge k\) 后，无论进行什么操作，\(x\) 都不会小于 \(k\)。

而，设 \(x\) 在 \(i\) 处变为 \(k\)，在 \(j_1,j_2,\dots j_m\) 处再次减为 \(k\)。则可以推出 \(sum[i+1,j_1],sum[j_1+1,j_2]\dots sum[j_{m-1}+1,j_m]\le 0\)。进而可以得到 \(sum[i+1,j_m]\le 0\)。

而我们本质上是将这几段区间和改为了0。但我们发现它虽然改了几段，但效果相同：等价于将 \(sum[i+1,j_m]\) 改为了0。而这个区间有什么性质呢？

以 \(i+1\) 为左端点的最小子段和！因为在最小子段和中，由两端删去一个值为负的区间，剩下的那个区间的和必定不会大于0，否则删去的这个区间才是真正的最小子段和。反着推过来，这便是最小子段和。

而这个的处理呢？我们倒着做一遍最小子段和的动态规划，就可以得到以某个点作为左端点的最小子段和了。设 \(f_i\) 表示 \([i,n]\) 的最小子段和，最后实际上 \(x\) 的值为 \(k+sum[i+1,n]-f_{i+1}\)（这里显然在 \(i\) 时令 \(k=x\) 可以取到最大值）

而 \(k\) 等价于 \(sum[1,i]\)。所以 \(x\) 的最大值实际为总和减去最小子段和。而 \(k\) ，则等于 \(sum[1,i]\)。

注意这里不需要判断 \([1,i]\) 是否满足区间内没有负数，因为如果有，则根本不会选择这个 \(i\)。

int a[505050];
int get(int k){
	int x=0;
	for(int i=1;i<=n;i++){
		if(x>=k)x=max(k,x+a[i]);
		else x=x+a[i];
	}
	return x;
}
int f[505050];
signed main(){
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--){
		cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
		f[n+1]=0;
		for(int i=n;i;--i){
			f[i]=min(f[i+1]+a[i],a[i]);
		}
		for(int i=1;i<=n;i++){
			a[i]+=a[i-1];
		}
		int id=-1;
		for(int i=1;i<=n;i++){
			if(id==-1||f[id]>f[i])id=i;
		}
		cout<<a[id-1]<<"\n"; 
	} 
}

E-Boxes and Balls

关键：注意到一个数组可以通过两次操作不变化，这启发我们将恰好转化为奇偶性相同的最少

设 \(g_i\) 为将原序列变为本质不同的序列中，最小操作数为 \(i\) 的序列个数。

则 \(ans=\sum_{i=1}^kg_i[(i+k)\bmod 2=0]\)

这是本题中第一个关键。

考虑对于一个新序列 \(b_1\sim b_n\)，它的最小操作数是？

第二个关键：由于元素只有1,0，则可以关注值相同的数的相对位置。

由于1不能与1交换，0不能与0交换，所以相对而言，1的顺序是固定的。设 \(pos_i\) 表示原序列中第 \(i\) 个1的位置，\(pos'_i\) 表示原序列中第 \(i\) 个1的位置，则最小操作数为 \(\sum_{i=1}^{cnt_1}|pos_i-pos'_i|\)。运用相对思想，统计每个1的相对位置之差，相当于统计序列中每个位置经过了多少1，而由于1的相对位置不变，可以有：设 \(s\) 为前缀和数组，则 \(\sum_{i=1}^{cnt_1}|pos_i-pos'_i|=\sum_{i=1}^n|s_i-s'_i|\)。

由于前缀和数组与原数组形成双射(一一对应)，故 \(g_i\) 转化为求所有合法的 \(s'\) 中，\(\sum_{i=1}^n|s_i-s'_i|=i\) 的个数。

合法的 \(s\)？两个条件：

  1. \(s_0=0,s_n=cnt_1\)
  2. \(0\le s_i-s_{i-1}\le 1(i\in [1,n])\)

（这里不难看出合法的 \(s\) 总共有 \({n\choose cnt_1}\) 个）

如何求出 \(g_i\)？这显然是一个动态规划问题。设 \(f_{i,j,k}\) 表示在前 \(i\) 个数中， \(s_i=j\)，且 \(\sum_{x=1}^i|s_i-s'_i|=k\) 的 \(s\) 的个数。

考虑一个朴素的转移，有：

\[f_{0,0,0}=0,f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k-|s_i-j|} \]

注意第一维在实现的时候要滚掉(此时 \(k\le |s_i-j|\) 的部分需要全部归0)。时间复杂度 \(O(n^3)\)。无法通过。

考虑优化。

这里注意到，将 \([1,x]\) 中 \(h\) 个1移动到区间外，最好的办法是移动到 \(x+1,x+2…x+h\)，但即使这样，也最少要移动 \(h^2\) 次。所以 \(j\) 只需要在 \(s_i\pm \sqrt k\) 范围内更新即可。(否则必定不会对 \(k\) 产生贡献)。

那么，复杂度就降低到了 \(O(n^{2.5})\)。这里 \(n,k\) 同级。

这里有另一个可以通过的做法，但时间复杂度稍劣(慢了大概二十倍)

那就是不维护 \(s\)，而是维护 \(pos\)，这样复杂度就变成了 \(O(nkc)\)，其中 \(c\) 是 \(1\) 的个数。稍稍卡卡可以过的。

signed main(){
	read(n),read(m);
	for(int i=1;i<=n;i++){
		read(s[i]);s[i]+=s[i-1]; 
	}
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=min(s[n],s[i]+45ll);j>=max(0ll,s[i]-45ll);j--){
			for(int k=m;k>=abs(s[i]-j);k--){
				f[j][k]=f[j][k-abs(s[i]-j)];
				if(j>0)f[j][k]=(f[j][k]+f[j-1][k-abs(s[i]-j)])%p; 
			}
			for(int k=abs(s[i]-j)-1;k>=0;--k)f[j][k]=0; 
		}
	}
	int ans=0;
	for(int i=m&1;i<=m;i+=2){
		ans=(ans+f[s[n]][i])%p;
	}
	cout<<ans<<"\n";
}