这名字诡异（然而就是这样）
这次主要是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=;
LL a[N][N],n,m,i,j,v,h,s;
inline char get(void)
{
static char buf[], *p1 = buf, *p2 = buf;
if (p1 == p2)
{
p2 = (p1 = buf) + fread(buf, , , stdin);
if (p1 == p2) return EOF;
}
return *p1++;
}
inline void read(LL &x)
{
x = ; static char c;
for (; !(c >= '' && c <= ''); c = get());
for (; c >= '' && c <= ''; x = x * + c - '', c = get());
}
inline bool check(LL k)
{
long long res=;
for (i=;i<=n;++i)
for (j=;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=;i<=n;++i)
for (j=;j<=m;++j)
read(a[i][j]);
LL l=,r=v+;
while (l<=r)
{
LL mid=l+r>>;
if (check(mid)) h=mid+,l=mid+; else r=mid-;
}
for (i=;i<=n;++i)
for (j=;j<=m;++j)
if (a[i][j]<=h) s+=a[i][j];
printf("%lld %lld",h,s);
return ;
}
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=;
LL sum[N],a[N],mx[N],n,m,i,x,res;
inline char get(void)
{
static char buf[], *p1 = buf, *p2 = buf;
if (p1 == p2)
{
p2 = (p1 = buf) + fread(buf, , , stdin);
if (p1 == p2) return EOF;
}
return *p1++;
}
inline void read(LL &x)
{
x = ; static char c;
for (; !(c >= '' && c <= ''); c = get());
for (; c >= '' && c <= ''; x = x * + c - '', c = get());
}
inline void write(LL x)
{
if (x/) write(x/);
putchar(x%+'');
}
int main()
{
freopen("dam.in","r",stdin); freopen("dam.out","w",stdout);
read(n); read(m);
for (i=;i<=n;++i)
read(a[i]);
while (m--)
{
read(x);
sum[]=;
for (i=;i<=n;++i)
sum[i]=sum[i-]+a[i]-x;
mx[n]=sum[n];
for (i=n-;i;--i)
mx[i]=sum[i]>mx[i+]?sum[i]:mx[i+];
res=;
for (i=;i+res<=n;++i)
while (mx[i+res]>=sum[i-]&&i+res<=n) ++res;
write(res);
putchar(' ');
}
//printf("\n%.2lf",(double)clock());
return ;
}
T3 当时看到题目蒙蔽了，从来没坐过概率之类的问题。
yu‘ao dalao打了很长（貌似）的递推，然后我看了标算才大彻大悟。
这就是一道你知道概率公式记忆化搜索的题。
把一个状态（m，a[]）（m是剩下的天数，a[]是每个人剩下的体力)hash成一个不会重复的大整数。记搜即可。
CODE
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=,seed=,MAX_SIZE=;
int a[N],n,m,i;
double s[MAX_SIZE];
bool f[MAX_SIZE];
inline void read(int &x)
{
x=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
inline int hash(int m)
{
int res=m;
for (int i=;i<n;++i)
res=res*seed+a[i];
return res;
}
inline double dfs(int m)
{
if (!m) return 1.0*(a[]>);
if (f[hash(m)]) return s[hash(m)];
f[hash(m)]=;
double tot=0.0,t=0.0;
for (int i=;i<=n;++i)
if (a[i]>)
{
a[i]--; tot+=dfs(m-); a[i]++; t++;
}
if (t) return s[hash(m)]=tot/t; else return ;
}
int main()
{
freopen("hung.in","r",stdin); freopen("hung.out","w",stdout);
read(n); read(m);
for (i=;i<=n;++i)
read(a[i]);
for (i=;i<=n;++i)
{
swap(a[],a[i]);
memset(f,,sizeof(f));
printf("%.6lf\n",dfs(m));
}
return ;
}