首页 > 其他分享 >【考试题解】多校A层冲刺NOIP2024模拟赛17

【考试题解】多校A层冲刺NOIP2024模拟赛17

时间：2024-11-01 19:43:03浏览次数：1  
标签：17 int 多校 long 考试题 2002 now dp define

A. 网格(grid)

题目内容

给你一个 \(n\times m\) 的字符网格 \(s\)，\(s_{i,j}\in[1,9]\cup\{+,*\}\)，从 \((1,1)\) 开始，仅向下或向右走并最终到达 \((n,m)\) 的路径被称为合法路径，求所有合法路径对应的表达式的运算结果之和，答案对 \(998244353\) 取模。

部分分

44pts

爆搜，枚举路径，直接算表达式值然后求和。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b;
const int mod=998244353;
char c[2002][2002],d[4004];
long long ans;
il void check()
{
	stack<int>num;
	stack<char>op;
	register long long rn=0;
	for(ri i=1;i<=a+b-1;i++)
	{
		if(d[i]>='0'&&d[i]<='9')
		{
			rn=(rn*10+d[i]-'0')%mod;
		}
		else
		{
			if(!op.empty()&&op.top()=='*')
			{
				op.pop();
				rn=(rn*num.top())%mod;
				num.pop();
			}
			num.push(rn);
			op.push(d[i]);
			rn=0;
		}
	}
	if(!op.empty()&&op.top()=='*')
	{
		op.pop();
		rn=(rn*num.top())%mod;
		num.pop();
	}
	num.push(rn);
	rn=0;
	while(!num.empty())
	{
		rn=(rn+num.top())%mod;
		num.pop();
	}
	ans=(ans+rn)%mod;
}
void dfs(int x,int y)
{
	d[x+y-1]=c[x][y];
	if(x==a&&y==b)
	{
		check();
		return;
	}
	if(x!=a)
	{
		dfs(x+1,y);
	}
	if(y!=b)
	{
		dfs(x,y+1);
	}
}
int main()
{
	freopen("grid.in","r",stdin);
	freopen("grid.out","w",stdout);
	scanf("%d%d",&a,&b);
	for(ri i=1;i<=a;i++)
	{
		for(ri j=1;j<=b;j++)
		{
			scanf("%c",&c[i][j]);
			if((c[i][j]<'0'||c[i][j]>'9')&&c[i][j]!='+'&&c[i][j]!='*')
			{
				j--;
			}
		}
	}
	dfs(1,1);
	printf("%lld",ans);
	return 0;
}

55pts

对于没有运算符的情况，容易观察到一个点对经过它的所有路径的贡献是相同的，而经过一个点有多少合法路径是经典问题，直接算就行。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b;
const int mod=998244353;
bool te1;
char c[2002][2002],d[4004];
long long ans,jc[4004],ny[4004],ten[4004];
void exgcd(int u,int v,long long &x,long long &y)
{
	if(!v)
	{
		x=1;
		y=0;
		return;
	}
	exgcd(v,u%v,y,x);
	y-=u/v*x;
}
il long long C(int x,int y)
{
	return (((jc[x]*ny[x-y])%mod)*ny[y])%mod;
}
il void check()
{
	stack<int>num;
	stack<char>op;
	register long long rn=0;
	for(ri i=1;i<=a+b-1;i++)
	{
		if(d[i]>='0'&&d[i]<='9')
		{
			rn=(rn*10+d[i]-'0')%mod;
		}
		else
		{
			if(!op.empty()&&op.top()=='*')
			{
				op.pop();
				rn=(rn*num.top())%mod;
				num.pop();
			}
			num.push(rn);
			op.push(d[i]);
			rn=0;
		}
	}
	if(!op.empty()&&op.top()=='*')
	{
		op.pop();
		rn=(rn*num.top())%mod;
		num.pop();
	}
	num.push(rn);
	rn=0;
	while(!num.empty())
	{
		rn=(rn+num.top())%mod;
		num.pop();
	}
	ans=(ans+rn)%mod;
}
void dfs(int x,int y)
{
	d[x+y-1]=c[x][y];
	if(x==a&&y==b)
	{
		check();
		return;
	}
	if(x!=a)
	{
		dfs(x+1,y);
	}
	if(y!=b)
	{
		dfs(x,y+1);
	}
}
namespace task1
{
	short main()
	{
		jc[0]=ny[0]=ten[0]=1;
		for(ri i=1;i<=a+b;i++)
		{
			jc[i]=(jc[i-1]*i)%mod;
			register long long j;
			exgcd(jc[i],mod,ny[i],j);
			while(ny[i]<0)
			{
				ny[i]+=mod;
			}
			ten[i]=(ten[i-1]*10)%mod;
		}
		for(ri i=1;i<=a;i++)
		{
			for(ri j=1;j<=b;j++)
			{
				register long long k=(C(i+j-2,i-1)*C(a+b-i-j,a-i))%mod;
				k*=(ten[a+b-i-j]*(c[i][j]-'0'))%mod;
				ans+=k%mod;
				ans%=mod;
			}
		}
		printf("%lld",ans);
		return 0;
	}
}
int main()
{
	freopen("grid.in","r",stdin);
	freopen("grid.out","w",stdout);
	scanf("%d%d",&a,&b);
	te1=true;
	for(ri i=1;i<=a;i++)
	{
		for(ri j=1;j<=b;j++)
		{
			scanf("%c",&c[i][j]);
			if((c[i][j]<'0'||c[i][j]>'9')&&c[i][j]!='+'&&c[i][j]!='*')
			{
				j--;
			}
			if(c[i][j]=='+'||c[i][j]=='*')
			{
				te1=false;
			}
		}
	}
	if(te1)
	{
		return task1::main();
	}
	dfs(1,1);
	printf("%lld",ans);
	return 0;
}

