B.Black Cells
题目:
思路:
首先我们发现要分奇偶讨论。
- 偶数:很简单,取a[2]-a[1],a[4]-a[3],.........a[n]-[n-1]的最大值。
- 奇数:我只需要知道假如删除当前的这个数剩下的数最大的间隔值,注意只能删除1,3,等奇数位,因为要保证删除后左右的数为偶数。(我的代码里面是偶数位因为我的索引从0开始)
代码:
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve(){
ll n;cin>>n;
vector<ll> a(n);
for(ll i=0;i<n;i++)cin>>a[i];
ll ans=0x3f3f3f3f3f3f3f3f;
if(n%2){
for(ll i=0;i<n;i+=2){
ll t=1;
for(ll j=i-1;j>0;j-=2){
t=max(t,a[j]-a[j-1]);
}
for(ll j=i+1;j+1<n;j+=2){
t=max(t,a[j+1]-a[j]);
}
ans=min(ans,t);
}
}else{
ans=0;
for(ll i=1;i<n;i+=2){
ans=max(a[i]-a[i-1],ans);
}
}
cout<<ans<<endl;
return;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll _;cin>>_;
while(_--)solve();
return 0;
}C.Action Figures
题目:
思路:
通过题目我们可以知道只有当s[i]=='1'时我们才能购买。所以我们就要考虑当s[i]=='1'时我们怎样买最优。然后可以发现我们如果前面由0的话我们尽量先把为0的人偶购买了,因为对于s[i]=='1'的最优处理法是买一个前面的让他变成免费的,所以如果前面有0我们尽量买0的人偶,如果没有的话才考虑买1。
代码:
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve(){
ll n;cin>>n;
string s;cin>>s;
s='*'+s;
ll ans=0;
stack<ll> stk0;
stack<ll> stk1;
for(ll i=1;i<=n;i++){
if(s[i]=='0'){
stk0.push(i);
}
}
for(ll i=n;i>=1;i--){
if(s[i]=='1'){
while(stk0.size()&&stk0.top()>i){
ans+=stk0.top();
stk0.pop();
}
if(stk0.size()){
ans+=stk0.top();
stk0.pop();
}else{
stk1.push(i);
}
}
}
ll t=stk1.size()+1;
for(ll i=1;i<=t/2;i++){
ans+=stk1.top();
stk1.pop();
}
while(stk0.size()){
ans+=stk0.top();
stk0.pop();
}
cout<<ans<<endl;
return;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll _;cin>>_;
while(_--)solve();
return 0;
}D.Sums of Segments
题目:
思路:
就写一下每一项然后观察,然后建各种数组就行了。这里为了防止超时要用一个二分。
代码:
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve(){
ll n;cin>>n;
vector<ll> a(n+1);
for(ll i=1;i<=n;i++)cin>>a[i];
vector<ll> b(n+1);
vector<ll> pre(n+1);
for(ll i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
ll sm=0;
for(ll i=1;i<=n;i++)sm+=pre[i];
for(ll i=1;i<=n;i++){
b[i]=sm;
sm-=(n-i+1)*a[i];
}
for(ll i=1;i<=n;i++){
b[i]+=b[i-1];
}
vector<ll> a2(n+1);
for(ll i=1;i<=n;i++){
a2[i]=a[i]*(n-i+1);
}
for(ll i=1;i<=n;i++)a2[i]+=a2[i-1];
for(ll i=1;i<=n;i++)pre[i]+=pre[i-1];//对pre求第二次前缀
ll q;cin>>q;
for(ll i=1;i<=n;i++)a[i]+=a[i-1];
auto pos=[&](ll x)->ll{
return x*n-x*(x-1)/2;
};
auto f1=[&](ll idx)->ll{
ll l,r;
l=0,r=n;
ll res=0;
ll cnt=0;
while(l<=r){
ll mid=(l+r)/2;
if(pos(mid)<=idx){
cnt=mid;
l=mid+1;
}else{
r=mid-1;
}
}
res=b[cnt];
if(idx>pos(cnt)){
ll en=idx-pos(cnt)+cnt;
res+=pre[en]-a2[cnt]+a[cnt]*(n-en);
}
return res;
};
while(q--){
ll t1,t2;cin>>t1>>t2;
cout<<f1(t2)-f1(t1-1)<<endl;
}
return;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
solve();
return 0;
}
/
/// //
/
/ . . ///
/ ///
// ---
//
/
/
////好困!课好多
标签：Educational,Rated,ll,Codeforces,long,cin,stk0,while,cnt From： https://blog.csdn.net/2301_77680189/article/details/143358090