首页 > 其他分享 >武汉理工大学第四届ACM校赛 部分题解

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

时间：2023-07-04 15:25:14浏览次数：54  
标签：题意 int 题解 void cin ACM Solution 武汉理工大学 dp

比赛地址

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]<<" ";
	}
}

标签：题意,int,题解,void,cin,ACM,Solution,武汉理工大学,dp
From： https://www.cnblogs.com/HikariFears/p/17525833.html

相关文章

  • 洛谷CF29B题解
    CF29B交通信号灯传送门题目很好理解，这里就不多说了，思路都在代码里#include<bits/stdc++.h>usingnamespacestd;doublel,d,v,g,r;intmain(){ cout<<fixed<<setprecision(8);//重置输出方式（保留8位小数） cin>>l>>d>>v>>g>>r; if(l<=d)cout<<......
  • 2023ACM暑假训练day 8-9 线段树
    目录DAY8-9线段树训练情况简介题DAY8-9线段树训练地址：传送门训练情况简介题题意：思路：......
  • P9431 [NAPC-#1] Stage3 - JRefreshers 题解
    传送门这个人赛时看错了几次题目导致样例调了1h。\(Sol1:n\leqslant10,T\leqslant10\)乱搞分。枚举跳跃的顺序，判断可不可行，最后取最大值，复杂度\(O((n-1)!)\)。\(Sol2:B\)感觉跟正解没什么关系，先说这个。特殊性质\(\mathbfB\)：保证对于任意跳跃球\(u,v\)，如......
  • [LOJ 6029]「雅礼集训 2017 Day1」市场 题解
    这道题恶心之处在于区间向下取整。这里给出两种思路：区间覆盖做法如果最大值和最小值向下取整后相等，则对此区间进行区间覆盖。我考场写的是这个，但是码错了，加上习惯不好,\(100\to64\),再加上烦了弱智错误，\(64\to9\)，不给出代码。差值相等做法注意到相邻两数的向下取整的差值不......
  • [LOJ 6030]「雅礼集训 2017 Day1」矩阵 题解
    首先不难想到一个贪心，就是先填出一个全黑的行，然后再用其填黑列。而且在其中“填出一个全黑的行步数”我们应该最小化。这个贪心的正确性证明如下：必要性：填黑列的必要条件为有一个全黑的行。充分性：“填黑列的步数”就是“非全黑列的数量”。显然，如果填出一个全黑的行的过程中......
  • Property ‘sqlSessionFactory‘ or ‘sqlSessionTemplate‘ are required 问题解决
    以下是报错日志解决方案确认以下配置是否都存在：1、配置文件有写mybatis配置2、启动类里加上Mapper扫描的注解（指向自己mapper存放的位置）3、删除SpringBootApplication注解的exclude属性:@SpringBootApplication(exclude={DataSourceAutoConfiguration.class,DataSourc......
  • P2202 题解
    前言题目传送门！更好的阅读体验？提供一个平衡树做法，虽然和std::set一个道理就是了。（那你为啥不写set！！！！）前置知识如何判断两个点对应的正方形相交？正方形的边长是\(k\)，中心距离四条边就是\(\dfrack2\)了。中心要相隔严格小于两段\(\dfrack2\)，显然只需满足：\[|X_p-X_q|,|Y_......
  • 【CF1621G】Weighted Increasing Subsequences 题解（优化树状数组）
    CF传送门|LG传送门。优化树状数组+反向处理。Solution发现直接做不好下手。难点主要在求出所有的上升子序列并计算它们分别的贡献。所以需要反向考虑每个单点在什么情况下产生贡献。一个单点会产生多少贡献。一个单点产生贡献的条件很容易得到。一个是在一个上升子序......
  • 2023ACM暑假训练day 7-RMQ问题
    目录DAY7RMQ问题训练情况简介题DAY7RMQ问题训练地址：传送门训练情况简介2023-07-03星期一早上：下午：晚上：题题意：思路：......
  • 题解 ARC163C【Harmonic Mean】
    没想出来什么优美的解法，来个乱搞。特判平凡情况\(n\le2\)，其中\(n=1\)显然有\(1=\frac{1}{1}\)，\(n=2\)无解。众所周知\(1=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots+\frac{1}{2^k}+\frac{1}{2^k}\)。注意到公式中除了\(\frac{1}{2^k}\)有重复外，其余项均无重复。容易......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99