Codeforces Round #591 (Div. 2, based on Technocup 2020 Elimination Round 1) 题解(示例代码)

栏目: 类库 · 发布时间: 2021-05-07

来源: bluefly-hrbust

作者:bluefly-hrbust

简介  这篇文章主要介绍了Codeforces Round #591 (Div. 2, based on Technocup 2020 Elimination Round 1) 题解(示例代码)以及相关的经验技巧,文章约22051字,浏览量2621,点赞数2,值得参考!

A..B略

C 对当前的值排序,再二分答案,然后对于(i%x==0 && i%y==0)放入大的,再放其他的贪心解决即可。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#define LL long long
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int maxx = 2e5+7;
int a[maxx];
int vis[maxx];
LL k;
LL aa,bb;
int x,y,n;
bool check(int mid){
      LL ans=0;
      int top=0;
       for (int i=1;i<=mid;i++){
            if (i%x==0 && i%y==0){
                vis[i]=a[++top];
                ans=(LL)ans+vis[i]/100*(aa+bb);
            }else {
                vis[i]=0;
            }
 
        }
        for (int i=1;i<=mid;i++){
            if (i%y==0 && !vis[i]){
                vis[i]=a[++top];
                ans=(LL)ans+vis[i]/100*bb;
            }
 
        }
        for (int i=1;i<=mid;i++){
            if (i%x==0 && !vis[i]){
                vis[i]=a[++top];
                ans=(LL)ans+vis[i]/100*aa;
            }
        }
        return ans>=k;
}
bool cmp(int x,int y){
   return x>y;
}
int main(){
  int t;
  scanf("%d",&t);
  while(t--){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
      scanf("%d",&a[i]);
    }
    scanf("%d%d",&aa,&x);
    scanf("%d%d",&bb,&y);
    scanf("%lld",&k);
    if (aa>bb){
        swap(x,y);
        swap(aa,bb);
    }
    sort(a+1,a+1+n,cmp);
    int l=1;
    int r=n;
    int ans=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if (check(mid)){
            ans=mid;
            r=mid-1;
        }else {
            l=mid+1;
        }
    }
    if (ans==-1){
        printf("-1
");
    }else {
        printf("%d
",ans);
    }
  }
  return 0;
}

D 记录一次出现和最后一次出现的,考虑移动的比较麻烦,我们可以考虑对于两个相邻的大小的值,前面那个值最后次出现的位置是大于这个值第一次出现的,那么他们的相对位置关系是不用移动的,我们求出这种不用移动的相对位置连续个数是最多的,那么就是最长不用移动的,其他的肯定要移动,那么直接用所有值的个数去减这个值就行了。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#define LL long long
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int maxx = 2e5+7;
int a[maxx];
int vis[maxx];
LL k;
LL aa,bb;
int x,y,n;
bool check(int mid){
      LL ans=0;
      int top=0;
       for (int i=1;i<=mid;i++){
            if (i%x==0 && i%y==0){
                vis[i]=a[++top];
                ans=(LL)ans+vis[i]/100*(aa+bb);
            }else {
                vis[i]=0;
            }
 
        }
        for (int i=1;i<=mid;i++){
            if (i%y==0 && !vis[i]){
                vis[i]=a[++top];
                ans=(LL)ans+vis[i]/100*bb;
            }
 
        }
        for (int i=1;i<=mid;i++){
            if (i%x==0 && !vis[i]){
                vis[i]=a[++top];
                ans=(LL)ans+vis[i]/100*aa;
            }
        }
        return ans>=k;
}
bool cmp(int x,int y){
   return x>y;
}
int main(){
  int t;
  scanf("%d",&t);
  while(t--){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
      scanf("%d",&a[i]);
    }
    scanf("%d%d",&aa,&x);
    scanf("%d%d",&bb,&y);
    scanf("%lld",&k);
    if (aa>bb){
        swap(x,y);
        swap(aa,bb);
    }
    sort(a+1,a+1+n,cmp);
    int l=1;
    int r=n;
    int ans=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if (check(mid)){
            ans=mid;
            r=mid-1;
        }else {
            l=mid+1;
        }
    }
    if (ans==-1){
        printf("-1
");
    }else {
        printf("%d
",ans);
    }
  }
  return 0;
}

E. Paint the Tree

  我们考虑dp[i][0]代表这个节点的k重颜色已经全部匹配,dp[i][0代表当前节点还有颜色没有匹配。那么我们其实可以很容易得到dp的转移

  首先dp[i][1]+=sigma[son[i]][0] dp[i][0]+=sigma[son[i]][0] 也就是说我们每个节点首先看出全部选了子树颜色已经全部匹配的结果

  我们再把所有节点选择子树没有匹配完全的加上这条路径的长度去减去子树已经匹配的完全的差值,然后再差值中选中前k大的正数和加到dp[i][0]表示选择后悔了

把前i-1的正数加到dp[i][1]中即可。最后取根节点两者的最大值即可。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#define LL long long
using namespace std;
const int maxx = 5e5+6;
int ver[maxx*2],edge[2*maxx],head[maxx],Next[2*maxx];
int n,k,tot;
LL dp[maxx][2];
void add(int x,int y,int w){
   ver[++tot]=y;edge[tot]=w;Next[tot]=head[x];head[x]=tot;
   ver[++tot]=x;edge[tot]=w;Next[tot]=head[y];head[y]=tot;
}
bool cmp(int a,int b){
   return a>b;
}
void dfs(int u,int fa){
   dp[u][0]=dp[u][1]=0;
   vector<int>vv;
   vv.clear();
   for (int i=head[u];i;i=Next[i]){
       int v=ver[i];
       if (v==fa)continue;
       dfs(v,u);
       dp[u][0]+=dp[v][0];
       dp[u][1]+=dp[v][0];
   }
   for (int i=head[u];i;i=Next[i]){
       int v=ver[i];
       if (v==fa)continue;
       vv.push_back(dp[v][1]+edge[i]-dp[v][0]);
   }
   sort(vv.begin(),vv.end(),cmp);
   int sz=min((int)vv.size(),k);
   for (int i=0;i<sz;i++){
       if(vv[i]<0)break;
       if(i==k-1){
          dp[u][0]=(LL)vv[i]+dp[u][1];
       }else {
          dp[u][0]=(LL)vv[i]+dp[u][1];
          dp[u][1]=(LL)vv[i]+dp[u][1];
       }
   }
}
int main(){
  int t;
  scanf("%d",&t);
  int uu,vv,ww;
  while(t--){
     scanf("%d%d",&n,&k);
     for (int i=1;i<=n;i++){
        head[i]=0;
     }
     for (int i=1;i<=n-1;i++){
        scanf("%d%d%d",&uu,&vv,&ww);
        add(uu,vv,ww);
     }
     dfs(1,-1);
     printf("%lld
",max(dp[1][0],dp[1][1]));
  }
  return 0;
}

 


以上就是本文的全部内容,希望对大家的学习有所帮助,本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 原文地址:https://www.cnblogs.com/bluefly-hrbust/p/11637692.html

codeforces 591B Rebranding (模拟)(示例代码)

Codeforces-591C题解(示例代码)

CodeForces 591B(示例代码)

CodeForces 591A(示例代码)

CodeForces 591A(示例代码)

CodeForces 591B(示例代码)

codeforces #591 div2 ABCD(示例代码)

codeforces Technocup 2017 - Elimination Round 2/Codeforces Round #380 (Div. 2, Rated, Based on Techn