CF1733

发布于 2022-09-20  267 次阅读


碎碎念

一些在csp反扑大成功之后的大失败

csp反扑大成功,100+100+100+55+70=425

总rk28,新生rk1直接进队QwQ

于是第二天本想当作紫名晋级赛的CF遭遇巨大滑铁卢......

C漏读一句话,rating痛失98

A - Consecutive Sum

给你长度为n的数组a和整数k

每次操作可以将下标对k同余的两个数交换位置

至多执行k次操作,最大化连续k个数的和

solution

显然同余的分成1组,一共k组,每组取最大的

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		int n,k;
		cin >> n >> k;
		int x,a[110];
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++)
		{
			cin >> x;
			if(x>a[i%k])
				a[i%k]=x;
		}
		long long ans=0;
		for(int i=0;i<k;i++)
			ans+=a[i];
		cout<<ans<<endl;
	}
	return 0;
}

B - Rule of League

n个人举行n-1场比赛,1先和2打,胜者和3打,依次往后决出最后的胜者

现在满足一个人要么胜x场要么胜y场,求出一组可行解

solution

发现必须满足关于a的方程ax+(n-a)y=n-1有整数解且解在0到n的范围

显然x和y必须有且仅有一个为0,剩下那个必须得被n-1整除

然后按题意构造即可

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		int n,x,y;
		cin >> n >> x >> y;
		if(x>y)swap(x,y);
		if(x==0&&y!=0&&(n-1)%y==0)
		{
			for(int i=1,c=2;i<n;i++)
			{
				cout<<c<<(i==n-1?'\n':' ');
				if(i%y==0)
					c+=y;
			}
		}
		else cout<<"-1\n";
	}
	return 0;
}

C - Parity Shuffle Sorting

给你一个长度为n的数组a,每次操作可以选取两个数

如果和为奇数则a[r]=a[l],和为偶数则a[l]=a[r]

现在需要在n次操作内使得数组a严格不降,找出方案

solution

显然把a数组都变成一样的就行了

先对于头和尾进行一次操作,变成相同的

然后对于中间的每一个数,一定能变成头或者尾

#include<bits/stdc++.h>
using namespace std;
int t,n,a[100010];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> t;
	while(t--)
	{
		cin >> n;
		for(int i=1;i<=n;i++)
			cin >> a[i];
		if(n==1)
		{
			cout<<"0\n";
			continue;
		}
		cout<<n-1<<endl;
		cout<<1<<" "<<n<<endl;
		if((a[1]+a[n])%2)a[n]=a[1];
		else a[1]=a[n];
		for(int i=2;i<n;i++)
		{
			if((a[1]+a[i])%2)
				cout<<1<<" "<<i<<endl;
			else cout<<i<<" "<<n<<endl;
		}
	}
	return 0;
}

D - Zero-One

给你两个长度均为n的01序列

每次操作可以将序列中的两个数同时翻转

如果两个数相邻,代价为x,不相邻,代价为y

求从第一个序列变成第二个序列的最小代价

solution

分成两种情况讨论,x>=y和x<y

x>=y,不相邻的一定更优,发现除非只剩两个相邻的,否则一定能全部用不相邻的去做

x<y,假设一开始所有操作全部以y为代价,那么更优秀的一定是用x操作去滚动的替换两个相邻的数

设dp[i]表示到第i个要操作的点用x代替y能节省的最大代价,很容易推出递推方程

#include<bits/stdc++.h>
using namespace std;
int t,n,x,y,p[5010];
char a[5010],b[5010];
int o[5010];
long long dp[5010];
bool check()
{
	int cnt=0;
	for(int i=0;i<n-1;i++)
		if(p[i]&&p[i+1])
			cnt++;
	return cnt==1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> t;
	while(t--)
	{
		cin >> n >> x >> y >> a >> b;
		int cnt=0;
		for(int i=0;i<n;i++)
			p[i]=(a[i]!=b[i]),cnt+=p[i];
		if(cnt%2)
		{
			cout<<"-1\n";
			continue;
		}
		if(x>=y)
		{
			x=min(x,y*2);
			if(cnt==2&&check())cout<<x<<endl;
			else cout<<1ll*cnt/2*y<<endl;
		}
		else
		{
			int r=0;
			for(int i=0;i<n;i++)
			{
				if(p[i])o[++r]=i;
				dp[i+1]=0;
			}
			dp[1]=0,dp[2]=max(0ll,y-1ll*(o[2]-o[1])*x);
			for(int i=3;i<=r;i++)
				dp[i]=max(dp[i-1],dp[i-2]+y-1ll*(o[i]-o[i-1])*x);
			cout<<1ll*cnt/2*y-dp[r]<<endl;
		}
	}
	return 0;
}

E - Conveyor

一个矩阵上摆满了传送带,只有向右和向下两种方向,一开始全部朝向右边

每一秒会从左上角生成一个球,而每有一个球经过传送带,传送带就会改变方向

现在询问第t秒(x,y)上是否有球

solution

是个原!呜呜呜

原题是询问对于第k秒出现的球在第n条对角线上在哪一个点

把t,x,y和k,n的关系推出来,就是原题了

至于原题,其实是个思维题

对于一个点,如果有x个球经过它,那么它下面两个点分别会被经过x/2次和(x+1)/2次

因此可以递推得到整个图的每个点的球经过次数,最后模拟最后一个小球的下落过程即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;ll k;
ll dp[250][250];
int down(int x,int y)
{
	if(x+y==n-1)return y;
	if(dp[x][y]&1)return down(x+1,y);
	else return down(x,y+1);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int q;
	cin >> q;
	while(q--)
	{
		ll t;int x,y;
		cin >> t >> x >> y;
		n=x+y+1,k=t-n+2;
		if(k<=0)
		{
			cout<<"NO"<<endl;
			continue;
		}
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)
				dp[i][j]=0;
		dp[0][0]=k;
		for(int i=0;i<n;i++)
			for(int j=0;i+j<=n-1;j++)
			{
				dp[i+1][j]+=(dp[i][j]+1)/2;
				dp[i][j+1]+=dp[i][j]/2;
			}
		cout<< (down(0,0)==x?"YES":"NO") << endl;
	}
	return 0;
}