codeforce round 753 div3 题解报告

在vp比赛的时候只过了5题，后三题跨度还是挺大，不过也有前五题写的慢的愿意在里面，没有太多时间看后面的题。

A. Linear Keyboard

给你一个键盘的顺序，让你模拟打某个单词需要的步数，稍微对应建立映射即可

#include<bits/stdc++.h>
using namespace std;
int t,n;
map<char,int>mp;
int main()
{
	string s1,s2;
	scanf("%d",&t);
	while(t--)
	{
		mp.clear();
		scanf("%d",&n);
		cin>>s1>>s2;
		for(int i=1;i<=26;i++)
		{
			mp[s1[i]]=i;
		}
		int ans=0;
		for(int i=1;i<s2.size();i++)
		{
			
			ans+=abs(mp[s2[i]]-mp[s2[i-1]]);
			
		}
		cout<<ans<<endl;
	}
	return 0;
}

B.Odd Grasshopper

题意是给你一个初始位置，和蚂蚱跳的次数，问最终会停留在哪里，不难发现 无论起点的奇偶性，中间两次方向都和第一次和最后一次相反，所以没四次都会回到原地。然后就%4，观察一下性质即可，这里我写复杂了。

#include<bits/stdc++.h>
using namespace std;
long long int t,x,n;
int main()
{
	cin>>t;
	while(t--)
	{
		long long int ans=0;
		cin>>x>>n;
		ans+=x;
		if(x%2==0)
		{
			if(n%4==0)
			{
				ans+=0;
			}
			if(n%4==1)
			{
				ans-=n;
			}
			if(n%4==2)
			{
				ans+=1;
			}
			if(n%4==3)
			{
				ans+=(n+1);
			}
		}
		else
		{
			if(n%4==0)
			{
				ans+=0;
			}
			if(n%4==1)
			{
				ans+=n;
			}
			if(n%4==2)
			{
				ans-=1;
			}
			if(n%4==3)
			{
				ans-=(n+1);
			}
		}
		cout<<ans<<endl;
	}
	
	return 0;
}

C.Minimum Extraction

题意自己看吧，做法就是排个序，然后找最大的差值，正确性是因为，每个最小的消失的代价就是其他同时-某个数，不影响相对关系，那么我们删到差值最大的以后停止，留下的最小值就是题目要求的最大值。关键在于排完序后，相对位置不可能发生变化，所以只需要考虑在哪里停止即可。可以留下的最大的数就是差值。那么实质上留下的值的大小就是也可以模拟这个过程。

#include<bits/stdc++.h>
using namespace std;
int t,n;
int a[200010],b[200010];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		sort(a+1,a+1+n);
		int ans=a[1];
			for(int i=1;i<n;i++)
				ans=max(ans,a[i+1]-a[i]);
		cout<<ans<<endl;	
	}
	return 0;
}

D.Blue-Red Permutation

根据性质，可知蓝的一定严格小于红色，排个序，代表的是他们分别能负责的区间，然后依次判断是否合法即可。

#include<bits/stdc++.h>
using namespace std;
int t,n;
int a[200010],red[200010],blue[200010];
int main()
{
	string s;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		cin>>s;
		int cnt1=0,cnt2=0;
		for(int i=1;i<=n;i++)
		{
			if(s[i-1]=='B')
				blue[++cnt1]=a[i];
			else 
				red[++cnt2]=a[i];
		}
		sort(blue+1,blue+1+cnt1);
		sort(red+1,red+1+cnt2);
		int flag=0;
		for(int i=1;i<=cnt1;i++)
		{
			if(blue[i]<i){
				flag=1;
			}
		}
		for(int i=1;i<=cnt2;i++)
		{
			if(red[i]>cnt1+i)flag=1;
		}
		if(flag==0)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

E.Robot on the Board 1

给你机器人，告诉你应该咋走，然后问从哪出发能走最多，我们只需要从头维护最左最右最上最下可能到达的位置，不得不出届时，根据记录的值在中间找平衡。有一点边界需要处理。浪费了不少时间

#include<bits/stdc++.h>
using namespace std;
int t,x,y;
string s;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&y,&x);
		cin>>s;
		int cnt1=0,cnt2=0,mxl=0,mxr=0,mxu=0,mxd=0,tmpx=0,tmpy=0;
		int len=s.size();
		int flag=0;
		for(int i=0;i<len;i++)
		{
			if(s[i]=='R')cnt1++;
			if(s[i]=='L')cnt1--;
			if(s[i]=='U')cnt2--;
			if(s[i]=='D')cnt2++;
			mxl=max(mxl,-cnt1);
			mxr=max(mxr,cnt1);
			mxu=max(mxu,-cnt2);
			mxd=max(mxd,cnt2);
			if(mxl+mxr>=x)
			{
				if(s[i]=='R')
				cout<<mxu+1<<" "<<mxl+1<<endl;
				else cout<<mxu+1<<" "<<mxl<<endl;
				flag=1;
				break;
			}
			if(mxu+mxd>=y)
			{
				if(s[i]=='U')
				cout<<mxu<<" "<<mxl+1<<endl;
				else cout<<mxu+1<<" "<<mxl+1<<endl;
				flag=1;
				break;
			}
		}
		if(flag==0)cout<<mxu+1<<" "<<mxl+1<<endl;
	}
	return 0;
}

F.Robot on the Board 2

