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+5;
ll n,k;
ll a[N],b[N],c[N];
vector <ll> vec[N];
bool check(ll x){
//x=25;
    for(int i=1;i<=k;i++) vec[i].clear();
    memcpy(c,a,sizeof(a));
    for(int i=1;i<=n;i++){
        ll pos=a[i]/b[i]+1;
        if(pos<=k){
            vec[pos].push_back(i);
            c[i]=a[i]%b[i];
        }
    }
    ll last=1;
    for(int i=1;i<=k;i++){
        while(last<=k&&vec[last].empty()) last++;
        if(last==k+1) 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=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    ll l=0,r=1e16,mid;
    while(l<r){
        mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    if(l==1e16) cout<<-1;
    else cout<<r;
    return 0;
}

View Code

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 = 505,INF = 0x3f3f3f3f3f;
int n;
char s[N];
int dp[N][N];
int main(){
    scanf("%d",&n);
    scanf("%s",s+1);
    memset(dp,INF,sizeof(dp));
    for(int i=1;i<=n;i++) dp[i][i]=1;
    for(int l=2;l<=n;l++){
        for(int i=1;i<=n;i++){
            int j=i+l-1;
            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+1][j]-1);
                else dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
        }
    }
    cout<<dp[1][n];
    return 0;
}

View Code