洛谷刷题8.2

P4086 [USACO17DEC] My Cow Ate My Homework S - 洛谷

 这里用简单的后缀和+后缀的最小值数组。注意每次要去掉最小值，平均分是除以（后缀数组长度-1）

#include<bits/stdc++.h>
#define ll long long
#define samplepassediscorrect for(;;)
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x&(-x))
#define N 100005
using namespace std;
ll n,a[N],sum[N],mn[N];
double ans[N],now=0;
int main(){
jiasu;
memset(mn,0x3f3f3f,sizeof(mn));
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=n;i>=1;i--){sum[i]=sum[i+1]+a[i];mn[i]=min(mn[i+1],a[i]);
}
for(int i=2;i<=n-1;i++){ans[i]=1.0*(sum[i]-mn[i])/(n-i);now=max(now,ans[i]);
}
for(int i=2;i<=n-1;i++){if(ans[i]==now){cout<<i-1<<endl;}
}return 0;
} 

P4085 [USACO17DEC] Haybale Feast G - 洛谷

 ST表+二分查找。我们可知，我们想要得到辣度的最小值，那么肯定是刚刚满足总风味>=m。那么对于每一个起点i，我们查找sum[j]>=sum[i]+m的那个点（用二分），再用ST表查找这个区间的辣度的最大值。

#include<bits/stdc++.h>
#define ll long long
#define samplepassediscorrect for(;;)
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x&(-x))
#define N 100005
using namespace std;
ll n,m,st[N][30],f,s,sum[N],mn,ans=1e18;
int search(ll x){return lower_bound(sum+1,sum+1+n,x)-sum;}
ll find(int l,int r){int x=log2(r-l+1);return max(st[l][x],st[r-(1<<x)+1][x]);
}
int main(){
jiasu;
cin>>n>>m;
for(int i=1;i<=n;i++){cin>>f>>s;st[i][0]=s;sum[i]=sum[i-1]+f;
}
for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
for(int i=0;i<=n;i++){int j=search(sum[i]+m);if(j==n+1) break;ans=min(ans,find(i+1,j));
}
cout<<ans;return 0;
} 

 P4514 上帝造题的七分钟 - 洛谷

 二维树状数组模板，但我现在还不太理解。只能硬记着先学会应用。这题开long long会MLE，很奇怪，t1,t4数组我开着long long就会有错的，提示是输出了负号就是有溢出。全改成int就没错。

#include<bits/stdc++.h>
#define ll long long
#define samplepassediscorrect for(;;)
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x&(-x))
#define N 2050
using namespace std;
int n,m,a,b,c,d,f;
char ch;
struct Two_dimensional_Fenwick_Tree{int t2[N][N],t3[N][N];int t1[N][N],t4[N][N];void update(int x,int y,ll d){for(int i=x;i<=n;i+=lowbit(i))for(int j=y;j<=n;j+=lowbit(j))t1[i][j]+=d,t2[i][j]+=x*d,t3[i][j]+=y*d,t4[i][j]+=x*y*d;}int sum(int x,int y){int ans=0;for(int i=x;i>0;i-=lowbit(i))for(int j=y;j>0;j-=lowbit(j))	ans+=(x+1)*(y+1)*t1[i][j]-(y+1)*t2[i][j]-(x+1)*t3[i][j]+t4[i][j];return ans;}
}r;
int main(){
jiasu;
cin>>ch>>n>>m;
while(cin>>ch){if(ch=='L'){cin>>a>>b>>c>>d>>f;r.update(a,b,f),r.update(a,d+1,-f),r.update(c+1,b,-f),r.update(c+1,d+1,f);}else{cin>>a>>b>>c>>d;cout<<r.sum(c,d)-r.sum(a-1,d)-r.sum(c,b-1)+r.sum(a-1,b-1)<<endl;}
}return 0;
}