正解

观察一个表达式一定是由几个乘积项相加得来，即形如：\(a_1*a_2+a_3*a_4\) 的式子。应用数学定义：几个数相乘为一项，则表达式为一个多项式。考虑DP：设 \(dp_{i,j}\) 表示当前位置已经处理过的项的和，\(now_{i,j}\) 表示当前位置没有处理（即这个数字还没有结束）的数字之和，\(re_{i,j}\) 表示如果这里是数字，那么这个数字会被加几次。对于转移要分讨当前位置：

\[dp_{i,j}=\begin{cases}dp_{i-1,j}+dp_{i,j-1},s_{i,j}\neq+\\dp_{i-1,j}+dp{i,j-1}+now_{i-1}{j}+now_{i,j-1},s{i,j}=+\end{cases} \]

这个就比较显然了。对于不是 \(+\) 的情况，由于该项还没有结束，所以不会对 \(dp\) 数组产生额外贡献；对于是 \(+\) 的情况，该项结束，所以把之前没结束的答案累加。

\[now_{i,j}=\begin{cases}0,s_{i,j}\notin[0,9]\\now_{i-1,j}+now{i,j-1}\times10+re_{i-1,j}\times s_{i,j},s{i,j}=\in[0,9]\end{cases} \]

对于运算符的情况就相当显然了，这个数结束了，所以赋值为 \(0\)；对于数字的情况，此时 \(re\) 数组就派上用场了，这里的被累加几次是包括了之前乘积做的贡献的，所以直接乘就行。

\[re{i,j}=\begin{cases}C(i+j-2,i-1),s_{i,j}=+\\now_{i-1,j}+now{i,j-1},s{i,j}=*\\re_{i-1,j}+re{i,j-1},s_{i,j}\in[0,9]\end{cases} \]

对于 \(+\)，之前的项直接结束，没有乘积贡献，所以初始化为经过次数；对于 \(*\)，要乘上之前的数，所以累加 \(now\)；对于数字，没有额外贡献，直接把之前乘积的贡献累加。

注意最终答案为 \(dp_{a,b}+now_{a,b}\)。注意阶乘要预处理到 \(n+m\)。

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b;
const int mod=998244353;
char c[2002][2002];
long long dp[2002][2002],re[2002][2002],now[2002][2002],jc[4004],ny[4004];
void exgcd(int u,int v,long long &x,long long &y)
{
	if(!v)
	{
		x=1;
		y=0;
		return;
	}
	exgcd(v,u%v,y,x);
	y-=u/v*x;
}
il long long C(int x,int y)
{
	return (((jc[x]*ny[x-y])%mod)*ny[y])%mod;
}
int main()
{
	freopen("grid.in","r",stdin);
	freopen("grid.out","w",stdout);
	scanf("%d%d",&a,&b);
	for(ri i=1;i<=a;i++)
	{
		for(ri j=1;j<=b;j++)
		{
			scanf("%c",&c[i][j]);
			if((c[i][j]<'0'||c[i][j]>'9')&&c[i][j]!='+'&&c[i][j]!='*')
			{
				j--;
			}
		}
	}
	jc[0]=ny[0]=1;
	for(ri i=1;i<=a+b;i++)
	{
		jc[i]=(jc[i-1]*i)%mod;
		register long long j;
		exgcd(jc[i],mod,ny[i],j);
		while(ny[i]<0)
		{
			ny[i]+=mod;
		}
	}
	re[0][1]=1;
	for(ri i=1;i<=a;i++)
	{
		for(ri j=1;j<=b;j++)
		{
			switch(c[i][j])
			{
				case '+':
				{
					dp[i][j]=(dp[i-1][j]+dp[i][j-1]+now[i-1][j]+now[i][j-1])%mod;
					re[i][j]=C(i+j-2,i-1);
					now[i][j]=0;
					break;
				}
				case '*':
				{
					dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
					re[i][j]=(now[i-1][j]+now[i][j-1])%mod;
					now[i][j]=0;
					break;
				}
				default :
				{
					dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
					re[i][j]=(re[i-1][j]+re[i][j-1])%mod;
					now[i][j]=((now[i-1][j]+now[i][j-1])*10+re[i][j]*(c[i][j]-'0'))%mod;
					break;
				}
			}
		}
	}
	printf("%lld",(dp[a][b]+now[a][b])%mod);
	return 0;
}

