T3 题

题解

解题思路

一看这题名字挺奇怪，网上一搜，是一套题（简，单，题）好像时学长出的，因为简太水了，就被教练踢掉了。

看见这个题的第一思路先是DP，随后想了想排列组合好像更好一些，最后一看时间不够了，先打了一个样例（5pts）然后就是大暴力了。

下面就是正解了：

typ=0

枚举横向移动了多少步。

横向移动i步时(为了存在合法解,i必须是偶数)，纵向的显然就是n-i了，横向方案数为\(C_i^{\frac{i}{2}}\)(来回随便走i步里面选\(\dfrac{i}{2}\)步

纵向就是\(C_{n-i}^{\frac{n-i}{2}}\)，和横向的式子差不多。

然后从n步里选i步，乘上一个\(C_n^i\)就好了。

typ=1

从\(\dfrac{n}{2}\)个-1和\(\dfrac{n}{2}\)个1里排列一下，这不就是个Catalan序列吗 （虽然我是现学的） 。

typ=2

这里就用上DP了

f[i]表示走了i步回到原点的方案数（中途可能回到过原点多次

枚举第一次回到原点时走过的步数j(为了存在合法解,j为偶数)

则此时方案数为\(f[i-j]*Catalan(j/2-1)\)

第 j 步第一次回到原点，之后可能有多次再次回原点\(f[i-j]\)，

在计算这 j 步时，我们必须保证 j 步中不回原点，所以\(Catalan(j/2-1)\)

这个 -1 就是保证栈不为空 (左右移动可以看作栈)

typ=3

与typ=1的做法有一点类似。

枚举横向移动了多少步

横向移动 i 步时(为了存在合法解, i 必须是偶数)

方案数为\(C_n^i*Catalan(\dfrac{i}{2})*Catalan(\dfrac{n-i}{2})\)

代码优化

因为要取模，就一定要计算 inv ，又可以发现我们用的所有inv都是阶乘，因此我们可以直接把inv初始化阶乘。对于其他的快速幂一下就好了。

code

#include
#define int long long
using namespace std;
const int N=1e5+10,mod=1e9+7;
int n,ans,task,f[N],jc[N<<1],inv[N<<1];
void get_Jc()
{
	jc[0]=1;
	for(int i=1;i<(N<<1);i++)
		jc[i]=jc[i-1]*i%mod;
}
void get_Inv()
{
	inv[0]=inv[1]=1;
	for(int i=2;i<(N<<1);i++)
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1;i<(N<<1);i++)
		inv[i]=inv[i]*inv[i-1]%mod;
}
int ksm(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1)
			ans=ans*x%mod;
		y>>=1;
		x=x*x%mod;
	}
	return ans;
}
int C(int i,int j)
{
	if(i>j)
		return 0;
	if(i==0||j==0)
		return 1;
	return jc[j]%mod*inv[i]%mod*inv[j-i]%mod;
}
int Catalan(int x)
{
	return C(x,x<<1)%mod*ksm(x+1,mod-2)%mod;
}
#undef int
int main()
{
	#define int register long long
	#define ll long long
	scanf("%lld%lld",&n,&task);
	get_Jc();
	get_Inv();
	if(task==0)
	{
		for(int i=0;i<=n;i+=2)
			ans=(ans+C(i,n)%mod*C(i>>1,i)%mod*C((n-i)>>1,n-i)%mod)%mod;
	}
	else	if(task==1)
		ans=Catalan(n>>1)%mod;
	else	if(task==2)
	{
		n>>=1;
		f[0]=1;
		f[1]=4;
		for(int i=2;i<=n;i++)
			for(int j=1;j<=i;j++)
				f[i]=(f[i]+4*f[i-j]%mod*Catalan(j-1)%mod)%mod;
		ans=f[n]%mod;
	}
	else
	{
		for(int i=0;i<=n;i+=2)
			ans=(ans+C(i,n)*Catalan(i>>1)%mod*Catalan((n-i)>>1)%mod)%mod;
	}
	printf("%lld",ans%mod);
	return 0;
}

T4 大佬

题解

解题思路

暴力打法

这个题一看题面和题目，令人畏惧，但是细细读题后可以发现：好像就是个深搜，再一看数据范围，直接开码 （然后我们愉快的TLE40pts）。

code

正解

有一个十分重要的地方就是怼大佬与活下来是两个事。

然后我们就可以分别运算了：

DP最多天数

类似于背包 DP ，利用前面的更新现在的直接 +1 就好了，最后对于所有的 dp 值取 mod ，求出最大天数就好了。

void get_Day()
{
	for(int i=1;i<=n;i++)//枚举天数
		for(int j=a[i];j<=mc;j++)//枚举自己的自信
		{
			dp[i][j-a[i]]=max(dp[i][j-a[i]],dp[i-1][j]+1);
			int temp=min(mc,j-a[i]+w[i]);
			dp[i][temp]=max(dp[i][temp],dp[i-1][j]);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=mc;j++)
			day=max(day,dp[i][j]);
}

