【比赛】八一特别行动

建军节之际，怎么能没有点有纪念意义的活动呢.

背景

好了这不是重点，重点是：
做题！

这一次的题目以南昌起义为主题，通过题目探究使我们认识到党和人民一路走来的艰辛并为之奋斗.

在此之前先模一下史一鸣大佬

然后我这样

相差甚远.

A.南

密码保护的题面

一道经典的概率题.
定义 (f[i]) 为取完 (i) 种武器，要取完 (n) 种武器的期望步数，显然有 (f[n]=0)，转移也很好想，无非是取到已经有的和取到一个没有的
即：

定义 (g[i]) 为取完 (i) 种武器，要取完 (n) 种武器的期望钱数，同样有 (g[n]=0)，转移也是分为取到已经有的和取到一个没有的

最后 (g[0]) 即为期望值.

#include<bits/stdc++.h>
#define ll int
#define rg register
#define maxn 10001
#define rll rg ll
using namespace std;
inline ll read()
{
	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()
{
	n=read();
	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.昌

仍然是密码保护的题面
我们先假设根结点的权值 (geq x)，那么每一次在下面取 (min) 时，这个点的子结点权值都要 (geq x)，取 (max) 时，这个点的子结点权值至少有一个要 (geq x) .

通过DFS可以求出有多少叶子结点的权值 (geq x).
这里的 (max) 操作只需取 (f[u] = minlimits_{vin son[u]} f[v])，
(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];
	}
}

最后答案即为 (k-f[1]+1) （(k) 为叶子结点个数）.

C.起

题面（你懂的）

当时考场上不会做，因此就有了：

对于正解，显然这是一道dp题，定义 (f[i][j][k]) 为以 ((i,j)) 为左上角的边长为 (2k) 的合法正方形，定义 (g[i][j][k]) 为以 为右
下角的颜色为 (k) 的正方形的最长长度
那么有以下转移：

预处理 (f[i][j][k]) 的前缀和，查询时用其二分答案即可.

#include<bits/stdc++.h>
#define ll long long
#define rg register
#define maxn 501
#define rll rg ll
using namespace std;
inline ll read()
{
	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()
{
	n=read();m=read();q=read();
	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;
		a=read();b=read();c=read();d=read();
		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.义

仍然是你懂的

懒得写了，这里放上官方题解和一份std：

对于前 (sqrt n) 种物品，对于一种物品可能都会取完而对于 (sqrt n +1 ∼ n) 种物品，总共最多会取 (sqrt n) 个所以可以分开进行 dp
前 (sqrt n) 种物品，定义 (f[i][j]) 为取完第 (i) 种物品，背包容量占了 (j)，显然有转移

表示不拿 (i) 物品，再拿一个 (i) 物品，而且最多只能拿 (i) 个，所以要减去多拿的方案再考虑后面的物品，定义 (g[i][j]) 表示拿了 (i) 件 (sqrt n +1 ∼ n) 种中的物品，背包容量占了 (j)，转移为

表示选中的每个物品都增加 1 的容量，变为下一种物品，就是不拿第 (sqrt n +1) 种物品

表示拿一个第 (sqrt n +1) 种物品
最后把两个数组的方案数相乘加和即可，总复杂度是 (Theta(nsqrt n)) 的