NOIP2023模拟赛 种树

先整无脑爆搜

#include<iostream>
#include<algorithm>
#include<cstdio>

#define mod %998244353 
#define ll long long

const int N = 1e4 + 10;

using namespace std;

ll n, w;
ll p[N];
ll fy[N], nfy;
ll ans = -1;
int vis[N];

int getInShu(ll x)
{
	if (x >= N)
	{
		int cnt = 0;
		for (int i = 1; i <= x; i++)
		{
			if (x % i == 0) ++cnt;
		}
		return cnt;
	}
	if (vis[x]) return vis[x];
	int cnt = 0;
	for (int i = 1; i <= x; i++)
	{
		if (x % i == 0) ++cnt;
	}
	return vis[x] = cnt;
}

void setFertilizer()
{
	for (int i = 1; i <= w; i++)
	{
		if (w % i == 0)
		{
			fy[++nfy] = i;
		}
	}
}

void dfs(ll sum, ll w, ll now)
{
	if (now == n + 1)
	{
		sum = sum mod;
		ans = max(ans, sum);
		return ;
	}
	for (int i = 1; i <= nfy && fy[i] <= w; i++)
	{
		dfs((sum * getInShu(p[now] * fy[i]))mod , w / fy[i], now + 1);
	}
	dfs((sum * getInShu(p[now]))mod, w, now + 1);
}

int main()
{
	cin >> n >> w;
	for (int i = 1; i <= n; i++)
	{
		cin >> p[i];
	}
	setFertilizer();
	dfs(1, w, 1);
	cout << ans;
	return 0;
}

没啥好说的，就过第一个样例。

看起来很像DP，于是开始推状态转移方程。

DP尝试

状态方程

\(F[i][j]\)为前\(i\)个树木，肥料剩余\(i\)时的最优覆盖距离。

转移方程

肯定是从\(F[i][j * k]\)推过来，但是如果无脑枚举\(k\)，第二个样例都过不了。

我发现\(j*k\)必须得是\(w\)的因数，所以第三层循环没必要直接枚举\(k\)，而是枚举\(j*k\)，即\(w\)的因数，这样大大减少了时间复杂度。

F[0][w] = 1;
for (int i = 1; i <= n; i++)
{
	for (int j = 1; j <= nfy; j++)
	{
		F[i][fy[j]] = (F[i - 1][fy[j]] mod) * (getInShu(p[i]) mod);
		F[i][fy[j]] = F[i][fy[j]] mod;
		for (int k = j + 1; k <= nfy; k++)
		{
			if (fy[k] % fy[j] == 0)
			{
				ll temp = fy[k] / fy[j];
				F[i][fy[j]] = max(((F[i - 1][fy[k]]mod) * (getInShu(p[i] * temp)))mod, F[i][fy[j]]);
				F[i][fy[j]] = F[i][fy[j]] mod;
			}
		}
	}
}

然而第二个样例还是跑得慢，只好从取因数的函数来优化。

这里我发现基础上的一个重要漏洞。

我忘记了求一个数的因子数的\(O(\sqrt n)\)方法。

即从一枚举至\(\sqrt n\)即可，因为后面的因子数等同于前面的因子数。

ll getInShu(ll n)
{
    ll ans = 0;
    for(int i=1;i*i<=n;i++)
    {                      
        if(n % i == 0)
        {
            if(n / i == i)
            {          
                ans ++;   
            }   
            else 
            {
            	ans += 2;   	
			}
        }
 	}
	return ans;
}

终于第二个样例短时间内跑过了，然而第三个样例即超时，又答案错误。

感觉时取模和最大值的处理有问题，但是一直改不出来，比赛完发现还mle了，50分，静待讲评。