标签为 [ZJOI] 的文章

BZOJ1096 [ZJOI2007]仓库建设

题目传送门 这是一道比较裸的动态规划斜率优化 考虑f[i]表示前i个工厂,其中第i个一定建了仓库的最小费用。 s1[i]表示i号点到n号点的距离 s2[i]表示1~i号点的所有物资运到n号点的费用,s2[i]=s2[i-1]+s1[i]*p[i] s3[i]表示1~i号点的物资数量 $$f[j]=min_{j=0}^{i-1}{f[j]+s2[i]-s2[j]-s1[i]*(s3[i]-s3[j])}$$ 考虑对于i的两个决策点j,k(j<k),所以(s3[k]-s3[j])>0假设k比j优,即 $$f[j]+s2[i]-s2[j]-s1[i](s3[i]-s3[j])>=f[k]+s2[i]-s2[k]-s1[i](s3[i]-s3[k])$$ $$f[j]-s2[j]-f[k]+s2[k]>=s1[i]*(s3[k]-s3 ......

BZOJ4785 树状数组

题目传送门 solution 写错的树状数组其实就是求一个后缀和,设suml[i]为前缀和,sumr[i]为后缀和,则题目要求suml[r]-suml[l-1],然后我们来比较一下suml[r]-sum[l-1]和-(sumr[l-1]-sumr[r])(相反数在mod 2 意义下相等)发现他们相差的就是val[l-1]和val[r],然后要使他们相等就是说val[l-1]和val[r]要在mod 2意义下相等,当l=1时就是询问一个点的前缀和和后缀和是否相等。 然后将每个询问看成一个二维平面上的点,(l-1,r),用树套树来维护点合法的概率,用(l1,r1,l2,r2)表示左端点在l1,r1间,右端点在(l2,r2)间的所有区间,然后在(l,r ......