Educational Codeforces Round 61 (Rated for Div. 2) D,F题解

D. Stressful Training

题目链接：https://codeforces.com/contest/1132/problem/D

题意：

有n台电脑，每台电脑都有初始电量a_i，也有一个耗电量b_i，意即每1s耗电多少，现在你有一个充电器，它每s可以给一台电脑充x的点亮。

问x最少为多少，可以让所有电脑直至k时刻，点亮都不小于0。

题解：

我们考虑贪心，先给最需要充电的电脑充电，然后二分答案x去检验。大概思路就是这样吧...但是实现起来还是有点困难。

首先处理出每个电脑最晚需要充电的时刻t_i，然后每次用一个指针找到第一个需要充电的时刻，不断给这个电脑充电直至这个电脑在下一秒不会没电，然后就更新它的时间。

这个时间复杂度是O(n+k)的，如果用优先队列，代码实现起来就比较简单，但是时间复杂度就多个log，但是cf评测机比较好，还是可以卡过的。

具体细节建议自己去实现一下吧，这样才有更深的体会，代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5+;

ll n,k;

ll a[N],b[N],c[N];

vector <ll> vec[N];

bool check(ll x){

//x=25;

    for(int i=;i<=k;i++) vec[i].clear();

    memcpy(c,a,sizeof(a));

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

        ll pos=a[i]/b[i]+;

        if(pos<=k){

            vec[pos].push_back(i);

            c[i]=a[i]%b[i];

        }

    }

    ll last=;

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

        while(last<=k&&vec[last].empty()) last++;

        if(last==k+) return true;

        if(last<i) return false ;

        int now = vec[last].back();

        if(c[now]+x<b[now]){

            c[now]+=x;

            continue ;

        }

        c[now]+=x;

        vec[last].pop_back();

        if(last+c[now]/b[now]<=k){

            vec[last+c[now]/b[now]].push_back(now);

            c[now]%=b[now];

        }

    }

    return true;

}

int main(){

    cin>>n>>k;

    for(int i=;i<=n;i++) cin>>a[i];

    for(int i=;i<=n;i++) cin>>b[i];

    ll l=,r=1e16,mid;

    while(l<r){

        mid=(l+r)/;

        if(check(mid)) r=mid;

        else l=mid+;

    }

    if(l==1e16) cout<<-;

    else cout<<r;

    return ;

}

F. Clear the String

题目链接：https://codeforces.com/contest/1132/problem/F

题意：

给出一个字符串，每次可以消去相同的连续字符，然后问最少需要几次能将这个字符串全部消去。

题解：

这题主要的关键就是发现无论怎么消，都会和两边的一起消。那么我们就可以类似于区间dp那样通过枚举确定两个边界进行转移了。

枚举中间点的时候，如果发现那个中间点和左端点的字符相同，那么我们就可以将那个中间点和左端点一起消。

反正这个题的解法很多就是了~转移方程也很多。

具体见代码吧：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ,INF = 0x3f3f3f3f3f;

int n;

char s[N];

int dp[N][N];

int main(){

    scanf("%d",&n);

    scanf("%s",s+);

    memset(dp,INF,sizeof(dp));

    for(int i=;i<=n;i++) dp[i][i]=;

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

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

            int j=i+l-;

            if(j>n) break ;

            for(int k=i;k<j;k++){

                if(s[i]==s[j]) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]-);

                else dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]);

            }

        }

    }

    cout<<dp[][n];

    return ;

}

巴特西

Educational Codeforces Round 61 (Rated for Div. 2) D,F题解

最新文章

热门文章