企业官网建设流程全解析

C

贪心

N个物品，每个都有颜色和价值，要求选K个物品，至少M种颜色，使得价值和最大？

贪心的想，先凑齐M种颜色，然后剩下的不受颜色的约束，挑价值最大的。凑齐M种颜色的过程，可以对于每种颜色选出价值最大的，然后对于这些物品，颜色是互异的，选出价值最大的M个。对于这M个，标记为已选，然后把未标记的拿出来根据价值排序，选出最大的K-M个。

voidsolve(){intn,m,k;cin>>n>>k>>m;map<int,int>mp;vic(n+1),v(n+1);rep(i,1,n){cin>>c[i]>>v[i];if(v[i]>v[mp[c[i]]]){mp[c[i]]=i;}}vivis(n+1);vi a;for(auto[k,v]:mp){a.push_back(v);}sort(a.begin(),a.end(),[&](intx,inty){returnv[x]>v[y];});intans=0;rep(i,0,m-1){ans+=v[a[i]];vis[a[i]]=1;}// cout<<ans<<'\n';vi b;rep(i,1,n){if(!vis[i]){b.push_back(v[i]);}}ranges::sort(b);k-=m;while(k--){ans+=b.back();b.pop_back();}cout<<ans;}

D

枚举 扫描线 前缀和 时间戳

一个矩阵，问多少个子矩阵元素和恰好为K？n,m=500，那么有一个经典的O(n3)O(n^3)O(n3)做法，枚举子矩阵的x维度区间[i,j][i,j][i,j]，这是O(n2)O(n^2)O(n2)，然后看成一个一维数组，里面每个元素都是原数组上j−i+1j-i+1j−i+1个元素的和，于是问题转化成，问一个一维数组多少个区间元素和等于K，这可以map维护前缀和计数。

然后发现map被卡常了，换成静态数组+时间戳，时间很富裕。

voidsolve(){intn,m,K;cin>>n>>m>>K;vvia(n+1,vi(m+1));inttot=0;rep(i,1,n){rep(j,1,m){charc;cin>>c;a[i][j]=c-'0';if(a[i][j])tot++;}}intans=0;vicnt(tot+10),t(tot+10);inttime=0;autoadd=[&](inti,intv)->void{if(t[i]==time){cnt[i]++;}else{t[i]=time;cnt[i]=1;}};autoask=[&](inti)->int{if(t[i]==time){returncnt[i];}else{cnt[i]=0;t[i]=time;return0;}};rep(i,1,n){vicur(m+1);rep(j,i,n){add(0,1);intpre=0;rep(k,1,m){cur[k]+=a[j][k];pre+=cur[k];if(pre>=K)ans+=ask(pre-K);add(pre,1);}time++;}}cout<<ans;}

E

思维 数据结构

n*n的网格上，q=1e5次操作，每次染黑一行，或者染白一列。n=1e5，问每一步操作后的黑色格子数？

暴力计算黑色不可行，考虑每一次操作对黑色格子的改变量。

• 对于染黑一行，如果这是这一行第一次染黑，增加n个黑色，如果之前已经染黑了，这次能染黑的，只有在上次染黑，到这次之间，被染白的位置。于是计算从上次染黑，到这次之间，染白一列的操作次数。注意多次染白同一列也只计算一次，所以实际要求的是上次染黑到现在的不同列染白次数。
• 对于染白一列，类似，但有不同。如果之前染白过这一列，这次能染白的就是上次染白到现在，中间染黑的不同行的个数。如果之前没染白过，这次能染白的就是从最开始到现在，染黑的不同行数。

这里需要维护每一行最后一次染黑的时间，每一列最后一次染白的时间。这静态数组维护即可。然后还要求一个时间段内，染黑的不同行数，染白的不同列数。如果不考虑去重，前缀和就可以。考虑去重，不能让同一行产生多次贡献，每次操作一行，除了增加这一次的贡献，还要取消这一行之前的贡献，也就是让一行的贡献始终不超过1

想实现这点，考虑把前缀和换成树状数组，树状数组可以看成一个动态前缀和，不仅支持增加，还支持删除。横轴是操作的时间，每次对于染黑一行，假设当前时间t,上一次操作这一行的时间是pre，执行add(t,1),add(pre,-1)。查询的用法和前缀和一样，直接查区间和。

voidsolve(){intn,q;cin>>n>>q;viprex(n+1),prey(n+1);FenwickTreetx(q+10),ty(q+10);intans=0;rep(i,1,q){intop,x;cin>>op>>x;if(op==1){if(prex[x]==0){ans+=n;}else{ans+=ty.rangeQuery(prex[x]+1,i);}if(prex[x])tx.update(prex[x],-1);tx.update(i,1);prex[x]=i;}else{if(prey[x]==0){ans-=tx.query(i);}else{ans-=tx.rangeQuery(prey[x]+1,i);}if(prey[x])ty.update(prey[x],-1);ty.update(i,1);prey[x]=i;}cout<<ans<<'\n';}}

F

数论 枚举/记忆化搜索

对于N=1e10，一个分拆序列是，找到一个不含重复元素的序列，乘起来等于N。现在要计算所有分拆序列的元素和。注意这是序列，也就是相同元素不同排列视为不同方案。

对于1，乘上不影响结果，企鹅最多出现一次，可以单独处理。假设当前一个分拆方案有cnt个数，和为sum，那么不加入1是一类方案，答案是(cnt)!乘sum，也就是这些元素的全排列，加入1是另一类，(cnt+1)!×(sum+1)，也就是加入1之后再全排列。

接下来不考虑1，只要能求出所有组合方案的(cnt,sum)，就可以计算答案了。这会很多吗？注意到由于(14)!>1e10，N=1e10的不同质因子个数不会超过14，考虑到相同质因子，也是O(log⁡N)O(\log N)O(logN)量级的。

拆成一个序列，等价于把这个质因子集合，拆成若干个互不相交的子集，这是经典的贝尔数问题，B(14)左右的贝尔数不会太大，这里实际的肯定会多一点，因为14是对于不同质因子来说的，一个质因子可能出现多次。但是从另一方面讲，也不会那么多，因为不能包含相同元素，也就是有一些分拆子集，会产生相同元素

大胆guess一下，还是可以通过。尝试做一些剪枝。首先暴力O(n)O(\sqrt n)O(n​)的到所有因子，然后dfs枚举这个因子集合的一个子集，记录子集大小cnt,元素和sum，并且维护当前剩余待拆分的乘积，边界是剩余乘积为1，那么根据前面的讨论，计算加不加入1，对答案的贡献。每一层接下来要选的枚举因子，必须能整除剩余乘积才行。枚举时一个经典优化是，记录当前考虑了前idx个元素，只枚举idx往后的每个因子选不选。

直接这样还是超时，加点剪枝，把因子升序排序，递归枚举到因子x，如果x×x>curx×x>curx×x>cur了，由于后面都是更大的因子，不可能选出一个y，x∗y=curx*y=curx∗y=cur了，而cur还没等于1，没到边界，还需要一个因子，那么这个因子只能是x了，后面更大因子不用枚举了。

voidsolve(){intn;cin>>n;vi f;for(inti=2;i*i<=n;i++){if(n%i==0){f.push_back(i);if(i*i!=n){f.push_back(n/i);}}}f.push_back(n);intm=f.size();ranges::sort(f);vip(m+10);p[0]=1;rep(i,1,m+5){p[i]=p[i-1]*i%M2;}intans=0;auto&&dfs=[&](auto&&dfs,inti,intcur,intcnt,intsum)->void{if(cur==1){ans=(ans+sum*p[cnt]%M2)%M2;ans=(ans+(sum+1)*p[cnt+1]%M2)%M2;return;}rep(j,i,m-1){if(f[j]>cur){break;}if(f[j]*f[j]>cur){dfs(dfs,j+1,1,cnt+1,sum+cur);break;}if(cur%f[j]==0){dfs(dfs,j+1,cur/f[j],cnt+1,sum+f[j]);}}};dfs(dfs,0,n,0,0);cout<<ans;}