526互联

武汉理工大学第四届ACM校赛 部分题解

发布时间 2023-07-04 15:21:04作者: HikariFears

比赛地址

A.ST和TS回文问题

题意：给出一个字符串s，进行q次操作，操作如下：

1 x:给字符串的末尾加上一个字符x

2 k:查询是否存在长度为k的字符串t，满足s+t==t+s

Solution

字符串哈希

当k<n时，需检查s长度为k的前后缀是否相同，并且检查s长度为n-k的前后缀是否都是回文

当k==n时，一定有解

当k<2n时，需检查s长度为2n-k的前后缀是否相同，并且检查k-n的前后缀是否都是回文

当k==2n时，需检查s是否为回文串

当k>2n时，可以转化成k%(2n)的情况

debug半天，鉴定为：不咋会写哈希的飞舞（

ull h[N];
ull rh[N];
ull p[N+10];
ull b=13331;

void init()
{
	p[0]=1;
	for(int i=1;i<N;i++)
	{
		p[i]=p[i-1]*b;
	}
	
}



ull get_hash(int l,int r)
{
	if(l==0)return h[r];
	return h[r]-h[l-1]*p[r-l+1];
}

ull get_rhash(int l,int r)
{
	if(l==0)return rh[r];
	return rh[r]-rh[l-1]*p[r-l+1];
}


void solve()
{
	init();
	int n,q;cin>>n>>q;
	string s;cin>>s;
	
	vector<pii>v;
    
	while(q--)
	{
		int op;cin>>op;
		if(op==1)
		{
			char z;cin>>z;
			n++;
			s+=z;
		}else
		{
			int k;cin>>k;
			v.push_back({n,k%(2*n)});
		}
	}
	
	h[0]=(ull)(s[0]);
	for(int i=1;i<n;i++)
	{
		h[i]=(h[i-1]*b+(ull)(s[i]));
	}
	string rs=s;
	reverse(rs.begin(),rs.end());
	rh[0]=(ull)(rs[0]);
	for(int i=1;i<n;i++)
	{
		rh[i]=(rh[i-1]*b+(ull)(rs[i]));
	}
	

	
	for(auto it:v)
	{
		int len=it.first;
		int k=it.second;
		if(k==0)
		{
			if((get_hash(0,len-1)==get_rhash(n-len,n-1)))cout<<"Yes\n";
			else cout<<"No\n";
		}else if(k<len)
		{
			int flag1=get_hash(0,k-1)==get_hash(len-k,len-1);
			int flag2=get_hash(0,len-k-1)==get_rhash(n-(len-k),n-1);
			int flag3=get_hash(k,len-1)==get_rhash(n-len,n-k-1);
			if(flag1&&flag2&&flag3)cout<<"Yes\n";
			else cout<<"No\n";
		}else if(k==len)cout<<"Yes\n";
		else
		{
			int flag1=get_hash(0,2*len-k-1)==get_hash(k-len,len-1);
			int flag2=get_hash(0,k-len-1)==get_rhash(n-(k-len),n-1);
			int flag3=get_hash(2*len-k,len-1)==get_rhash(n-len,n-(2*len-k)-1);
			if(flag1&&flag2&&flag3)cout<<"Yes\n";
			else cout<<"No\n";
		}
	}
}

B.不降序列

题意：给一个不降序列，最多进行k次操作，每次操作可以将任意一个数删除或是修改成任意数字，要求操作后的序列仍然是不降序列

\[令res=\sum_{i=1}^{m-1}(a_{i+1}-a_{i})^{2} \]

求res的最大值

Solution

dp

假设最后的结果是一段一段的，例如原来的序列是123456789

删除一部分后变成了1**4**67*8，这样我们可以把他分成许多段

令dp[i][j]表示以第i个数为右端点的，且包含i一共有j个右端点的状态下，从1到i的res的最大值

那么有转移方程

\[dp[i][j]=max(dp[i][j],dp[t][j-1]+(a[i]-a[t])^{2}) \]

其中t的范围是1到i-1

void solve()
{
	int n,k;cin>>n>>k;
	memset(dp,-1,sizeof(dp));
	dp[1][1]=0;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=min(i,n-k);j++)
		{
			for(int t=1;t<=i-1;t++)
			{
				if(t>=j-1&&dp[t][j-1]!=-1)
				{
					dp[i][j]=max(dp[i][j],dp[t][j-1]+(a[i]-a[t])*(a[i]-a[t]));
				}
			}
		}
	}
	
	
	cout<<dp[n][n-k]<<"\n";
}

D.流水线作业

题意：一个食堂有k个套餐和m种食材，每个套餐需要一些对应的食材，每个厨师每秒钟可以准备1个食材（第1秒准备，第2秒的最开始食材数量才会增加），每种食材数量不超过厨师数，每个食材每秒仅能又一个厨师准备，最开始的食材数量等于厨师数，现在有一些顾客在某些秒的最开始点单，问最少需要多少位厨师。

Solution

二分+模拟

二分厨师数量然后按照题意看是否能满足顾客需求即可

