B 数学 分解质因数k n m o d n 0 k^n\mod n0knmodn0k只要包含n的所有质因数就好若n p 1 t 1 , k n p 1 n , 必有 n ≥ t 1 log p 1 n np_1^{t_1},k^np_1^n,必有n\geq t_1\log_{p_1}nnp1t1,knp1n,必有n≥t1logp1nvoidsolve(){intn;cinn;inttpn;mapint,intm;forr(i,2,sqrt(n)){intfg0;while(tp%i0){fg1;tp/i;m[i];}}m[tp];intans1;for(auto[p,x]:m){ans*p;}coutansendl;}C 贪心 排序 STL参考_olone的题解题意给一系列数组每个数组逆序后从前到后拼接数组每种数只输出最前面的一个让输出字典序最小直接考虑逆序数组最先想到的就是每次把数组字典序小的放前面直接排序如果像121999和122345应该122345放前面但是排序后121999在前面小的数会把大的数拉到前面去所以每次选最优数组不同数组比较应该剔除前面出现过的数已经输出的数同一个数组相邻重复的数作用相当于合为一个数voidsolve(){intn;cinn;vectorvinta(n1);forr(i,1,n){intl;cinl;intprex-1;forr(j,1,l){intx;cinx;if(xprex)continue;//相邻重复 不会有贡献prexx;a[i].push_back(x);}reverse(a[i].begin(),a[i].end());// 数组越后面的 在ans里越靠前}vectorintans;mapint,intvis;priority_queuevint,vectorvint,greatervintq;forr(i,1,n)q.push(a[i]);while(q.size()){vint qvq.top();q.pop();for(autox:qv){if(!vis[x])ans.push_back(x),vis[x]1;}priority_queuevint,vectorvint,greatervinttp_q;//在每个数组里剔除小的/已经放入ans的数while(q.size()){qvq.top();q.pop();vint newv;for(autox:qv)if(!vis[x])newv.push_back(x);tp_q.push(newv);}qtp_q;//priority_queue可以直接赋值}for(autox:ans)coutx ;coutendl;/*以下是一开始的wa代码 没有剔除已经放过了数 会影响之后的选择 sort(a.begin()1,a.end()); // forr(i,1,n){for(auto x:a[i])coutx ;coutendl;} vectorintfg(n1,0); mapint,intpos,jud; forr(i,1,n){ int la[i].size(); forr(j,0,l-1) if(!pos.count(a[i][j])||jud[a[i][j]]j){ pos[a[i][j]]i; jud[a[i][j]]j; } } for(auto [num,p]:pos){ // coutnum pendl; if(fg[p])continue; for(auto x:a[p]){ ans.push_back(x); fg[p]1; } } forr(i,1,n){ if(fg[i])continue; for(auto x:a[i]){ ans.push_back(x); } } setintvis; // coutans; for(auto x:ans){ if(!vis.count(x)){ vis.insert(x); coutx ; } // coutx ; } coutendl; */}D 分治题意一个排列数组每个连续三元组中间的数不是三元组的最大值这个数组是酷的。每次可以选择不满足条件的三元组删去两端任一数。由题意可知酷数组每个连续三元组最大值位于两端。让一个数组变酷至少要把最大值mx一边的数全删去mx位于边上mx一定可以进行这样的操作剩下另一边的数成为一个新的数组性质相同可以做和原数组相同的处理最小到三元组voidsolve(){intn;cinn;vectorinta(n1),pos(n1);forr(i,1,n){cina[i];pos[a[i]]i;}//st表找区间最大值vectorvintst(n1,vectorint((int)log2(n)1));forr(i,1,n)st[i][0]a[i];for(intj1;(1j)n;j){for(inti1;i(1j)-1n;i){st[i][j]max(st[i][j-1],st[i(1(j-1))][j-1]);}}autofindmx[](intl,intr)-int{intlenlog2(r-l1);intmxmax(st[l][len],st[r-(1len)1][len]);returnpos[mx];};autodiv[](autodiv,intl,intr)-int{if(r-l13)return0;intxfindmx(l,r);returnmin(r-xdiv(div,l,x-1),x-ldiv(div,x1,r));// 把最大值单边删去};coutdiv(div,1,n)endl;/* 一开始想用LIS vectorintdp; dp.push_back(a[1]); forr(i,2,n){ if(a[i]mx)break; if(dp.back()a[i]){ dp.push_back(a[i]); }else{ int posupper_bound(dp.begin(),dp.end(),a[i])-dp.begin(); dp[pos]a[i]; } } int ans1dp.size(); forr(i,1,n){ if(dp[0]a[i])break; if(dp[0]a[i]){ ans1; break; } } dp.clear(); dp.push_back(a[1]); forr(i,2,n){ if(dp.back()a[i]){ dp.push_back(a[i]); }else{ int posupper_bound(dp.begin(),dp.end(),a[i],greaterint())-dp.begin(); dp[pos]a[i]; } } int ans2dp.size(); reforr(i,1,n){ if(dp[ans2-1]a[i])break; if(dp[ans2-1]a[i]){ ans2; break; } }coutans; coutn-max(ans1,ans2)endl; */}还有一种笛卡尔树的做法 有空再学
Codeforces Round 1083 (Div. 2)vp补题
B 数学 分解质因数k n m o d n 0 k^n\mod n0knmodn0k只要包含n的所有质因数就好若n p 1 t 1 , k n p 1 n , 必有 n ≥ t 1 log p 1 n np_1^{t_1},k^np_1^n,必有n\geq t_1\log_{p_1}nnp1t1,knp1n,必有n≥t1logp1nvoidsolve(){intn;cinn;inttpn;mapint,intm;forr(i,2,sqrt(n)){intfg0;while(tp%i0){fg1;tp/i;m[i];}}m[tp];intans1;for(auto[p,x]:m){ans*p;}coutansendl;}C 贪心 排序 STL参考_olone的题解题意给一系列数组每个数组逆序后从前到后拼接数组每种数只输出最前面的一个让输出字典序最小直接考虑逆序数组最先想到的就是每次把数组字典序小的放前面直接排序如果像121999和122345应该122345放前面但是排序后121999在前面小的数会把大的数拉到前面去所以每次选最优数组不同数组比较应该剔除前面出现过的数已经输出的数同一个数组相邻重复的数作用相当于合为一个数voidsolve(){intn;cinn;vectorvinta(n1);forr(i,1,n){intl;cinl;intprex-1;forr(j,1,l){intx;cinx;if(xprex)continue;//相邻重复 不会有贡献prexx;a[i].push_back(x);}reverse(a[i].begin(),a[i].end());// 数组越后面的 在ans里越靠前}vectorintans;mapint,intvis;priority_queuevint,vectorvint,greatervintq;forr(i,1,n)q.push(a[i]);while(q.size()){vint qvq.top();q.pop();for(autox:qv){if(!vis[x])ans.push_back(x),vis[x]1;}priority_queuevint,vectorvint,greatervinttp_q;//在每个数组里剔除小的/已经放入ans的数while(q.size()){qvq.top();q.pop();vint newv;for(autox:qv)if(!vis[x])newv.push_back(x);tp_q.push(newv);}qtp_q;//priority_queue可以直接赋值}for(autox:ans)coutx ;coutendl;/*以下是一开始的wa代码 没有剔除已经放过了数 会影响之后的选择 sort(a.begin()1,a.end()); // forr(i,1,n){for(auto x:a[i])coutx ;coutendl;} vectorintfg(n1,0); mapint,intpos,jud; forr(i,1,n){ int la[i].size(); forr(j,0,l-1) if(!pos.count(a[i][j])||jud[a[i][j]]j){ pos[a[i][j]]i; jud[a[i][j]]j; } } for(auto [num,p]:pos){ // coutnum pendl; if(fg[p])continue; for(auto x:a[p]){ ans.push_back(x); fg[p]1; } } forr(i,1,n){ if(fg[i])continue; for(auto x:a[i]){ ans.push_back(x); } } setintvis; // coutans; for(auto x:ans){ if(!vis.count(x)){ vis.insert(x); coutx ; } // coutx ; } coutendl; */}D 分治题意一个排列数组每个连续三元组中间的数不是三元组的最大值这个数组是酷的。每次可以选择不满足条件的三元组删去两端任一数。由题意可知酷数组每个连续三元组最大值位于两端。让一个数组变酷至少要把最大值mx一边的数全删去mx位于边上mx一定可以进行这样的操作剩下另一边的数成为一个新的数组性质相同可以做和原数组相同的处理最小到三元组voidsolve(){intn;cinn;vectorinta(n1),pos(n1);forr(i,1,n){cina[i];pos[a[i]]i;}//st表找区间最大值vectorvintst(n1,vectorint((int)log2(n)1));forr(i,1,n)st[i][0]a[i];for(intj1;(1j)n;j){for(inti1;i(1j)-1n;i){st[i][j]max(st[i][j-1],st[i(1(j-1))][j-1]);}}autofindmx[](intl,intr)-int{intlenlog2(r-l1);intmxmax(st[l][len],st[r-(1len)1][len]);returnpos[mx];};autodiv[](autodiv,intl,intr)-int{if(r-l13)return0;intxfindmx(l,r);returnmin(r-xdiv(div,l,x-1),x-ldiv(div,x1,r));// 把最大值单边删去};coutdiv(div,1,n)endl;/* 一开始想用LIS vectorintdp; dp.push_back(a[1]); forr(i,2,n){ if(a[i]mx)break; if(dp.back()a[i]){ dp.push_back(a[i]); }else{ int posupper_bound(dp.begin(),dp.end(),a[i])-dp.begin(); dp[pos]a[i]; } } int ans1dp.size(); forr(i,1,n){ if(dp[0]a[i])break; if(dp[0]a[i]){ ans1; break; } } dp.clear(); dp.push_back(a[1]); forr(i,2,n){ if(dp.back()a[i]){ dp.push_back(a[i]); }else{ int posupper_bound(dp.begin(),dp.end(),a[i],greaterint())-dp.begin(); dp[pos]a[i]; } } int ans2dp.size(); reforr(i,1,n){ if(dp[ans2-1]a[i])break; if(dp[ans2-1]a[i]){ ans2; break; } }coutans; coutn-max(ans1,ans2)endl; */}还有一种笛卡尔树的做法 有空再学
