D.灵能传输##
神仙结论
把前缀和应用到极致,6
先考虑三个数a,b,c,
进行一次变换也就是a+b,-b,c+b
可见三个数之和不变,也就是s[3]不变
然后之前的s[1]+b,愿称之为s[2]
之前的s[2],因为b变成-b,再加上后来的第一个数也就是a+b,变成a,也就是s[1]
所以相当于前两个的前缀和交换
而相邻前缀和相减就是一个数,相当于数可以随意换,最后一个除外
方便起见,加上s[0]=0
排个序,按一定顺序排就好
`#include <bits/stdc++.h>
using namespace std;
define endl '\n'
define ll long long
int main()
{
ll t;
cin>>t;
while(t--) {
ll n;
cin>>n;
vector
for (int i = 1; i <= n; i++) {
cin >> pre[i];
pre[i] += pre[i - 1];
}
ll L = pre[0], R = pre.back();
if (L > R) swap(L, R);
sort(pre.begin(), pre.end());
int l = lower_bound(pre.begin(), pre.end(), L) - pre.begin();
int r = lower_bound(pre.begin() + l + 1, pre.end(), R) - pre.begin();
vector
vector
for (int i = l; i >= 0; i -= 2) {
ve.push_back(pre[i]);
vis[i] = 1;
}
for (int i = r; i <= n; i += 2) {
vr.push_back(pre[i]);
vis[i] = 1;
}
reverse(vr.begin(), vr.end());
for (int i = 0; i <= n; i++) {
if (!vis[i]) ve.push_back(pre[i]);
}
for (ll i: vr) ve.push_back(i);
ll ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, abs(ve[i] - ve[i + 1]));
}
cout << ans << endl;
}
return 0;
}`
E.后缀表达式##
赛时压根没多想,按中缀做,想得太少了以至于分也非常低,
数据结构栈小括号啥的都没想
总的来说就是可以任意加小括号的意思
一、 m=0 即 没有减号 那就正常相加
二、m != 0 统计负数的个数 ans
1, ans=0 即全是正数 那就取一个减号 (因为至少一个)
所以把最小的数减去
2. ans = n+m+1 即全是负数 那就取 n+m个减号 所以把最大的负数留下 (绝对值小)
其余的数全部变成相反数
3. 有正数也有负数
这种情况下 有几个负数就取几个减号 来把它们变成正数
所以答案是 所有绝对值相加
`#include <bits/stdc++.h>
using namespace std;
define endl '\n'
define ll long long
const int N=2e5+10;
ll a[N];
int main()
{
int n,m;
int ans=0;
ll sum=0,num=0;
cin>>n>>m;
for(int i=1;i<=n+m+1;i++){
cin>>a[i];
if(a[i]<0) ans++;
sum+=abs(a[i]);
num+=a[i];
}
if(m0) cout<<num<<endl;
else{
sort(a+1,a+m+n+2);
if(ans0) sum-=2a[1];
else if(ans==n+m+1) sum+=2a[n+m+1];
cout<<sum<<endl;
}
return 0;
}`
F.等差数列##
排序,计算出相邻数之间最小的差
用最大数去除,
注意差为0的情况,因为这个RE了
`#include <bits/stdc++.h>
using namespace std;
define ll long long
define endl '\n'
ll r[100005];
int main()
{
ll n;
cin>>n;
for(ll i=1;i<=n;i++){
cin>>r[i];
}
ll mi=1000000005;
sort(r+1,r+1+n);
for(ll i=2;i<=n;i++){
mi=min(mi,r[i]-r[i-1]);
}
if(mi==0) {
cout<<n<<endl;
return 0;
}
cout<<(r[n]-r[1])/mi+1;
return 0;
}`
H.完全二叉树的权值##
暴力枚举
还是函数,这次是对数函数
C++对数函数用法
`#include <bits/stdc++.h>
using namespace std;
define ll long long
define endl '\n'
int main()
{
ll n,tem;
cin>>n;
vector
for(int i=1;i<=n;i++){
cin>>tem;
sum[__lg(i)+1]+=tem;
}
ll mx=0;
for(int i=1;i<n;i++){
if(sum[i]>sum[mx]) mx=i;
}
cout<<mx<<endl;
return 0;
}`
完结撒花