以后平时练习还是写一写吧。
（题目搞来搞去太烦了，直接PDF存起来）
T1 水题（???），主要是数据水，正解是设一个阙值，然而根本没人打。（暴力出奇迹）
CODE
#include<cstdio> using namespace std; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } const int N=1e5+5; int sum,a[N],n,t,p,i,q; int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); read(n); read(t); for (i=0;i<n;++i) read(a[i]); while (t--) { sum=0; read(q); read(p); for (i=q;i<n;i+=p) sum+=a[i]; printf("%d ",sum); } return 0; }
T2 猥琐数学题（？？？）一定要想到，如果有解那么h[i]+l[j]≡k-a[i][j](mod k) 然后可以每次枚举第一列的数来当做这一列的操作次数，然后由此递推下去。
因为一定有解，所以取最小值即可。
（其实当时我打了BFS然后帅气爆0，连5*5的图都搜不出来）
CODE
#include<cstdio> #include<cstring> using namespace std; typedef long long LL; const int N=1005; LL a[N][N],h[N],l[N],ans_h[N],ans_l[N],n,m,i,j,ans=-1,sum,k,p; inline void read(LL &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline void copy() { for (int i=1;i<=n;++i) ans_h[i]=h[i]; for (int j=1;j<=m;++j) ans_l[j]=l[j]; } int main() { freopen("b.in","r",stdin); freopen("b.out","w",stdout); read(n); read(m); read(k); for (i=1;i<=n;++i) for (j=1;j<=m;++j) read(a[i][j]),a[i][j]=(k-a[i][j]%k)%k; for (p=1;p<=m;++p) { memset(h,0,sizeof(h)); memset(l,0,sizeof(l)); h[1]=a[1][p]; sum=h[1]; for (i=1;i<=n;++i) l[i]=(a[1][i]-h[1]+k)%k,sum+=l[i]; for (j=2;j<=m;++j) h[j]=(a[j][1]-l[1]+k)%k,sum+=h[j]; if (ans==-1||sum<ans) ans=sum,copy(); } printf("%lld ",ans); for (i=1;i<=n;++i) printf("%lld ",ans_h[i]); putchar(' '); for (j=1;j<=m;++j) printf("%lld ",ans_l[j]); putchar(' '); return 0; }
（注意开 long long）
T3 爆力+小优化即可轻松跑过（然而我想出了优化却把暴力的一个很重要的数组删掉了）
注意到一个位置上的存水量即为max(min(l[i],r[i])-a[i],0); l[i],r[i]是左（右）两边（不包括自己）的最高高度，a[i]是i位置上的墙的高度。
l[i],r[i]可以预处理，每次有墙的高度变化的时候就像左右更新l[i],r[i]，如果发现高度没有其它墙高直接break即可（important）。
在上次的基础计算的时候再开一个last[i]记录上一次操作后剩下的水量（后来就是作死删掉了这个数组）
CODE
#include<cstdio> using namespace std; typedef long long LL; inline void read(LL &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline LL max(LL a,LL b) { return a>b?a:b; } inline LL min(LL a,LL b) { return a<b?a:b; } const LL N=1e5+5; LL a[N],l[N],r[N],last[N],n,q,x,y,t,w,i; int main() { freopen("c.in","r",stdin); freopen("c.out","w",stdout); w=0; read(n); read(q); for (i=1;i<=n;++i) read(a[i]); l[1]=r[n]=0; for (i=2;i<=n;++i) l[i]=max(l[i-1],a[i-1]); for (i=n-1;i;--i) r[i]=max(r[i+1],a[i+1]); for (i=1;i<=n;++i) w+=last[i]=max(min(l[i],r[i])-a[i],0); while (q--) { char ch=getchar(); while (ch!='P'&&ch!='U') ch=getchar(); if (ch=='P') { printf("%lld ",w); getchar(); } else { read(x); read(y); a[x]+=y; if (last[x]>y) w-=y,last[x]-=y; else w-=last[x],last[x]=0; for (i=x-1;i;--i) if (a[x]>r[i]) w+=max(min(l[i],a[x])-a[i],0)-max(min(l[i],r[i])-a[i],0),last[i]=max(min(l[i],a[x])-a[i],0),r[i]=a[x]; else break; for (i=x+1;i<=n;++i) if (a[x]>l[i]) w+=max(min(a[x],r[i])-a[i],0)-max(min(l[i],r[i])-a[i],0),last[i]=max(min(a[x],r[i])-a[i],0),l[i]=a[x]; else break; } } return 0; }