CF-1114
A. Got Any Grapes?
- skip
- B. Yet Another Array Partitioning Task
将 n 个数分成连续的 k 组, 使得每组的前 m 大的数字的总和最大.
首先可以想到肯定可以包含 n 个数中前 m*k 大的数. 所以可以先将他们标记, 然后扫一遍确定每组的端点即可
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- int n,m,k;
- struct node{
- int x;
- int id;
- }a[200010];
- int v[200010];
- bool cmp(node a,node b){
- return a.x>b.x;
- }
- int main(){
- cin>>n>>m>>k;
- for(int i=1;i<=n;i++){
- scanf("%d",&a[i].x);
- a[i].id = i;
- }
- sort(a+1,a+n+1,cmp);
- ll sum = 0;
- for(int i=1;i<=m*k;i++){
- v[a[i].id] = 1;
- sum += a[i].x;
- }
- vector<int> ans;
- int num = 0;
- for(int i=1;i<=n;i++){
- if(v[i])num++;
- if(num==m){
- ans.push_back(i);num=0;
- if(ans.size()==k-1)
- break;
- }
- }
- cout<<sum<<endl;
- for(int i=0;i<k-1;i++)
- cout<<ans[i]<<' ';
- puts("");
- return 0;
- }
- C. Trailing Loves (or L'oeufs?)
- $ n! = p_1^{x_1} \cdot p_2^{x_2}\cdots p_m^{x_m} \cdot Q$
- \(b = p_1^{y_1} \cdot p_2^{y_2} \cdots p_m^{y_m}\)
分解 n! 的质因数复杂度为 O(log N). 所以我们可以将 b 分解质因数, 对于质因数 \(p_i\), 计算 n! 含有多少个质因子 \(p_i\) (设 \(x_i\)) , 则该质因子下答案为 \(\lfloor x_i/y_i \rfloor\) , 最终 \(ans = min \{ \lfloor x_1/y_1 \rfloor \cdots \lfloor x_m/y_m\rfloor \}\)
计算 n! 中含有多少个 \(p_i\) 时, 可以这样计算:
首先在 1 到 n 的排列中肯定有 \(\lfloor n/p_i \rfloor\)个包含质因子 \(p_i\)的数, 同理也有 \(\lfloor x/{p_i^2}\rfloor\) 个含有两个 \(p_i\)的数, 不过其中的一个质因子已经在 \(\lfloor n/p_i \rfloor\)中统计过, 所以只需要再统计第二个质因子, 即累加上 \(\lfloor x/{p_i^2}\rfloor\), 而不是 \(2*\lfloor x/{p_i^2}\rfloor\)
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const ll inf = LONG_LONG_MAX;
- ll n,b;
- ll calc(ll p,ll cnt){
- //res 为上述 xi
- ll res = 0,base = 1;
- for(;base<=n/p;){
- base*=p;
- res += n/base;
- }
- /* 写成下面这样会爆
- for(base=x;base<=n;base*=x){
- res += n/base;
- }*/
- return res/cnt;
- }
- int main(){
- cin>>n>>b;
- ll ans = inf;
- // 分解质因数
- for(ll i=2;i*i<=b;i++){
- if(b%i==0){
- ll cnt = 0;//cnt 为上述 yi
- while(b%i==0)b/=i,cnt++;
- ans = min(ans,calc(i,cnt));
- }
- }
- if(b>1) ans = min(ans,calc(b,1));
- cout<<ans<<endl;
- }
- D. Flood Fill
(又是一个没见过的区间 DP, 题解里面说可以倒过来 LCS, 相当于求最长回文子序列, 不过我还没搞懂
d[i][j][0]表示区间 [i,j] 所有数字与 a[i]相同时所需要的最少改变次数, d[i][j][1]表示与 a[j]相同. 复杂度为 \(O(n^2)\)
每次转移只能向左或者向右移动一格, 细节看代码吧
- #include <bits/stdc++.h>
- using namespace std;
- const int inf = 0x3f3f3f3f;
- int n;
- int a[5050];
- int dp[5050][5050][2];
- int main(){
- cin>>n;
- for(int i=1;i<=n;i++)scanf("%d",&a[i]);
- if(n==1){
- puts("0");return 0;
- }
- memset(dp,0x3f,sizeof dp);
- for(int i=1;i<=n;i++)dp[i][i][0] = dp[i][i][1] = 0;
- for(int i=n;i>=1;i--){
- for(int j=i;j<=n;j++){
- for(int k=0;k<2;k++){
- //c 为标准
- int c = k==0?a[i]:a[j];
- if(j<n)
- dp[i][j+1][1] = min(dp[i][j+1][1],dp[i][j][k]+(a[j+1]==c?0:1));
- if(i>1)
- dp[i-1][j][0] = min(dp[i-1][j][0],dp[i][j][k]+(a[i-1]==c?0:1));
- }
- }
- }
- cout<<min(dp[1][n][0],dp[1][n][1])<<endl;
- }
CF 每日一练(2.11)
来源: http://www.bubuko.com/infodetail-2950621.html