【LittleXi] 牛客小白月赛85 ACDF

A

签到题，计算一下可以组成多少份A，多少份CC，多少份E，多少份P，多少份T

#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

void solve(){
    int n ;
    cin>>n;
    string s;cin>>s;
    int cnt[26]={0};
    for(char c:s) cnt[c-'A'] ++;
    int ans = n;
    ans = min(ans,cnt[0]);
    ans = min(ans,cnt['C'-'A']/2);
    ans = min(ans,cnt['E'-'A']);
    ans = min(ans,cnt['P'-'A']);
    ans = min(ans,cnt['T'-'A']);
    cout<<ans<<endl;
}

int main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t = 1;
    cin>>t;
    while(t--){
        solve();
    }
}

B

题目大意：求1,1+2,1+2+3,1+2+3+4...的第n项偶数的位置

可以将数字分为 ，利用等差数列求和，然后可以发现 位置的项一定是奇数，位置一定是偶数

#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

void solve(){
    ll n ;
    cin>>n;
    if(n%2==0) cout<<n*2;
    else cout<<(n-1)*2+3;
}

int main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t = 1;
    while(t--){
        solve();
    }
}

C

题意：求一个最大的数字，使得满足游戏的得分规则

可以很明显考虑二分，二分的时候判断，如果某个位置不合理的化，直接修改l或者r，如果合理，那么增大l为m

#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

void solve(){
    ll n; 
    cin>>n;
    vector<ll> a(n);
    for(ll &x:a) cin>>x;
    double l = 0,r =  2e9;
    while(l+1e-6<r){
        double m = (l+r)/2;
        double sm = 0;
        ll ok = 1;
        for(ll i=0;i<n;i++){
            sm += m;
            if(((ll)sm)!=a[i]){
                if(sm<a[i]) l=m;
                else r= m;
                ok = 0;
                break;
            }
        }
        if(ok) l = m;
    }
    cout<<fixed<<setprecision(15)<<l<<endl;
}

signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    ll t = 1;
    // cin>>t;
    while(t--){
        solve();
    }
}

D 阿里马马与四十大盗

很有意思的一个题，一眼看上去是dp，实际不是

考虑贪心

找到最后一个一定要恢复的位置，然后前面位置全部选择回复，后面位置全部选择不恢复，就行了，如果中途挂掉，那么就真的死了

为什么呢？对于找到的某个要恢复的位置 K，如果血量已经满足了后面所有恶魔的伤害，那么后面没必要回复了，对于前面的回复位置，如果选择了回复，那么其实答案是不会变坏的，因为前面选择了回复，那么K位置可以少回复，所以是一样的，那么前面尽情回复吧！

#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

ll pre_sum(vector<ll>&pre,ll l,ll r){
    if(l) return pre[r]-pre[l-1];
    return pre[r];
}

void solve(){
    ll n,m;
    cin>>n>>m;
    vector<ll> a(n);
    for(ll&x:a)cin>>x;
    vector<ll >pre(n,a[0]);
    for(ll i=1;i<n;i++){
        pre[i] = pre[i-1]+a[i];
    }
    ll bld = m;
    ll ans = 0;
    for(ll i =0 ;i<n-1;i++){
        if(a[i] == 0){
            ans+=m-bld;
            bld = m;
            if(m>pre_sum(pre,i+1,n-1)){
                cout<<ans+n-1<<endl;
                return;
            }
        } else{
            bld-=a[i];
            if(bld<=0){
                cout<<"NO"<<endl;
                return;
            }
        }
    }
    cout<<ans+n-1<<endl;
}

signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    ll t = 1;
    while(t--){
        solve();
    }
}

E

赛时没想出来，感觉是NPC问题的近似算法？

F（easy version)

题意：第i~i+1天有一个事件，降雨或者失水，你可以每天抽取任意的水，使得n天中，有最多的天数是适宜的

考虑DP

从后往前dp，对于第j天，我们可以枚举抽取之后还剩i份水，转移

dp[j][i] = [i是适宜的水量] + max(dp[j+1][max(0,a[j+1]-第j天吸走的水量)])

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"

int grid[5005][5005]={0};

void solve(){
    int n,l,r;
    cin>>n>>l>>r;
    vector<int> a(n);
    for(int &x:a)cin>>x;
    for(int i =0;i<=a[n-1];i++)
        grid[n-1][i] = i>=l&&i<=r;
    for(int j = n-2;j>=0;j--){
        vector<int> pre_mx(5005,grid[j+1][0]);
        for(int i = 1;i<=5005;i++) pre_mx[i] = max(pre_mx[i-1],grid[j+1][i]);
        for(int k=0;k<=a[j];k++){
            int dis = a[j]-k;
            grid[j][k] = (k>=l&&k<=r) + pre_mx[max(0,a[j+1]-dis)];
        }
    }
    int ans = 0;
    for(int i=0;i<=a[0];i++)
        ans = max(ans,grid[0][i]);
    cout<<ans<<endl;
}

int main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t = 1;
    while(t--){
        solve();
    }
}