BFS求二元组(d,f)

二元组 \((d,f)\) 表示第 d 天 \((d 并且此时的 \(F=f\) ，运算的过程中需要去重，用 Hash 或者 map 可以很好的解决这个问题这里给出 map 做法。

队列的数组三维分别表示: 天数， L ，F，对于大于上面求的D，直接跳过，其他的枚举并更新 L 和 F 入队就好了，然后用一个 S1 数组储存所有的二元组。

void get_Dui()
{
	int head=1,tail=0;
	q[++tail]=make_pair(1,make_pair(0,1));
	a1[make_pair(1,1)]=1;
	while(head<=tail)
	{
		pair > temp;
		temp=q[head++];
		if(temp.first>=day)
			continue;
		int da=temp.first,l=temp.second.first,f=temp.second.second;
		q[++tail]=make_pair(da+1,make_pair(l+1,f));
		a1[make_pair(da+1,f)]=1;
		if(l>1&&l*f<=mxc&&!a1[make_pair(da+1,l*f)])
		{
			int new_f=l*f;
			q[++tail]=make_pair(da+1,make_pair(l,new_f));
			a1[make_pair(da+1,new_f)]=1;
			s1[++cnt]=make_pair(da+1,new_f);
		}
	}
}

算法主体

显然，可以怼没大佬自信值的情况有三种：

1. 一次都不怼，仅用 1 操作消磨他并且 \(C_i\le D\) 。
2. 只怼一次大佬，剩下的拿 1 来凑，这是需要有一个二元组 \((d,f)\) 满足 \(f\le C_i\) ,并且 \(f+D-d\ge C_i\)
3. 怼两次大佬，两次分别为 \((d_1,f_1)\) 和 \((d_2,f_2)\) 并且满足\(f_1+f_2 \le C_i\) 和 \(f_1+f_2-d_1-d_2+D \ge C_i\)。
   诚然，对于同一个 \(f\) 只有最小的 \(d\) 是最优的，因此我们只需要对于每一个 \(f\) 保存最小的 \(d\) 就好了， map 有一次正好的满足了这个条件（那还用Hash干嘛）,然后我们双向指针扫一下，再判断一小下就可以过掉此题了。

题目对于各项要求比较严格，具体实现细节见代码。

code

#include
#define int long long
using namespace std;
const int N=1e2+10,M=3e6+10,INF=1e9;//注意数组大小 
int n,m,mc,mxc,a[N],w[N],c[25];
int tot,cnt,day,dp[N][N];
pair s1[M],s2[M];
pair > q[M];//day l f
map,int> a1;
map a2;
void get_Day()//求出最大的day 
{
	for(int i=1;i<=n;i++)//类似于背包dp 
		for(int j=a[i];j<=mc;j++)
		{
			dp[i][j-a[i]]=max(dp[i][j-a[i]],dp[i-1][j]+1);
			int temp=min(mc,j-a[i]+w[i]);
			dp[i][temp]=max(dp[i][temp],dp[i-1][j]);
		}
	for(int i=1;i<=n;i++)//取最值 
		for(int j=1;j<=mc;j++)
			day=max(day,dp[i][j]);
}
void get_Dui()//求二元组(d,f) 
{
	int head=1,tail=0;
	q[++tail]=make_pair(1,make_pair(0,1));
	a1[make_pair(1,1)]=1;
	while(head<=tail)
	{
		pair > temp;
		temp=q[head++];
		if(temp.first>=day)
			continue;
		int da=temp.first,l=temp.second.first,f=temp.second.second;
		q[++tail]=make_pair(da+1,make_pair(l+1,f));
		a1[make_pair(da+1,f)]=1;
		if(l>1&&l*f<=mxc&&!a1[make_pair(da+1,l*f)])
		{
			int new_f=l*f;
			q[++tail]=make_pair(da+1,make_pair(l,new_f));
			a1[make_pair(da+1,new_f)]=1;
			s1[++cnt]=make_pair(da+1,new_f);
		}
	}
}
bool comp(pair x,pair y)//重新定义sort排序规则 
{
	if(x.second==y.second)
		return x.first=1;i--)
		{
			int da=s2[i].first,f=s2[i].second;
			if(f<=c[k]&&day-da+f>=c[k])
			{
				vis=true;
				break;
			}
			int maxn=-INF;
			while(pos<=tot&&f+s2[pos].second<=c[k])
			{
				maxn=max(maxn,s2[pos].second-s2[pos].first);//如果是int，应该把+f卸载循环里不然会爆掉 
				pos++;
			}
			if(f-da+maxn>=c[k]-day)//判断符合条件 
			{
				vis=true;
				break;
			}
		}
		printf("%d\n",vis?1:0);
	}
	return 0;
}