觅知网免费素材图库,镇江网站建设优化,长春专业企业网站建设价格,网站搭建好显示建设中开学了#xff0c;感觉没时间打cf了#xff0c;上课听不懂#xff0c;而且一直在忙转班的事情~~ 下周就要回学校了开心
昨天卡C题太久了#xff0c;一直在想lcm的性质#xff0c;还好最后回头了#xff0c;当成构造题做了#xff0c;瞎搞了搞就出来了#xff0c;然后看…开学了感觉没时间打cf了上课听不懂而且一直在忙转班的事情~~ 下周就要回学校了开心
昨天卡C题太久了一直在想lcm的性质还好最后回头了当成构造题做了瞎搞了搞就出来了然后看D由于没有看榜就硬着头皮看D发下没思路看下榜单发下都在搞E然后转头搞E忘了完全平方的性质就GG了~ E1. Square-free division (easy version)
不难知道xp1α1p2α2…pnαnxp_1^{\alpha_1}p_2^{\alpha_2}\dots p_n^{\alpha_n}xp1α1p2α2…pnαnyp1β1p2β2…pmβmyp_1^{\beta_1}p_2^{\beta_2}\dots p_m^{\beta_m}yp1β1p2β2…pmβm 设 axp1α1%2p2α2%2…pnαn%2a_xp_1^{\alpha_1\%2}p_2^{\alpha_2\%2}\dots p_n^{\alpha_n\%2}axp1α1%2p2α2%2…pnαn%2ayp1β1%2p2β2%2…pmβm%2a_yp_1^{\beta_1\%2}p_2^{\beta_2\%2}\dots p_m^{\beta_m\%2}ayp1β1%2p2β2%2…pmβm%2 如果xyxyxy是完全平方数一定有axaya_xa_yaxay于是开个数组贪心的选即可。
时间复杂度O(namaxn)O(n\sqrt{a_{\max}}n)O(namaxn) 裸的分解质因数TLE一个点加了个优化质数直接不分解然后过了其实感觉记忆化一下应该也能过。
// 1996 ms
#includeiostream
using namespace std;
constexpr int N200010;
int n,k,a[N],pre[10000010];
int prime[10000010],cnt;
bool is[10000010];
void init(int n)//筛质数
{for(int i2;in;i){if(!is[i]) prime[cnt]i;for(int j1;prime[j]n/i;j){is[prime[j]*i]1;if(i%prime[j]0) break;}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T1;cinT;init(10000000);while(T--){cinnk;for(int i1;in;i){a[i]1;int x;cinx;if(!is[x]) {a[i]x;continue;}//小优化for(int j2;jx/j;j)if(x%j0){int s0;while(x%j0) x/j,s;if(s1) a[i]*j; }if(x1) a[i]*x;}int last0,res0;for(int i1;in;i){if(pre[a[i]]last){for(int jlast;ji;j) pre[a[j]]0;res;lasti;}pre[a[i]]i;}for(int i1;in;i) pre[a[i]]0;coutres\n;}return 0;
}其实感觉上述代码仍然能被卡TEL时间复杂度主要在求xxx的axa_xax上学习了Heltion的代码发下可以在筛法中做文章 设axf(x)a_xf(x)axf(x)
如果fi%pj0f_i\%p_j0fi%pj0说明fif_ifi里面有一个pjp_jpjfpj×if_{p_j×i}fpj×i则有两个pjp_jpj于是fpj×ifi/pjf_{p_j×i}f_i/p_jfpj×ifi/pj 如果fi%pj≠0f_i\%p_j\ne0fi%pj0说明fif_ifi里面没有pjp_jpj于是fpj×ifi×pjf_{p_j×i}f_i×p_jfpj×ifi×pj 按照上述递推即可。 时间复杂度O(amaxn)O(a_{\max}n)O(amaxn)
//311 ms
#includeiostream
using namespace std;
constexpr int N200010;
int n,k;
int a[N];
int pre[10000010];
int prime[10000010],cnt;
bool is[10000010];
int f[10000010];
void init(int n)
{f[1]1;for(int i2;in;i){if(!is[i]) prime[cnt]i,f[i]i;for(int j1;prime[j]n/i;j){is[prime[j]*i]1;if(f[i]%prime[j]) f[i*prime[j]]f[i]*prime[j];elsef[i*prime[j]]f[i]/prime[j];if(i%prime[j]0) break;}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T1;cinT;init(10000000);while(T--){cinnk;for(int i1;in;i){a[i]1;int x;cinx;a[i]f[x];}int last0,res0;for(int i1;in;i){if(pre[a[i]]last){for(int jlast;ji;j) pre[a[j]]0;res;lasti;}pre[a[i]]i;}for(int i1;in;i) pre[a[i]]0;coutres\n;}return 0;
}
E2. Square-free division (hard version)
10710^7107以内质数个数是664579664579664579不难得出只要你改变一个数一定能改变成一个数和任意数组的数的积不是完全平方数。
共有26645792^{664579}2664579选择只要挑一个变成当前没有的即可。
设计dp 状态表示fi,jf_{i,j}fi,j表示考虑前iii个数操作了jjj次分成的最小段数。 状态转移考虑第iii个数和哪些数划分到一组。
比如最后一组是[L,i][L,i][L,i]表明数组[L,i][L,i][L,i]的数两两相乘不是完全平方数根据第一问转化后即[L,i][L,i][L,i]的数都不相同。只需要求出需要操作多少次能使得[L,i][L,i][L,i]数都不相同即可。
一个常用的trick就是记录这个数前一个和它相同数的位置prei\text{pre}_iprei不难得出[L,i][L,i][L,i]操作次数为∑jLi1(L≤prej≤i)−1\sum_{jL}^{i}1(L \leq \text{pre}_j\leq i)-1∑jLi1(L≤prej≤i)−1即可转移。
下面代码效仿Heltion的trick非常巧妙用一个set维pre数组。最后一组为[x1,i][x1,i][x1,i]然后枚举操作次数转移即可。注意边界情况也就是最后一组为[1,i][1,i][1,i]的情况。
#includeset
#includeiostream
#includealgorithm
using namespace std;
constexpr int N200010;
int n,k;
int a[N];
int pre[N];
int mp[10000010];
int prime[10000010],cnt;
bool is[10000010];
int f[10000010];
int dp[N][22];
void init(int n)
{f[1]1;for(int i2;in;i){if(!is[i]) prime[cnt]i,f[i]i;for(int j1;prime[j]n/i;j){is[prime[j]*i]1;if(f[i]%prime[j]) f[i*prime[j]]f[i]*prime[j];elsef[i*prime[j]]f[i]/prime[j];if(i%prime[j]0) break;}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T1;cinT;init(10000000);while(T--){cinnk;for(int i1;in;i){cina[i];a[i]f[a[i]];}for(int i1;in;i){pre[i]mp[a[i]];mp[a[i]]i;}for(int i1;in;i) for(int j0;jk;j) dp[i][j]n;dp[0][0]0;setint,greaterint s;for(int i1;in;i){if(pre[i]) s.insert(pre[i]);for(int j0;jk;j) dp[i][j]dp[i-1][j]1;int c0;for(int x:s){if(ck) break;for(int jc;jk;j)dp[i][j]min(dp[i][j],dp[x][j-c]1);c;}if((int)s.size()k) dp[i][s.size()]1;}cout*min_element(dp[n],dp[n]1k)\n;for(int i1;in;i) mp[a[i]]0;}return 0;
}
