今天的考试真的是天崩地裂，写了的三个题全炸。。。然而谁叫我弱+不注意细节呢？？？真的要扇耳光。。。
T1:
题意：一段区间的高度为这个区间中高度的最小值，给定n个宽度，求每个宽度的期望高度
40% ：算出长度为x的区间的所有的最小值的取值的和，除以总的方案数(n-x+1)，用ST表预处理可以n^2;(记得开long long)
100%：对于每个点求出他取最小值的区间，即用两遍单调栈求出左,右边第一个小于他的值。。。记为l[i]，和r[i],这一步和影魔很像；
对于当前这一个点，考虑以他为最小值，能贡献给多少个区间。。。
记l1=i-l[i]+1,l2=r[i]-i+1;
对于长度L在[1,min(l1,l2)]的区间，可以贡献L*a[i]；
对于长度L在[min(l1,l2)+1,max(l1,l2)]，可以贡献min(l1,l2)*a[i];
对于长度L在[max(l1,l2)+1,r[i]-l[i]+1]，可以贡献(r[i]-l[i]+1-L+1)*a[i];
(算对长度为L的区间的贡献就是看长度为L的区间在[l[i],r[i]]内移动能包含i点多少次);
然后涉及多次修改和一次询问，考虑序列差分。。。然而这是一个优秀的差分。。。
发现修改有两种，一个是一段区间加上相同的值，另一个是和每个点本身的长度有关。。。
所以建两个差分数组，一个记录正常的差分，一个记录L前的系数，这样第三个情况需要拆成两个修改来维护。。。
其实说了这么多，代码还是很短的。。。
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
typedef long long ll;
const int N=2000000;
int gi(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
int n,m,a[N],q[N],tail,l[N],r[N],ans[N],cf1[N],cf2[N];
main(){
freopen("fence.in","r",stdin);
freopen("fence.out","w",stdout);
scanf("%lld",&n);for(int i=1;i<=n;i++) a[i]=gi();
tail=0;q[++tail]=0;
for(int i=1;i<=n;i++){
while(tail>0&&a[i]<=a[q[tail]]) tail--;
l[i]=q[tail]+1;q[++tail]=i;
}
tail=0;q[++tail]=n+1;
for(int i=n;i>=1;i--){
while(tail>0&&a[i]<a[q[tail]]) tail--;
r[i]=q[tail]-1;q[++tail]=i;
}
for(int i=1;i<=n;i++){
int l1=i-l[i]+1,l2=r[i]-i+1;
cf1[1]+=a[i];cf1[min(l1,l2)+1]-=a[i];
cf2[min(l1,l2)+1]+=a[i]*min(l1,l2);cf2[max(l1,l2)+1]-=a[i]*min(l1,l2);
cf2[max(l1,l2)+1]+=a[i]*(r[i]-l[i]+2),cf2[r[i]-l[i]+2]-=a[i]*(r[i]-l[i]+2);
cf1[max(l1,l2)+1]-=a[i],cf1[r[i]-l[i]+2]+=a[i];
}
for(int i=1;i<=n;i++) cf1[i]+=cf1[i-1],cf2[i]+=cf2[i-1],ans[i]=cf1[i]*i+cf2[i];
scanf("%lld",&m);while(m--){int x=gi();printf("%.5f
",ans[x]*1.0/(n-x+1));}
return 0;
}
T2:
题意：由于题面描述过于生动，令人影响深刻，所以不再描述。。。
做法：考虑到要尽量在v大的那天开，且一天就要开完，且前面可以养精蓄锐留到v大的那天来开。。。
所以考虑维护一个v递减的单调栈来对决策进行调整，在弹栈的过程中分情况讨论一下调整即可。。。
if(life[i]+life[q[tail]]<=E) life[i]+=life[q[tail],Ans-=v[q[tail]]*life[q[tail]];//把第q[tail]天的精力留到第i天
if(life[i]+life[q[tail]]>E) Ans-=(E-life[i])*v[q[tail]],life[i]=E;//和上面同理，yy一下
然后有一个史前巨坑：R>E,如果没有R=min(R,E)就会光荣baoling。。。。
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
typedef long long ll;
const int M=1000050;
int T,E,R,N,v[M],life[M],q[M],tail,Ans;
main(){
freopen("power.in","r",stdin);
freopen("power.out","w",stdout);
scanf("%lld",&T);
while(T--){
scanf("%lld%lld%lld",&E,&R,&N);R=min(R,E);
for(int i=1;i<=N;i++) scanf("%lld",&v[i]);
memset(life,0,sizeof(life));tail=0;Ans=0;
q[++tail]=1;life[1]=E;Ans=life[1]*v[1];
for(int i=2;i<=N;i++){
life[i]=R;
while(tail>0&&v[q[tail]]<v[i]){
if(life[i]+life[q[tail]]>E) Ans-=(E-life[i])*v[q[tail]],life[i]=E;
else Ans-=life[q[tail]]*v[q[tail]],life[i]+=life[q[tail]];
tail--;
}
Ans+=life[i]*v[i];q[++tail]=i;
}
printf("%lld
",Ans);
}
return 0;
}
T3:弃坑了。。。
T4:
题意：关路灯，见codevs。。。
我真的是太弱了，这种DP都打不出来。。。
dp[i][j][0]表示关完了区间[i,j]的灯，然后在区间的左端点的最少花费。。。
dp[i][j][1]表示关完了区间[i,j]的灯，然后在区间的右端点的最少花费。。。
然后用功率的前缀和表示其他区间的能耗情况。。。
然后转移就是4种：
从左到左，从右到左，从右到右，从左到右。。。每次至移动一位来转移。。。
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define RG register
#define Min(a,b) (a<b?a:b)
const int N = 1050;
using namespace std;
typedef long long ll;
inline int gi(){
RG char ch=getchar();RG int x=0;
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
ll d[N],w[N],dp[N][N][2];
int main(){
freopen("light.in","r",stdin);
freopen("light.out","w",stdout);
int n=gi(),m=gi(); RG int i,j; ll z;
for (i=1; i<=n; ++i) d[i]=gi(),w[i]=w[i-1]+gi();
memset(dp,56,sizeof(dp));
dp[m][m][0]=dp[m][m][1]=0;
for (i=m; i; --i)
for (j=m; j<=n; ++j){
z=w[n]-w[j]+w[i-1];
dp[i-1][j][0]=Min(dp[i-1][j][0],dp[i][j][0]+(d[i]-d[i-1])*z);
dp[i-1][j][0]=Min(dp[i-1][j][0],dp[i][j][1]+(d[j]-d[i-1])*z);
dp[i][j+1][1]=Min(dp[i][j+1][1],dp[i][j][0]+(d[j+1]-d[i])*z);
dp[i][j+1][1]=Min(dp[i][j+1][1],dp[i][j][1]+(d[j+1]-d[j])*z);
}
printf("%lld",Min(dp[1][n][0],dp[1][n][1]));
return 0;
}