多校A层冲刺NOIP2024模拟赛02 & csp-s模拟9

hzoi_Shadow / 2024-10-07 / 原文

多校A层冲刺NOIP2024模拟赛02

四道题因为暑假被拉去当模拟赛暑假集训CSP提高模拟22 了，遂直接把赛后代码交了上去，然后就被通知换题了。

原 $100+100+100+20$ 被在 accoders NOI 上被卡成了 $100+100+90+10$ ，更改 long long 和 int 后达到了 $100+100+100+30$ 。

$T1$ A. 法阵

详见暑假集训CSP提高模拟22 T1 P264. 法阵。

$T2$ B. 连通块

详见暑假集训CSP提高模拟22 T2 P265. 连通块。

$T3$ C. 军队

详见暑假集训CSP提高模拟22 T3 P266. 军队。

$T4$ D. 棋盘

详见暑假集训CSP提高模拟22 T4 P267. 棋盘。

csp-s模拟9

$T1$ T1075. 邻面合并 $0pts$

部分分
- $30 \%$ ：打表加手摸。
  - 该代码仅手摸了 $n,m \le 3$ 的数据，且不保证正确性。

正解

观察到 $\min \{ n,m \} \le 8$ ，考虑状压 $DP$ 。
具体地，以每一块的开头作为分割点，并记录作状态，总状态数为 $2^{m}$ 。
- 判断是否合法的一个重要标准是原矩阵中的 $0$ 不可以是分割点，原矩阵的 $1$ 若本身不是分割点则到前面最近的分割点直接不能有 $0$ 。
转移的时候枚举上一行的状态，计算达成这两行的分割方式需要新创建多少个块。较为简便的做法是拿本行块的总数减去与上一行分割方式相同的块数（可以直接合并的块），建议画图理解。
- 图来自官方题解。

时间复杂度为 $O(nm2^{2m})$ 。

点击查看代码

int a[120][10],f[110][1<<10],opt[110][10][1<<10];
bool check(int hang,int s,int m)
{
	int last=0;
	for(int i=0;i<=m-1;i++)
	{
		if(((s>>i)&1)&&a[hang][i+1]==0)
		{
			return false;
		}
	}
	for(int i=0;i<=m-1;i++)
	{
		if((s>>i)&1)
		{
			last=1;
		}
		if(a[hang][i+1]==0)
		{
			last=0;
		}
		if(last==0&&a[hang][i+1]==1)
		{
			return false;
		}
	}
	return true;
}
int work(int hang,int lie,int s)
{
	while(a[hang][lie+1]==1&&((s>>(lie-1+1))&1)==0)
	{
		lie++;
	}
	return lie;
}
int main()
{
	freopen("merging.in","r",stdin);
	freopen("merging.out","w",stdout);
	int n,m,ans=0x7f7f7f7f,sum,i,j,k,h;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(i=0;i<=(1<<m)-1;i++)
	{
		f[0][i]=0;
	}
	for(k=1;k<=n;k++)
	{
		for(i=0;i<=(1<<m)-1;i++)
		{
			if(check(k,i,m)==true)
			{
				for(j=1;j<=m;j++)
				{
					opt[k][j][i]=work(k,j,i);
				}
			}
		}
	}
	for(k=1;k<=n;k++)
	{
		for(i=0;i<=(1<<m)-1;i++)
		{
			if(check(k,i,m)==true)
			{
				for(j=0;j<=(1<<m)-1;j++)
				{
					if(check(k-1,j,m)==true) 
					{
						sum=__builtin_popcount(i);
						for(h=0;h<=m-1;h++)
						{
							if(((i>>h)&1)&&((j>>h)&1))
							{
								sum-=(opt[k][h+1][i]==opt[k-1][h+1][j]);
							}
						}
						f[k][i]=min(f[k][i],f[k-1][j]+sum);
					}
				}
			}
		}
	}
	for(i=0;i<=(1<<m)-1;i++)
	{
		ans=min(ans,f[n][i]);
	}
	cout<<ans<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

$T2$ T1076. 光线追踪 $0pts$

部分分
正解
- 不难发现对于矩阵覆盖对答案有可能产生贡献的只有左高和下底两条边。
- 考虑处理处理出每个矩形左高、下底对应的斜率范围。
- 对横纵坐标各开一棵区间修改、单点查询线段树维护即可。
- 离线下来对斜率离散化减少炸精度的可能。
  点击查看代码

$T3$ T2186. 百鸽笼 $0pts$

原题： UOJ 390. 【UNR #3】百鸽笼

部分分

$0pts$ ：爆搜。

点击查看代码

const ll p=998244353;
ll a[50],aa[50],pos[50],inv[50],f[50];
ll qpow(ll a,ll b,ll p)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=ans*a%p;
		}
		b>>=1;
		a=a*a%p;
	}
	return ans;
}
void dfs(ll len,ll n,ll sum,ll mul,ll cnt)
{
	if(len==sum)
	{
		for(ll i=1;i<=n;i++)
		{
			if(a[i]==1)
			{
				f[i]=(f[i]+mul)%p;
				return;
			}
		}
	}
	else
	{
		for(ll i=1;i<=n;i++)
		{
			if(a[i]>=1)
			{
				a[i]--;
				dfs(len+1,n,sum,mul*inv[cnt]%p,cnt-(a[i]==0));
				a[i]++;
			}
		}
	}
}
int main()
{
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
	ll n,sum=-1,i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
		inv[i]=qpow(i,p-2,p);
	}
	dfs(0,n,sum,1,n);
	for(i=1;i<=n;i++)
	{
		cout<<f[i]<<" ";
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

详见 UOJ NOI Round #3 Day2 题解百鸽笼。

正解
- 详见 UOJ NOI Round #3 Day2 题解百鸽笼。

$T4$ T2188. 滑稽树下你和我 $0pts$

原题： UOJ 371. 【UR #17】滑稽树下你和我

部分分

$5 \%$ ：输出 $stx,sty$ 在图上的距离。

点击查看代码

struct node
{
	int nxt,to;
}e[2010];
int head[2010],du[2010],cnt=0;
double x[2010],y[2010];
void add(int u,int v)
{
	cnt++;
	e[cnt].nxt=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
double work(double x1,double y1,double x2,double y2)
{ 
	return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	int n,u,v,stx,sty,i;
	double ans=0x7f7f7f7f;
	cin>>n>>stx>>sty;
	for(i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i];
	}
	for(i=1;i<=n-1;i++)
	{
		cin>>u>>v;
		add(u,v);
		add(v,u);
		du[u]++;
		du[v]++;
	}
	printf("%.8lf\n",work(x[stx],y[stx],x[sty],y[sty]));
	fclose(stdin);
	fclose(stdout);
	return 0;
}

详见 UOJ Round #17 题解滑稽树下你和我。

正解
- 详见 UOJ Round #17 题解滑稽树下你和我。

总结

期初只在 $ftp$ 里下发了 $T1,T2$ 的题面（没有数据范围和样例），过了 $10 \min$ 后才陆续上传了全部题面（截图）；全程没有看见除 $T3$ 大样例外的下发文件。
$T1$ 不会写爆搜，打表程序出的结果都是手动判断的。
$T2$
- 做法假了，把矩形覆盖当成了点的覆盖，询问直接死掉，从一开始的暴力到 map 套动态开点线段树、珂朵莉树都 $RE,MLE,TLE,WA$ 了。
- $huge$ 把数据点中的一个点作为大样例下发了，但做数据点配置文件时把输入、输出文件写反了。
$T4$ 两点间距离公式炸 int 了，挂了 $20pts$ 。