标签：17,int,多校,long,考试题,2002,now,dp,define
From： https://www.cnblogs.com/ywhhdjser-97/p/18521132

相关文章

  • 『模拟赛』多校A层冲刺NOIP2024模拟赛17
    Rank一般A.网络签不上的签到题。首先考虑枚举路径的做法，如果先枚举再计算的话复杂度会是\(\mathcal{O(\binom{n+m-2}{n-1}(n+m))}\)的，稍微优化一点的过程中可以去掉后面的\((n+m)\)。考虑此时我们要记什么，首先遇到加号其前面的值\(z\)就确定了，若上个符号为乘号那么......
  • Navicat 17下载与安装
    1、安装包 Navicat17：链接：https://pan.quark.cn/s/c75e892c4705提取码：YvyFNavicat16：链接：https://pan.quark.cn/s/63c07b20ea7b提取码：B9ij2、安装教程（这里以安装Navicat17为例）1)       如之前已安装的需卸载当前Navicat，如未安装，直接双击无限试用Navicat.bat脚......
  • 2024.10.7 模拟赛 多校3
    模拟赛水题场。T1colorful签。感觉题挺好，正难则反，找出四角都相同的。在这两排有6个四角相同的矩形对于两排来说，我们只需要记录相同的列的个数，然后能直接算出个数。发现桶排每次清空复杂度太高，考虑每次只开一排的桶，只会有\(n\)个。code#include<bits/stdc++.h>u......
  • CesiumJS 案例 P17：添加文本、文本样式、删除文本、移动文本
    CesiumJSCesiumJSAPI：https://cesium.com/learn/cesiumjs/ref-doc/index.htmlCesiumJS是一个开源的JavaScript库，它用于在网页中创建和控制3D地球仪（地图）一、添加文本<!DOCTYPEhtml><htmllang="en"> <head> <metacharset="UTF-8"/> &l......
  • Unity6 URP17使用初探
    1.简介随着Unity6的发布，URP17也已经可以上手使用，相对旧的版本改动较大的是加入了RenderGraph、STP、Foveatedrendering、GPUResidentDrawer等功能，部分功能只需要开关参数即可使用，而GRD更像是Gpudriven管线下的SRPBatches升级，RenderGraph相较于HDRP之前使用的版本换了一套A......
  • COCI 17/18 Contest 6 Vrtić
    傻逼题。首先经典的结论是有很多个环，让每个环最小。显然将数组从小到大排序，然后每个环都是取连续一段一定最优，交换法容易证明。然后对于每个环内如何最优呢？假设我们有从小到大排序的数组\(a_{\{1,n\}}\)，最优一定是这样的：\[a_1,a_3,a_5,a_7...a_8,a_6,a_4,a_2\]就是左右填......
  • VMwareWorkstation pro 17安装Win11（亲测好用）
    1、安装包   我用夸克网盘分享了「Win11_23H2_China_GGK_Chinese_Simplified_x64v2.iso」，点击链接即可保存。打开「夸克APP」：链接：https://pan.quark.cn/s/817ccfc90f29提取码：pPn12、安装教程(基于WMwareworkstationpro17)1)       打开WMwareWorkstation，点击......
  • “范式杯”2023牛客暑期多校训练营1
    现在真的啥也不会了。。。D Chocolate首先考虑极端情况，1$\times$1的网格的话，先手必输。考虑其他情况，如果只能一个一个吃的话，显然是和奇偶相关的。对于先手来说，偶数自己赢，奇数是自己输。那么在矩阵中，虽然有着限制，但通过推小的例子可以发现，两方还是可以控制吃的数量的。对于先手......
  • VMwareWorkstation pro 17安装Win10(亲测好用)
    1、安装包 夸克网盘分享「cn_windows_10_consumer_editions_version_1909_x64_dvd_76365bf8.iso」链接：https://pan.quark.cn/s/175d19630109提取码：fSMs2、安装教程(基于WMwareworkstationpro17)1)       打开WMwareWorkstation，点击创建新的虚拟机  2)  ......
  • P1779 魔鬼杀手 题解&&思路
    P1779魔鬼杀手题解&&思路题目链接。分析题目性质我们发现假如有状态表示\(M\)个方案选或不选，那么这个状态有唯一确定的结果，即结果不会随着施法的顺序而改变。考虑\(dp.\)我们从题目出发，发现每个方案有单个攻击或者集体攻击，想一想从这个方面考虑。又由于每一个方案是可......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99