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