2024 11.14训练赛

文章目录

前言
题目链接
C - Kousuke's Assignment
E - Black Cells
C. Sakurako's Field Trip
C. Alya and Permutation

前言

这次训练赛难度中等，主要都是前段时间CF里面难度中等的题目。这次自己写的不是很好，有几题有思路，将近完成代码，但是最后没有写出来，有点可惜。总体写的不是很好。主要考察的点就是思维的运用，还有一些简单的类似二分算法。继续学习~~~

题目链接

Vjudge

C - Kousuke’s Assignment

给出一串序列，要求找出不重叠的并且想加起来为0的最大序列数量。题目理解起来不难，难点就在于怎么找。其实可以用贪心的思路，从左到右，一旦发现总和为0，就ans++，最后输出ans的值。
所以我们这里就要用到前缀和来方便查询区间和，我们便利前缀和区间，发现有相同的数字就说明这一段区间和为0。然后可以用一个变量来标记这个区间的范围，保证这个区间只有他这一组区间为0的数据

void Solve () {
	int n;cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>a[i];
		a[i]+=a[i-1];
	}
	map<int,int>b;
	int ans = 0;
	int pos = -1;
	b[0]=1;
	for (int i=1;i<=n;i++) {
		if (b[a[i]]) {
			if (b[a[i]]>pos) {
				pos = i-1;
				ans++;
			}
			b[a[i]]=i;
		}
		else b[a[i]]=i;
	}
	cout<<ans<<'\n';
	return ;
}

重要的就是用pos来标记区间最右边，保证区间之间不重叠。

E - Black Cells

给出一串序列，起初都是白色的，要求每次选择两个白色的染色成黑色。两个白色的坐标之差的绝对值为 $\left | i-j \right | < k$ ，求k的最小值。
由于题目所给出的范围比较大，这里又是求最小值，所以显而易见要用到二分。
但是赛时看错题了，所以想了大半天的错误思路QWQ。
我们可以发现，如果n是偶数的话，显而易见要第1个跟第2个选择，第三个跟第四个选择~~~
如果n是奇数的话，我们就可以二分k，然后判断能否在只跟外界选择一次的条件下满足k的大小。

int check (int x) {
	int t=1;
	for (int i=2;i<=n;) {
		int k = a[i]-a[i-1];
		if (k<=x) i+=2;
		else {
			if (n&1) {
				if (t) {
					t=0;i++;
				}
				else return 0;
			}
			else return 0;
		}
		
	}
	return 1;
}

void Solve () {
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>a[i];
	}
	int l = 1,r=1e18;
	while (l<r) {
		int mid = l+r >>1;
		if (check(mid)) r = mid;
		else l=mid+1;
	}
	cout<<l<<'\n';
	return ;
}

C. Sakurako’s Field Trip

一道我觉得比较难想的题。主要是用到了动态规划的思想，从小部分推到整体，然后结合贪心的思想。
题目要求对于交换，只能交换它对称的那个位置上的值。给出一段序列1,2,3,4.我们可以发现对于每个的领居来说，交换2,3和1,4序列变成4,3,2,1。可以发现，每个人的领居又是一样的。那我们可以用1,2,3,4,5,6,7,8,9甚至更长的序列可以知道，如果每一个位置都变换的话，就等价于没有变。
然后我们贪心的想，对于每一个位置上的值，我们都有换与不换两种状态，我们如果想考虑最优解，就要考虑两边的领居，但是我们可以知道用动态规划的话，一边的领居就已经确定最优位置了，所以对于任何一个领居上的状态，我们就只用考虑一边的领居。
整体就是动态规划的思路，从两边开始可以确定一个位置，然后就可以不考虑两边，继续往后比较了。

void Solve () {
	int n;cin>>n;
	int pos1 = 0;
	for (int i=1;i<=n;i++) {
		cin>>a[i];
	}
	int pos = n/2;
	if (n%2==0) pos--;
	while (pos>=1) {
		int t1 = a[pos]==a[pos+1]?1:0;
		t1 += a[n-pos+1]==a[n-pos]?1:0;
		int t2 = a[n-pos+1]==a[pos+1]?1:0;
		t2+=a[pos]==a[n-pos]?1:0;
		if (t1>t2) {
			swap(a[pos],a[n-pos+1]);
		}
		pos--;
	}
	int ans = 0;
	for (int i=1;i<n;i++) {
		if (a[i]==a[i+1]) ans++;
	}
	cout<<ans<<'\n';
	return ;
}

C. Alya and Permutation

一道构造题，给出n，要求构造出 $1 到 n$ 中所有的数字，并且进行与或非操作。开始一个k为0，当数组下标为奇数时进行与操作，为偶数时进行或操作，问怎么构造k的值最大，最大值为多少？
观察数据并且上手操作可以发现，当为奇数时，最大值为自己本身，当为偶数时为二进制下的位数全为1的值。我们可以发现，当n为奇数时，构造结果就时n-1的构造结果后面加上n。所以我们只需要考虑n为偶数的时候，如果想构造出全部的二进制下的1，就要在倒数第二位和倒数第一位上进行|操作，找规律可以发现，倒数第三位为n时（因为这一位为|操作，这样可以确定二进制下的最高位的值，后续进行&操作可以保证一位已经确定），倒数第二位为n+1，最后一位为最大值减n就能构造出一个最大值的序列。但是当n为4,8,16,32这种数字的时候，我们稍加特判即可。

void Solve () {
	int n;cin>>n;k=0;string s = qwe(n);
	int f = 0,flag=0;	
	int len = s.size();
	int ans = 0;
	if (n&1) ans =n;
	else ans = pow(2,len)-1;
	cout<<ans<<'\n';
	if (n==5) {
		if (n==5) cout<<2<<' '<<1<<' '<<3<<' '<<4<<' '<<5;
		cout<<'\n';return ;
	}
	if (n&1) {
		n--;flag=1;
		k=0;
		s = qwe (n);
		len = s.size();
	}
	if (k==1) {
		f=1;n-=2;
		s = qwe (n);
		len = s.size();
	}	 
		
		int pos = pow(2,len)-1;
		int t = pow(2,len-1);
		map<int,int>mp;
		mp[t+1]=1,mp[t]=1,mp[pos-t]=1;
		for (int i=1;i<=n;i++) {
			if (mp[i]==0)
			cout<<i<<' ';
		}
		cout<<t<<' '<<t+1<<' '<<pos-t<<' ';
		if (f) cout<<n+1<<' '<<n+2<<' ';
		if (flag) {
			if (f) cout<<n+3;
			else cout<<n+1;
		}
	
	cout<<'\n';
	return ;
}

秒客网