这名字诡异（然而就是这样）
这次主要是yekehe和yu‘ao都来了，所以很开心的讨论（上了200）。
但是，yu’ao dalao又AK了！（666666）
不过总体难度也不高，主要是T3没思路。
T1 二分或桶
·如果你不会这道题，出门右转找傅哥去。
去年蒟蒻时期的噩梦啊。然而只是一道PJ的水题。
二分洪水的高度（题目错了，数据是向上取整），然后判断是否可行。
注意开long long（不开80）
CODE
#include<cstdio> using namespace std; typedef long long LL; const int N=405; LL a[N][N],n,m,i,j,v,h,s; inline char get(void) { static char buf[100000], *p1 = buf, *p2 = buf; if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, 100000, stdin); if (p1 == p2) return EOF; } return *p1++; } inline void read(LL &x) { x = 0; static char c; for (; !(c >= '0' && c <= '9'); c = get()); for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); } inline bool check(LL k) { long long res=0; for (i=1;i<=n;++i) for (j=1;j<=m;++j) if (a[i][j]<=k) res+=k-a[i][j]; return res<v; } int main() { freopen("water.in","r",stdin); freopen("water.out","w",stdout); read(n); read(m); read(v); for (i=1;i<=n;++i) for (j=1;j<=m;++j) read(a[i][j]); LL l=0,r=v+1; while (l<=r) { LL mid=l+r>>1; if (check(mid)) h=mid+1,l=mid+1; else r=mid-1; } for (i=1;i<=n;++i) for (j=1;j<=m;++j) if (a[i][j]<=h) s+=a[i][j]; printf("%lld %lld",h,s); return 0; }
T2 前缀和+姜度大佬玄学算法。
首先思路很好想，把墙的高度都减去一个x就转化成了一个找连续区间的和>=0的问题了。
暴力：O（n^3）； 前缀和优化：O（n^2）； 单调栈上二分（裸二分会炸）：O（n log n）；
这些，都过不了。
然后由于姜度dalao暑假来HW给我们讲过了求最长的区间和>=k的算法，非常简洁且有效率（O（n））；
设一个数组mx[]表示后向前缀和最大值，当前答案为res，那么如果mx[i+res]>=s[i]，则向后枚举答案一定增大。
由于两个指针（i和res）一起增大，所以复杂度为O（n）；
CODE
#include<cstdio> //#include<ctime> using namespace std; typedef long long LL; const LL N=1000005; LL sum[N],a[N],mx[N],n,m,i,x,res; inline char get(void) { static char buf[10000000], *p1 = buf, *p2 = buf; if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, 10000000, stdin); if (p1 == p2) return EOF; } return *p1++; } inline void read(LL &x) { x = 0; static char c; for (; !(c >= '0' && c <= '9'); c = get()); for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); } inline void write(LL x) { if (x/10) write(x/10); putchar(x%10+'0'); } int main() { freopen("dam.in","r",stdin); freopen("dam.out","w",stdout); read(n); read(m); for (i=1;i<=n;++i) read(a[i]); while (m--) { read(x); sum[0]=0; for (i=1;i<=n;++i) sum[i]=sum[i-1]+a[i]-x; mx[n]=sum[n]; for (i=n-1;i;--i) mx[i]=sum[i]>mx[i+1]?sum[i]:mx[i+1]; res=0; for (i=1;i+res<=n;++i) while (mx[i+res]>=sum[i-1]&&i+res<=n) ++res; write(res); putchar(' '); } //printf(" %.2lf",(double)clock()); return 0; }
T3 当时看到题目蒙蔽了，从来没坐过概率之类的问题。
yu‘ao dalao打了很长（貌似）的递推，然后我看了标算才大彻大悟。
这就是一道你知道概率公式记忆化搜索的题。
把一个状态（m，a[]）（m是剩下的天数，a[]是每个人剩下的体力)hash成一个不会重复的大整数。记搜即可。
CODE
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int N=5,seed=51,MAX_SIZE=20000005; int a[N],n,m,i; double s[MAX_SIZE]; bool f[MAX_SIZE]; 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(); } inline int hash(int m) { int res=m; for (int i=1;i<n;++i) res=res*seed+a[i]; return res; } inline double dfs(int m) { if (!m) return 1.0*(a[1]>0); if (f[hash(m)]) return s[hash(m)]; f[hash(m)]=1; double tot=0.0,t=0.0; for (int i=1;i<=n;++i) if (a[i]>0) { a[i]--; tot+=dfs(m-1); a[i]++; t++; } if (t) return s[hash(m)]=tot/t; else return 0; } int main() { freopen("hung.in","r",stdin); freopen("hung.out","w",stdout); read(n); read(m); for (i=1;i<=n;++i) read(a[i]); for (i=1;i<=n;++i) { swap(a[1],a[i]); memset(f,0,sizeof(f)); printf("%.6lf ",dfs(m)); } return 0; }