Codeforces Round #540 (Div. 3) 部分题解

时间：2024-01-16 10:08:20

Codeforces Round #540 (Div. 3)

题目链接：https://codeforces.com/contest/1118

题目太多啦，解释题意都花很多时间...还有事情要做，就选一些题来写吧。

B. Tanya and Candies

题意：

在n个数中任意删去一个，如果这个数被删去后，剩余数的奇数和以及偶数和相等，那么就定义这个数为"好数"。现在问这n个数中有多少个“好数”。

题解：

预处理出奇数前缀和、偶数前缀和，删去一个数后所有的奇数位置和 就为前面的奇数和以及后面的偶数和。然后枚举+判断就行了。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5+;

int n;

int a[N];

ll pre[N],sub[N];

int main(){

    cin>>n;

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    ll sum1=,sum2=;

    for(int i=;i<=n;i++){

        pre[i]=pre[i-];

        sub[i]=sub[i-];

        if(i&) pre[i]+=a[i];

        else sub[i]+=a[i];

    }

    sum1=pre[n];sum2=sub[n];

    ll sum=sum1+sum2;

    ll ans = ;

    for(int i=;i<=n;i++){

        ll now =;

        if(i&){

            now+=pre[i-];

            now+=sum-sub[i-]-sum1;

        }else{

            now+=sub[i-];

            now+=sum-pre[i-]-sum2;

        }

        if(now*==sum-a[i]) ans++;

    }

    cout<<ans;

    return ;

}

D2. Coffee and Coursework (Hard Version)

题意：

给出n杯咖啡，每杯咖啡能增加工作量ai，同时给出m即最终需要的工作量。

每一天都可以喝咖啡来增加工作量，但是在同一天中，每多喝一杯咖啡，相应增加的工作量就会多减少1。

最后问最少需要多少天，才能够完成工作量。

题解：

很显然，天数越多，工作越有可能被完成。所以可以二分天数，然后在此基础上，贪心地喝咖啡，也就是说，这x天的第1杯咖啡，都是权值最大的那些；第2杯就是次大的那些...以此类推。

这个题感觉也不是很难，就是二分+判断可行性，具体见代码吧：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3e5+;

int n,m;

int a[N];

int check(int x){

    int i;

    ll sum=,cnt=;

    for(i=;i<=n;i++){

        sum+=a[i]-cnt;

        if(i%x==) cnt++;

        if(sum>=m) return true;

    }

    return false;

}

int main(){

    cin>>n>>m;

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    sort(a+,a+n+);

    reverse(a+,a+n+);

    int l=,r=1e9+,mid;

    while(l<r){

        mid=l+r>>;

        if(check(mid)) r=mid;

        else l=mid+;

    }

    if(l==1e9+) cout<<-;

    else cout<<l;

    return ;

}

F1. Tree Cutting (Easy Version)

题意：

给出一颗树，其中有些点被染为颜色1，有些被染为颜色2，还有些没被染色，就是颜色0。现在要求删去一条边，使得树变为两个部分，并且满足每一部分中不同时存在1或者2颜色。

现在问有多少条边删去后，满足条件。

题解：

这个题也不是很难...维护每个结点的cnt1,cnt2，分别表示以它为根的子树中，1颜色和2颜色有多少。

如果满足一个结点，以它为根的子树中，包含了所有的1或者2颜色，并且不包含另外一种颜色，那么答案就加一。

一个dfs就搞定了。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3e5+;

int n,sum1,sum2;

int a[N],cnt1[N],cnt2[N];

vector <int> g[N];

int ans;

void dfs(int u,int fa){

    if(a[u]==) cnt1[u]++;

    if(a[u]==) cnt2[u]++;

    for(auto v:g[u]){

        if(v==fa) continue ;

        dfs(v,u);

        cnt1[u]+=cnt1[v];

        cnt2[u]+=cnt2[v];

    }

    if(cnt1[u]==sum1 && !cnt2[u]) ans++;

    if(!cnt1[u] && cnt2[u]==sum2) ans++;

}

int main(){

    cin>>n;

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    for(int i=;i<=n;i++){

        if(a[i]==) sum1++;

        if(a[i]==) sum2++;

    }

    for(int i=;i<n;i++){

        int u,v;

        scanf("%d%d",&u,&v);

        g[u].push_back(v);

        g[v].push_back(u);

    }

    dfs(,-);

    cout<<ans;

    return ;

}

相关文章