• 欢迎光临~

# 【比赛】八一特别行动

## 背景

 # 用  户  名 南 昌 起 义 总分 18 1Liu 100 03:58:44 10 02:02:22 1 03:51:14 0 00:59:03 111 03:58:44

## A.南

[begin{align*} f[i]&=frac{i}{n}times(f[i]+1)+frac{n-i}{n}times(f[i+1]+1) \ &=f[i+1]+frac{n}{n-i} end{align*}]

[begin{align*} g[i]&=frac{i}{n}times(g[i]+f[i]+1)+frac{n-i}{n}times(g[i+1]+f[i+1]+1) \ &=frac{i}{n-i}times f[i]+g[i+1]+f[i+1]+frac{n}{n-i} end{align*}]

``````#include<bits/stdc++.h>
#define ll int
#define rg register
#define maxn 10001
#define rll rg ll
using namespace std;
{
rll f=0,x=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
ll n;
double dp[maxn],ans[maxn];
int main()
{
for(rll i=n-1;i+1;i--)
{
dp[i]=dp[i+1]+(double)n/((double)(n-i));
ans[i]=((double)n)/((double)(n-i))+(double)dp[i]*((double)i/(n-i))+dp[i+1]+ans[i+1];
}
printf("%.2lf",ans[0]);
return 0;
}
``````

## B.昌

(max) 操作只需取 (f[u] = sumlimits_{vin son[u]} f[v]) .

``````inline void dfs(rll x)
{
if(g[x].empty()) { dp[x]=1; return; }
if(a[x])
{
dp[x]=0x7fffffff;
for(rll i=0;i<g[x].size();i++)
{
rll to=g[x][i];
dfs(to);
dp[x]=min(dp[x],dp[to]);
}
}
else for(rll i=0;i<g[x].size();i++)
{
rll to=g[x][i];
dfs(to);
dp[x]+=dp[to];
}
}
``````

## C.起

[g[i][j][k] = min(g[i − 1][j][k], g[i][j − 1][k], g[i − 1][j − 1][k]) + 1 ]

[f[i+2times k-1][j+2times k-1][k] = sumlimits_{k=1}^{min(n,m)} {(g[i + k − 1][j + k − 1][1] ≥ k)cup (g[i + k − 1][j + 2 × k − 1][2] = k)cup (g[i + 2 × k − 1][j + k − 1][3] = k)cup (g[i + 2 × k − 1][j + 2 × k − 1][4] = k])} ]

``````#include<bits/stdc++.h>
#define ll long long
#define rg register
#define maxn 501
#define rll rg ll
using namespace std;
{
rll f=0,x=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
inline void write(rll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);putchar(x%10|48);
}
ll n,m,t,q,a,b,c,d,ans;
ll mp[maxn][maxn];
ll f[maxn][maxn][maxn>>1],g[maxn][maxn][5];
char s[maxn];
inline bool check(rll x1,rll y1,rll x2,rll y2,rll mid)
{
return f[x2][y2][mid]-f[x2][y1-1][mid]-f[x1-1][y2][mid]+f[x1-1][y1-1][mid]>0;
}
int main()
{
for(rll i=1;i<=n;i++)
{
scanf("%s",s+1);
for(rll j=1;j<=m;j++)
switch(s[j])
{
case 'B':mp[i][j]=1;break;
case 'W':mp[i][j]=2;break;
case 'P':mp[i][j]=3;break;
case 'G':mp[i][j]=4;break;
}
}
for(rll i=1;i<=n;i++)
for(rll j=1;j<=m;j++)
if(mp[i][j]==1)
g[i][j][1]=min(g[i-1][j][1],min(g[i][j-1][1],g[i-1][j-1][1]))+1;
else if(mp[i][j]==2)
g[i][j][2]=min(g[i-1][j][2],min(g[i][j-1][2],g[i-1][j-1][2]))+1;
else if(mp[i][j]==3)
g[i][j][3]=min(g[i-1][j][3],min(g[i][j-1][3],g[i-1][j-1][3]))+1;
else if(mp[i][j]==4)
g[i][j][4]=min(g[i-1][j][4],min(g[i][j-1][4],g[i-1][j-1][4]))+1;
for(rll k=1;k<=(min(n,m)>>1);k++)
for(rll i=1;i<=n;i++)
for(rll j=1;j<=m;j++)
if(g[i+k-1][j+k-1][1]>=k&&g[i+k-1][j+(k<<1)-1][2]==k&&g[i+(k<<1)-1][j+k-1][3]==k&&g[i+(k<<1)-1][j+(k<<1)-1][4]==k)
f[i+(k<<1)-1][j+(k<<1)-1][k]=1;
for(rll i=1;i<=n;i++)
for(rll j=1;j<=m;j++)
for(rll k=1;k<=(min(n,m)>>1);k++)
f[i][j][k]+=f[i-1][j][k]+f[i][j-1][k]-f[i-1][j-1][k];
while(q--)
{
ans=0;
rll l=1,r=min(c-a+1,d-b+1);
if(r>1) r>>=1;
while(l<=r)
{
rll mid=(l+r)>>1;
if(check(a+(mid<<1)-1,b+(mid<<1)-1,c,d,mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d",(ans*ans)<<2);putchar('n');
}
return 0;
}
``````

## D.义

(sqrt n) 种物品，定义 (f[i][j]) 为取完第 (i) 种物品，背包容量占了 (j)，显然有转移

[f[i][j] = f[i−1][j]+f[i][j−i]−f[i−1][j−i×(i+1)] ]

[g[i][j+i] = g[i][j+i]+g[i][j] ]

[g[i][j+sqrt n +1] = g[i][j+sqrt n +1]+g[i][j] ]