CF Edu 130 A-D vp 补题

CF Edu 130 A-D vp 补题

数模也是终于结束了。开始恢复vp。今天这场vp发挥比上次好一些，三题rank3600+。A，B题做的很顺利。C题标记没弄全多WA了两发。D题是个交互题，也是研究了一下。基本思路正确。

题目链接

A. Parkway Walk 贪心
题意：你依次要去n个地方。每个地方消耗$a_i$的能量。你最开始有m能量，你可以随时停下来休息，可以恢复能量。只有能量大于等于当前地点所需能量才可以前进，询问最小需要恢复的能量。
思路：直接一开始就休息攒够不足的能量再出发即可。所以
$ans=min(sum-m,0)$

void Showball(){int n,m;cin>>n>>m;vector<int> a(n);int sum=0;for(auto &x:a) cin>>x,sum+=x;cout<<max(sum-m,0)<<endl;
}

B. Promo 前缀和+贪心
题意：有n件商品，每件商品的价格为$p_i$，现在商家推出一个活动，买x件物品，这x件物品中的前y个便宜的商品就可以免费（$x\ge y$）。对于每个x和y，求出最多有多少金额可以免费。
思路：贪心，为了能够免费更多，那么我们只需要买最贵的x个物品，然后我们需要统计出这x个商品中前y个便宜的商品价格总和。
因为有q次询问。所以我们可以用前缀和来解决。就可以先对p从大到小排序，然后求前缀和，那么对于每次询问，我们要求的就是$[n-x+1,n-x+y]$这段区间的和。记得开long long，否则会溢出。

void Showball(){LL n,q;cin>>n>>q;vector<LL> a(n+1),s(n+1);for(int i=1;i<=n;i++) cin>>a[i];sort(a.begin()+1,a.end());for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];while(q--){LL x,y;cin>>x>>y;cout<<s[n-x+y]-s[n-x]<<endl;}
}

C. awoo’s Favorite Problem字符串
题意：给你两个长度为n且只含’a’,‘b’,'c’的字符串s和t。问你能否通过以下操作将s变为t。操作1：将"ab"变为“ba”。操作2：将"bc"变为“cb”。
思路：一道乱搞题，做法很多，这里说一下我赛时的想法。赛时也想了比较久，后面没找到什么结论，便开始一位一位讨论。
首先对于该位$i$,如果$s[i]=t[i]$，就可以直接跳过。
其次如果$t[i]=$‘a’,那么如果s想变成t只有该位为‘a’的情况才可以，否则不符合情况。

如果$t[i]=$‘b’,那么除了s[i]该位也为‘b’的情况之外，还可以该位为’a’并且后面有连续的‘a’后接一个‘b’,例如aaab。那么就可以一直进行交换，把后面的‘b’换到这个地方。否则不符合情况。

如果$t[i]=$‘c’,那么除了s[i]该位也为‘c’的情况之外，还可以该位为’b’并且后面有连续的‘b’后接一个‘c’,例如bbbc。那么就可以一直进行交换，把后面的‘c’换到这个地方。否则不符合情况。

接着我们把这个步骤进行模拟维护即可。具体实现看代码：
注意边界情况

void Showball(){int n;cin>>n;string s,t;cin>>s>>t;if(s==t) {cout<<"YES"<<endl;return;}s="?"+s+"?";t="?"+t+"?";bool flg=true;for(int i=1;i<=n;i++){if(s[i]==t[i]) continue;if(t[i]=='a') {flg=false;break;} else if(t[i]=='b') {if(s[i]=='a') {int j=i+1;while(j<=n&&s[j]=='a') j++;if(s[j]=='b') swap(s[i],s[j]);else {flg=false;break;} }else {flg=false;break;} }else{if(s[i]=='b') {int j=i+1;while(j<=n&&s[j]=='b') j++;if(s[j]=='c') swap(s[i],s[j]);else {flg=false;break;} }else {flg=false;break;} }}if(flg) cout<<"YES"<<endl;else cout<<"NO"<<endl;
}

D. Guess The String 交互+二分
题意：告诉你一个只含小写字母字符串的长度，你可以进行提问。
1.“？1 i ”会告诉你第i个字符是什么。
2.“？ 2 l r ”会告诉你区间l到r之间有多少的不重复的字母。
你最多可以询问26次1,6000次询问2。
最后猜出这个字符串并且输出。
思路：交互题做的不多，赛时的想法是每次先询问1-i区间不同字母个数，如果增加就直接询问该位字母，否则就不断缩小区间找到那个与该位字母相同得到位置。但是没有想到二分优化，超过了询问限制。这题参考了t宝的解法，非常简洁！qrz。

首先，我们需要维护一个b数组，$b[i]$表示当前字符串的第i位字母最后一次出现的下标。我们对b数组进行排序。然后我们要去寻找该位字母在之前字符串最后出现的位置。就可以用二分查询。如果找到了，那么更新一下字符串，并且更新b数组的值。反之，没有找到，那么直接询问1即可，然后将该位置加入b数组。

void Showball(){int n;cin>>n;string s="";auto ask1=[&](int x){cout<<"? 1 "<<x+1<<endl;char res;cin>>res;return res;};auto ask2=[&](int l,int r){cout<<"? 2 "<<l+1<<" "<<r+1<<endl;int res;cin>>res;return res;};vector<int> b;for(int i=0;i<n;i++){sort(b.begin(),b.end());int l=-1,r=(int)b.size()-1;while(l<r){int mid=(l+r+1)>>1;if(ask2(b[mid],i)==(int)b.size()-mid) {l=mid;}else {r=mid-1;}}if(l==-1){s+=ask1(i);b.push_back(i);}else{s+=s[b[l]];b[l]=i;}}cout<<"! "<<s<<endl;
}