Codeforces Round 822 (Div. 2)(D前缀和+贪心加血量)

本文主要是介绍Codeforces Round 822 (Div. 2)(D前缀和+贪心加血量)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A.选三条相邻的边遍历一次求最小值

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=1e9+7;
#define int long long
int n,m;
vector<int> g[N];
int a[N];
void solve()
{cin>>n;int res=2e18;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);for(int i=2;i<=n-1;i++){res=min(res,abs(a[i]-a[i-1]+abs(a[i]-a[i+1])));}cout<<res<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

B.手玩一下最后一层的每个点可以由哪些点转移过来，可以观察到直接涂两边是可以相等的

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=1e9+7;
#define int long long
int n,m;
vector<int> g[N];
int a[N];
int s[N];
int get(int l,int r){return s[r]-s[l-1];
}
int b[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){if(j==1||j==i) cout<<1<<" ";else cout<<0<<" ";}cout<<"\n";}
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

C.贪心，从小到大选数，能去掉就去掉

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=1e9+7;
#define int long long
int n,m;
vector<int> g[N];
int a[N];
void solve()
{int res=0;cin>>n;string s;cin>>s;s="?"+s;vector<bool> st(n+10);for(int i=1;i<=n;i++){for(int j=i;j<=n;j+=i){if(st[j]) continue;if(s[j]=='0'){st[j]=true;res+=i;}else break;}}cout<<res<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

D：

要么到0要么到n+1，所以枚举出去哪个口

然后就贪心，什么情况下去另一侧，当然是去另一侧能加血量，如果当前能加血量肯定优先加，再跑去当前要出的口子，所以预处理另一侧加血量的贡献和能加这个血量需要付出的条件即这个过程扣血量的最小值

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=1e9+7;
#define int long long
int n,m;
vector<int> g[N];
int a[N];
int s[N];
int get(int l,int r){return s[r]-s[l-1];
}
int b[N];
void solve()
{int k;cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];auto check=[&](){int sum=0,mn=0;vector<int> nxt;vector<int> need;for(int i=k+1;i<=n;i++){sum+=a[i];mn=min(mn,sum);if(sum>0){nxt.push_back(sum);need.push_back(mn);sum=0;mn=0;}}int cur=a[k];for(int i=k,j=0;i;i--){while(j<nxt.size()&&cur+need[j]>=0){cur+=nxt[j];j++;}if(cur+a[i-1]<0) return false;cur+=a[i-1];}return true;};if(check()){cout<<"YES\n";return ;}reverse(a+1,a+1+n);k=n-k+1;if(check()){cout<<"YES\n";return ;}cout<<"NO\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

这篇关于Codeforces Round 822 (Div. 2)(D前缀和+贪心加血量)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---