首页 > 其他分享 >CSP17

CSP17

时间:2024-08-11 16:26:56浏览次数:14  
标签:int max long CSP17 mx dp define

请注意:题目背景与题目可能没有关系
image
第一题,性质题,找到序列的最大值与最小值,我们发现如果只有正数的话和只有负数的话都很好处理,正数正序处理类似前缀加,负数后缀加,那如果正负都有,该怎么办呢?其实我们可以吧序列全变为正的或负的吧,但是需要比较一下最大值最小值,如果都变成正的话,对被卡掉,例如1 1 1 1 1 1 1 1 -1e9就死了

点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define ull unsigned long long
#define pii pair<int,int>
#define lid (rt<<1)
#define rid (rt<<1|1)
#define pii pair<int,int>
using namespace std;
const int N = 1e5+5;
ll n,a[N],b[N];int cnt;
vector <pii> put;
void zh(int l,int r)
{
	for(int i=l;i<r;i++)
	{
		if(a[i]<=a[i+1])continue;
		a[i+1]+=a[i];
		put.pb({i,i+1});
		cnt++;
	}
}
void fu(int l,int r)
{
	for(int i=r;i>l;i--)
	{
		if(a[i]>=a[i-1])continue;
		a[i-1]+=a[i];
		put.pb({i,i-1});
		cnt++;			
	}
}
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];b[i]=a[i];
	}
	sort(b+1,b+1+n);
	if(b[1]>=0)
	{
		zh(1,n);
		cout<<cnt<<endl;
		for(auto [l,r]:put)
		{
			cout<<l<<" "<<r<<endl;
		}
	}else
	{
		if(b[n]<=0)
		{
			fu(1,n);
			cout<<cnt<<endl;
			for(auto [l,r]:put)
			{
				cout<<l<<" "<<r<<endl;
			}
		}
		else
		{
			ll mx=b[n],pos=max_element(a+1,a+1+n)-a;
			ll mi=b[1],pp=min_element(a+1,a+1+n)-a;
			if(mx>-mi)
			{
				for(int i=n;i;i--)
				{
					int st=i;
					while(a[st]<=0&&st>0)
					{
						a[st]+=mx;
						put.pb({pos,st});
						if(mx<a[st])
						{
							mx=a[st];
							pos=st;
						}
						cnt++;
						st--;
					}
				}
				// for(int i=1;i<=n;i++)cout<<a[i]<<" ";
				zh(1,n);
				// for(int i=1;i<=n;i++)cout<<a[i]<<" "
				cout<<cnt<<endl;
				for(auto [l,r]:put)
				{
					cout<<l<<" "<<r<<endl;
				}				
			}else
			{
				for(int i=n;i;i--)
				{
					int st=i;
					while(a[st]>=0&&st>0)
					{
						a[st]+=mi;
						put.pb({pp,st});
						if(mi>a[st])
						{
							mi=a[st];
							pp=st;
						}
						cnt++;
						st--;
					}
				}
				// for(int i=1;i<=n;i++)cout<<a[i]<<" ";
				fu(1,n);
				// for(int i=1;i<=n;i++)cout<<a[i]<<" "
				cout<<cnt<<endl;
				for(auto [l,r]:put)
				{
					cout<<l<<" "<<r<<endl;
				}			
			}

		}
	}
	// for(int i=1;i<n;i++)
	// {
	// 	if(a[i]>a[i+1])
	// 	{
	// 		cout<<i<<" "<<a[i]<<" "<<a[i+1]<<endl;
	// 		cout<<"Wa"<<endl;
	// 		return 0;
	// 	}
	// }
	return 0;
}

image
这题,如果直接用暴力矩阵乘法的话是\(O(n^3)\),显然过不了,但我们可以发现一个性质,就是我们可以随机一个\(n\times 1\)矩阵,值得注意的是矩阵不满足交换律,但是\(randP \times A\times B \equiv randP\times C\)矩阵由\(n^2\)转换为\(n\)
这样我们就转换为\(O(n^2)\)的复杂度了

