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分，静待讲评。