• 欢迎光临~

【比赛】八一特别行动

开发技术 开发技术 2022-08-02 次浏览

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

背景

【比赛】八一特别行动

好了这不是重点,重点是:
做题!

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

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

【比赛】八一特别行动

然后我这样

#

  用  户  名  

总分

18

1Liu

100

03:58:44

10

02:02:22

1

03:51:14

0

00:59:03

111

03:58:44

相差甚远.

A.南

密码保护的题面

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

[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*}]

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

[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*}]

最后 (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) 的正方形的最长长度
那么有以下转移:

[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])} ]

预处理 (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),显然有转移

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

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

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

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

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

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

程序员灯塔
转载请注明原文链接:【比赛】八一特别行动
喜欢 (0)