点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define ull unsigned long long
#define pii pair<int,int>
#define lid (rt<<1)
#define rid (rt<<1|1)
using namespace std;
const ll mod=998244353;
ll n;
mt19937 seed(random_device{}());
int rand(int l,int r)
{
	uniform_int_distribution<int>range(l,r);
	return range(seed);
}
struct Matrix
{
	vector <vector<ll>> a;
	int n,m;
	Matrix(int _n,int _m):n(_n),m(_m)
	{
		a.resize(n+1,vector<ll>(m+1));
	}
	void resize(int n,int m)
	{
		a.resize(n+1,vector<ll>(m+1));
	}
	Matrix operator * (const Matrix& A)const
	{
		Matrix ans(n,1);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=A.m;j++)
				for(int k=1;k<=m;k++)
					ans.a[i][j]=(ll)(ans.a[i][j]+(ll)a[i][k]*A.a[k][j]*1ll%mod)%mod;
		return ans;
	}
	void T()
	{
		cout<<"******"<<endl;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
				cout<<a[i][j]<<" ";
			cout<<endl;
		}
			
	}
};
int main()
{
	speed();
	// freopen("sequence2.in","r",stdin);
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		Matrix A(n,n),B(n,n),C(n,n),b(n,1);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)cin>>A.a[i][j];
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)cin>>B.a[i][j];
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)cin>>C.a[i][j];
		for(int i=1;i<=n;i++)
			b.a[i][1]=rand(1,16);
		// b.T();
		C=C*b;
		// C.T();
		b=B*b;//这里注意啊,为什么这么写A*(B*b)=C*b
		// b.T();
		b=A*b;
		// b.T();
		bool f=1;
		for(int i=1;i<=n;i++)
		{
			if(!f)break;
			for(int j=1;j<=1;j++)
			{
				if(b.a[i][j]!=C.a[i][j])
				{
					f=0;break;
				}
			}
		}
		if(f)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;

	}
	return 0;
}

image

这题暴力分就是二维背包,考场上这都能写挂,挂了35分

点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define ull unsigned long long
#define pii pair<int,int>
#define lid (rt<<1)
#define rid (rt<<1|1)
using namespace std;
const int N = 1e4+5;
short n,A,B;short dp[N][N];
struct ac
{
	short a,b;
}q[N];
int ans;
bool vis[N];
void dfs(int a,int b,int cnt)
{
	if(a>A||b>B)
	{
		ans=max(ans,cnt);
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i])continue;
		vis[i]=1;
		dfs(a+q[i].a,b+q[i].b,cnt+1);
		vis[i]=0;
	}	
}
int main()
{
	speed();
	// freopen("construct2.in","r",stdin);
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n>>A>>B;
	short mx=0;
	for(int i=1;i<=n;i++)
	{
		cin>>q[i].a>>q[i].b;
		mx=max(q[i].a,mx);
		mx=max(q[i].b,mx);
	}
	mx=max(mx,A);mx=max(mx,B);
	// dfs(0,0,0);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=mx;j>=q[i].a;j--)
		{
			for(int k=mx;k>=q[i].b;k--)
			{
				// if(j>=A&&j-q[i].a>=A)continue;
				// if(k>=B&&k-q[i].b>=B)continue;
				dp[j][k]=max<short>(dp[j][k],dp[j-q[i].a][k-q[i].b]+1);
				// if(j>=A&&j-q[i].a>=A)continue;
				// if(k>=B&&k-q[i].b>=B)continue;
				ans=max<short>(ans,dp[j][k]);
				// cout<<j<<" "<<k<<" "<<dp[j][k]<<endl;
			}
		}
	}
	// for(int i=0;i<=mx;i++)ans=max(ans,dp[A][i]);
	// for(int i=0;i<=mx;i++)ans=max(ans,dp[i][B]);
	cout<<dp[A][B]+(dp[A][B]!=n)<<endl;
	return 0;
}

正解
考虑到\(O(nV^2)\)中\(V\)太大了,我们可以换一种枚举方式,换成\(f_{i,j,k}\)枚举前\(i\)人中选了\(j\)个人,\(A\)值为多少,复杂度为\(O(n^2V)\)这样就可以过了

点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define ull unsigned long long
#define pii pair<int,int>
#define lid (rt<<1)
#define rid (rt<<1|1)
using namespace std;
const int N = 1e4+5;
int n,A,B,dp[2][85][N];
struct ac
{
	int a,b;
}q[N];
bool cmp(ac a,ac b)
{
	return a.b<b.b;
}
int ans;
bool vis[N];

int main()
{
	speed();
	// freopen("construct2.in","r",stdin);
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n>>A>>B;
	int mx=0;
	for(int i=1;i<=n;i++)
	{
		cin>>q[i].a>>q[i].b;
		mx=max(q[i].a,mx);
		mx=max(q[i].b,mx);
	}
	mx=max(mx,A);mx=max(mx,B);
	memset(dp,0x3f,sizeof dp);
	dp[0][0][0]=0;;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=i;j++)
		{
			for(int v=A;v>=0;v--)
			{

				dp[i&1][j][v]=dp[(i-1)&1][j][v];
				if(j>=1&&v>=q[i].a)dp[i&1][j][v]=min(dp[i&1][j][v],dp[(i-1)&1][j-1][v-q[i].a]+q[i].b);
				// cout<<dp[i][j][v]<<endl;
				
			}
		}
	}
	for(int j=1;j<=n;j++)
		for(int v=A;v>=0;v--)
			if(dp[n&1][j][v]<=B)ans=max(ans,j);
	cout<<min(ans+1,n)<<endl;
	return 0;
}

标签:int,max,long,CSP17,mx,dp,define
From: https://www.cnblogs.com/wlesq/p/18352402

相关文章