vector<int>p[50005];
int a[N];
struct node
{
	int x,y;
	bool operator <(const node&t)const &{
		if(x!=t.x)return x<t.x;
		return y<t.y;
	}
}b[N];
vector<int>g[100005];
int m,k;
bool check(int x)
{
	for(int i=0;i<m;i++)a[i]=x;
	
	for(int i=1;i<=86400;i++)
	{
		for(int j=0;j<g[i].size();j++)
		{
			for(auto it:p[g[i][j]])
			{
				if(a[it]==0)return false;
				a[it]--;
			}
		}
		for(int j=0;j<m;j++)
		{
			b[j].x=a[j],b[j].y=j;
		}
		sort(b,b+m);
		for(int j=0;j<x;j++)if(b[j].x<x)a[b[j].y]++;
	}
	return true;
}


void solve()
{
	cin>>k>>m;
	for(int i=0;i<k;i++)
	{
		int cnt;cin>>cnt;
		for(int j=1;j<=cnt;j++)
		{
			int x;cin>>x;
			p[i].push_back(x);
		}
	}
	
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		int t,c;cin>>t>>c;
		g[t].push_back(c);
	}
	
	
	int l=1,r=m;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	if(!check(l))cout<<"You need to expand!\n";
	else cout<<l<<"\n";
}

E.copy

题意：略

Solution

纯模拟

void solve()
{
	int n;cin>>n;
	unordered_map<string,int>mp;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		mp[s]=i;
	}
	int q;cin>>q;
	cout<<q<<"\n";
	while(q--)
	{
		string s;cin>>s;
		int x=mp[s];
		for(auto &it:mp)
		{
			if(it.second<x)it.second++;
		}
		mp[s]=1;
		cout<<x<<"\n";
	}
}

F.三角形重心

题意：给出n个点，问是否存在两个不同的三角形（至少有一个点不重合），其重心坐标相同

重心坐标公式:

\[(\frac{(x_1+x_2+x_3)}3,\frac{(y_1+y_2+y_3)}3) \]

Solution

鸽巢原理，根据题目给的范围，重心最多有36000000个，所以我们在枚举的时候，一旦找到了重心相同的三角形，即可直接返回答案。

void solve()
{
	int n;cin>>n;
	map<pii,node>mp;
	for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			for(int k=j+1;k<=n;k++)
			{
				
				if(mp.count({x[i]+x[j]+x[k],y[i]+y[j]+y[k]}))
				{
					cout<<"YES\n";
					cout<<i<<" "<<j<<" "<<k<<"\n";
					node t=mp[{x[i]+x[j]+x[k],y[i]+y[j]+y[k]}];
					cout<<t.a<<" "<<t.b<<" "<<t.c<<"\n";
					return;
				}else
				{
					node t;
					t.a=i,t.b=j,t.c=k;
					mp[{x[i]+x[j]+x[k],y[i]+y[j]+y[k]}]=t;
				}
			}
		}
	}
	cout<<"NO\n";
}

H.小e的果树

题意：给出一个横轴，上面有n棵果树，第i颗果树在坐标上的距离是Xi，第i棵果树上有ci个果子，第i颗果树的第j个果子采摘所需时间为hi,j，问从0出发，在t时间内最多能摘多少个果子

Solution

枚举+贪心

枚举右端点，采摘花费时长最少的果子即可

void solve()
{
	int n,t;cin>>n>>t;
	for(int i=1;i<=n;i++)
	{
		cin>>e[i].x>>e[i].c;
		for(int j=1;j<=e[i].c;j++)
		{
			int x;cin>>x;
			e[i].h.push_back(x);
		}
	}
	sort(e+1,e+1+n,cmp);
	vector<int>g;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int tans=0;
		int res=t-e[i].x;
		for(auto it:e[i].h)g.push_back(it);
		sort(g.begin(),g.end());
		for(int i=0;i<g.size();i++)
		{
			if(res<g[i])break;
			res-=g[i];
			tans++;
		}
		ans=max(tans,ans);
		
	}
	cout<<ans<<"\n";
}

K.雇佣农民

题意：给出一个n，第i天白天最多可以雇i个农民，每天晚上有x个农民则会获得x块钱，构造一个雇佣序列，使得刚好获得n块钱的时间最短且雇佣农民数量最多

Solution

贪心

先不考虑刚好获得的情况，假设我们每天都雇最多的农民，由此得到的肯定是时间最少的天数，在这个情况下，我们再改变前面的策略，从而使得刚好获得n块钱

再就是考虑时间越早，人越多，我们考虑当前还剩tmp块未获得，那么要求越快获得，前面应该能有多少人就有多少人

void solve()
{
	int n;cin>>n;
	if(n==0)
	{
		cout<<"1\n0\n";
		return;
	}
	int t=0;
	int now=0;
	int res=0;
	while(res<n)
	{
        t++;
		a[t]=t;
		now+=t;
		res+=now;
	}
	int tmp=n;
	for(int i=1;i<=t;i++)
	{
		a[i]=min(a[i],tmp/(t-i+1));
		tmp-=a[i]*(t-i+1);
	}
	cout<<t<<"\n";
	for(int i=1;i<=t;i++)
	{
		cout<<a[i]<<" ";
	}
}