改成了规定了每个格子的走法，成环或出界后停止，问从哪个点出发走的最多，最多走几步。其实就暴力搜索一下。然后每次记录下路径。成环后按顺序倒回去把这些环的值也修改成相同的值。可以递归处理，也可以用栈记录状态来做。

这题的一个教训是c++20比17慢，还卡内存。而且递归里加else 好像比不加else 要快。我也不清楚为啥。

这里的代码实现时参考别人的

#include<bits/stdc++.h>
using namespace std;
int t,n,m,cnt,x,y,ans;
char a[2010][2010];
int dis[2010][2010],vis[2010][2010];
vector<pair<int,int>>path;
int dfs(int x,int y)
{
	path.push_back({x,y});
	if(x<1||x>n||y<1||y>m||vis[x][y])
	{
		return dis[x][y];
	}
	vis[x][y]=1;
	if(a[x][y]=='U')dis[x][y]=dfs(x-1,y)+1;
	else if(a[x][y]=='D')dis[x][y]=dfs(x+1,y)+1;
	else if(a[x][y]=='L')dis[x][y]=dfs(x,y-1)+1;
	else if(a[x][y]=='R')dis[x][y]=dfs(x,y+1)+1;
	return dis[x][y];
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		scanf("%s",a[i]+1);
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(!vis[i][j])
			{
				path.clear();
				path.push_back({0,0});
				dfs(i,j);
				cnt=path.size();
				for(int i=1;i<cnt-1;i++)
				{
					if(path[i]==path[cnt-1])
					{
						for(int j=i;j<cnt;j++)
						dis[path[j].first][path[j].second]=cnt-i-1;
					}
				}
			}
		}
		ans=0;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(dis[i][j]>ans)
			{
				x=i,y=j;
				ans=dis[i][j];
			}
			vis[i][j]=0;
			dis[i][j]=0;
		}
		printf("%d %d %d\n",x,y,ans);
	}
	return 0;
}

G.Banquet Preparations 1

给你一堆菜，分别有a和b两个值，对于每个菜，我们一共可以吃m。问最后两菜差的绝对值最小值是什么。贪心就好了，先算出两个菜可能的最大差值。之后在慢慢补回去，补的时候，注意几个值min(tmp,min(c[i],b[i]-d[i]))；

tmp值得是当前差值的一半，超过了之后没有意义，C[I]指的是a被吃了多少，不能反哺更多的值，B[I]-D[I]是b还能被吃多少，这三个都不能超过。按顺序贪心即可。

#include<bits/stdc++.h>
using namespace std;
long long t,n,m,x,y;
long long  a[200010],b[200010],c[200010],d[200010],sum;
int main()
{
	cin.tie(0);
	scanf("%lld",&t);
	while(t--)
	{
		sum=0;
		scanf("%lld%lld",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld %lld",&a[i],&b[i]);
			x=max(a[i]-m,0ll);
			y=min(b[i],b[i]-(m-a[i]));
			sum+=x-y;
			c[i]=min(a[i],m);
			d[i]=m-c[i];
			 
		}
		for(int i=1;i<=n;i++)
		{
			long long int tmp=-sum/2;
			if(tmp<=0)continue;
			long long int x=min(tmp,min(c[i],b[i]-d[i]));//b[i]还有多少可以吃掉的
			sum+=x*2;
			c[i]-=x;
			d[i]+=x;
		}
		cout<<abs(sum)<<endl;
		for(int i=1;i<=n;i++)
		cout<<c[i]<<" "<<d[i]<<endl;
	}
	return 0;
}

H.Banquet Preparations 2

题意类似，不过每个菜都有自己对应的m值了，目的是让不同种类的菜数量更少。那么首先可以发现，a[i]+b[i]-m[i]的值必须相同才有可能相同，先按这个关键词排序。继续观察。可以发现当A[I]固定之后b也会固定，所以我们不需要同时考虑这些问题。那么也就是说我们可以把a的值的可能区间范围求出来，问题就转化成了一个经典的模型。给你一堆区间。用最少的线覆盖所有区间的问题。对于这个问题，我们可以简单的贪心解决。有一些边界问题需要注意。贪心原则是按区间R排序。每次假设线都设在最右边，下一个的左边如果在线左边就不管。否则更新最右的线的位置。注意排序后会乱序。需要通过id来标记每个菜对于的位置。这个经典问题也不止这一种方法可以解决，有兴趣可以继续探索。

#include<bits/stdc++.h>
using namespace std;
int t,n,ans,tmp;
int a[200010],b[200010],m[200010],ans1[200010];
struct node{
	int val,l,r,an,id;
	bool operator <(const node x)const{
		return val==x.val?r<x.r:val<x.val;
	}
}x[200010];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d",&a[i],&b[i],&m[i]);
			x[i].val=a[i]+b[i]-m[i];
			x[i].l=max(0,a[i]-m[i]);
			x[i].r=a[i]+min(0,b[i]-m[i]);
			x[i].id=i;
		}
		sort(x+1,x+1+n);
		tmp=x[1].r;ans=1;
		ans1[x[1].id]=a[x[1].id]-tmp;
		for(int i=2;i<=n;i++)
		{
			if(x[i].val!=x[i-1].val||tmp<x[i].l){
				ans++;
				tmp=x[i].r;
			}
			ans1[x[i].id]=a[x[i].id]-tmp;
		}
		printf("%d\n",ans);
		for(int i=1;i<=n;i++)
		printf("%d %d\n",ans1[i],m[i]-ans1[i]);
	}
	return 0;
}