CF Edu 130 A-D vp 補題

數(shù)模也是終于結(jié)束了。開始恢復(fù)vp。今天這場vp發(fā)揮比上次好一些，三題rank3600+。A，B題做的很順利。C題標記沒弄全多WA了兩發(fā)。D題是個交互題，也是研究了一下。基本思路正確。

題目鏈接

A. Parkway Walk 貪心
題意：你依次要去n個地方。每個地方消耗$a_i$的能量。你最開始有m能量，你可以隨時停下來休息，可以恢復(fù)能量。只有能量大于等于當前地點所需能量才可以前進，詢問最小需要恢復(fù)的能量。
思路：直接一開始就休息攢夠不足的能量再出發(fā)即可。所以
$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$，現(xiàn)在商家推出一個活動，買x件物品，這x件物品中的前y個便宜的商品就可以免費（$x\ge y$）。對于每個x和y，求出最多有多少金額可以免費。
思路：貪心，為了能夠免費更多，那么我們只需要買最貴的x個物品，然后我們需要統(tǒng)計出這x個商品中前y個便宜的商品價格總和。
因為有q次詢問。所以我們可以用前綴和來解決。就可以先對p從大到小排序，然后求前綴和，那么對于每次詢問，我們要求的就是$[n?x+1,n?x+y]$這段區(qū)間的和。記得開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變?yōu)閠。操作1：將"ab"變?yōu)椤癰a”。操作2：將"bc"變?yōu)椤癱b”。
思路：一道亂搞題，做法很多，這里說一下我賽時的想法。賽時也想了比較久，后面沒找到什么結(jié)論，便開始一位一位討論。
首先對于該位$i$,如果$s[i]=t[i]$，就可以直接跳過。
其次如果$t[i]=$‘a(chǎn)’,那么如果s想變成t只有該位為‘a(chǎn)’的情況才可以，否則不符合情況。

如果$t[i]=$‘b’,那么除了s[i]該位也為‘b’的情況之外，還可以該位為’a’并且后面有連續(xù)的‘a(chǎn)’后接一個‘b’,例如aaab。那么就可以一直進行交換，把后面的‘b’換到這個地方。否則不符合情況。

如果$t[i]=$‘c’,那么除了s[i]該位也為‘c’的情況之外，還可以該位為’b’并且后面有連續(xù)的‘b’后接一個‘c’,例如bbbc。那么就可以一直進行交換，把后面的‘c’換到這個地方。否則不符合情況。

接著我們把這個步驟進行模擬維護即可。具體實現(xiàn)看代碼：
注意邊界情況

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 ”會告訴你區(qū)間l到r之間有多少的不重復(fù)的字母。
你最多可以詢問26次1,6000次詢問2。
最后猜出這個字符串并且輸出。
思路：交互題做的不多，賽時的想法是每次先詢問1-i區(qū)間不同字母個數(shù)，如果增加就直接詢問該位字母，否則就不斷縮小區(qū)間找到那個與該位字母相同得到位置。但是沒有想到二分優(yōu)化，超過了詢問限制。這題參考了t寶的解法，非常簡潔！qrz。

首先，我們需要維護一個b數(shù)組，$b[i]$表示當前字符串的第i位字母最后一次出現(xiàn)的下標。我們對b數(shù)組進行排序。然后我們要去尋找該位字母在之前字符串最后出現(xiàn)的位置。就可以用二分查詢。如果找到了，那么更新一下字符串，并且更新b數(shù)組的值。反之，沒有找到，那么直接詢問1即可，然后將該位置加入b數(shù)組。

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