HDU-7111 Remove 单调队列优化DP 贪心

题意

给定一个素数集合\(P\) ，个数为\(n\)的石子堆，每次可以从\(P\)中取数\(p\)，使石子堆石子减少\(n \mod p\) 个，求最少的次数使得\(n\)减少到0

无法变为0输出0

求\(1 - N\)的所有答案

\(1 \leq N \leq 2e6\)

分析

容易发现是一道要求\(O(n)\)的题

每次操作变化相当于\(n \rightarrow n - n \ mod \ p\) ，可以得到递推式$dp[i] = max \lbrace dp[j] + 1\rbrace,j= n - n \ mod \ p $

这样直接转移是不方便的，如果考虑刷表，\(dp[i]\)能够转移的范围是\([i + 1,i + p - 1]\) 考虑"模"操作的意义

这个时候就只要找最大的\(p\)满足\(p | i\) 贪心转移就行(会覆盖掉其他)

注意到转移是取\(max\)的，因此答案非递减，可以用单调队列优化成\(O(n)\)，注意还要预处理出每个数最大的质因子，略卡常

代码

#include<bits/stdc++.h>
#define pii pair<ll,ll>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;

/*
inline ll rd(){
    ll x;
    scanf("%lld",&x);
    return x;
}*/

const int MOD = (int)1e9 + 7;

inline int mul(int a,int b){
    int res = (ll)a * b % MOD;
    if(res < 0) res += MOD;
    return res;
}

inline void add(int &a,int b){
    a += b;
    if(a >= MOD) a -= MOD;
}

inline void sub(int &a,int b){
    a -= b;
    if(a < 0) a += MOD;
}

const int maxn = 2e6 + 5;

int vis[maxn],pri[maxn],low[maxn],G[maxn];
int tot;


inline char nc() {
    static char buf[100000], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> inline void read(T &x) {
    x = 0; char c = nc();
    while (!isdigit(c)) c = nc();
    while (isdigit(c)) x = x * 10 + c - ‘0‘, c = nc();
}

inline void sieve(){
	tot = 1;
    low[1] = 1;
    for (int i = 2; i < maxn; i++){
        if (!vis[i]){
            pri[tot++] = i;
            low[i] = i;
            G[i] = i;
        }
        for (int j = 1; j <= tot && pri[j] * i < maxn; j++){
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                low[i * pri[j]] = low[i] * pri[j];
                if (i == low[i]) 
                    G[i * pri[j]] = pri[j];
                else
                    G[i * pri[j]] = max(G[i / low[i]] , G[pri[j] * low[i]]);
                break;
            }
            low[i * pri[j]] = pri[j];
            G[i * pri[j]] = max(G[i] , G[pri[j]]);
        }
    }
}




int p[maxn],dp[maxn],g[maxn];

int main(){
	sieve();
	int T;
	read(T);
	while(T--){
		int n,P;
		read(n);
		read(P);
		int mx = 0;
		VI ok((int)2e6 + 5);
		for(int i = 1;i <= P;i++)
			read(p[i]),mx = max(mx,p[i]),ok[p[i]] = 1;
		deque<pii> Q;
		for(int i = 1;i <= n;i++){
			if(i == 1) g[i] = -1;
			else g[i] = g[i / G[i]];
			if(ok[G[i]]) g[i] = max(g[i],G[i]);
			dp[i] = 0;
			while(!Q.empty() && Q.front().se < i) Q.pop_front();
			if(!Q.empty()) dp[i] = Q.front().fi;
			if(i < mx) dp[i] = 1;
			if(dp[i] && g[i] != -1)  {
				Q.push_back(make_pair(dp[i] + 1,i + g[i] - 1));
			}
		}
		ull ans = 0;
		for(int i = 1;i <= n;i++)
			ans = ans * 23333 + dp[i];
		printf("%llu\n",ans);
	}
}

HDU-7111 Remove 单调队列优化DP 贪心