CF1398 - LeAf146

1
void solve(){
2
    int n;cin>>n;
3
    vector<int> a(n);
4
    for(int i=0;i<n;i++){
5
        cin>>a[i];
6
    }
7
    if(a[0]+a[1]>a[n-1])cout<<-1<<endl;
8
    else cout<<"1 2 "<<n<<endl;
9
}

B. Substring Removal Game #

有一 01 字符串，每次可以删除一段连续相同的子串，得分为删除的 1 的数量，问先手得到的最大得分。

易得，删除 0 是劣的，若删除 0 后两侧的 1 相连，则下家可以一次性获得原本两侧需要两次的分数；若删除 0 后两侧的 1 不相连，则本次操作没有意义。即两人均不会删除任意 0。两人每次的得分只能是原本就相连的 1 的数量。统计连续的 1 的数量，从大到小贪心选择，奇数位的得分即为先手得分。

1
void solve(){
2
    string s;cin>>s;
3
    int n=s.size();
4
    vector<int> cnt;
5
    int now=(int)(s[0]=='1');
6
    for(int i=1;i<n;i++){
7
        if(s[i]=='1'){
8
            if(s[i-1]=='0') now=1;
9
            else now++;
10
        }else{
11
            if(s[i-1]=='1') cnt.push_back(now);
12
            now=0;
13
        }
14
    }
15
    cnt.push_back(now);
16
    sort(cnt.rbegin(),cnt.rend());
17
    int ans=0;
18
    for(int i=0;i<cnt.size();i+=2){
19
        ans+=cnt[i];
20
    }
21
    cout<<ans<<endl;
22
}

C. Good Subarrays #

给定一由 0-9 的整数组成的数组，问有多少好子数组满足数组元素和等于数组长度。

设原数组为 a[n]，则好数组 a[l,r] 满足 $\sum_{i=l}^r a_{i} = r-l+1 \implies \sum_{i=l}^r (a_i-1) = 0$ 设数组 b[n] 有 b[i]=a[i]-1，求 b[n] 的前缀和 pre[n]，满足 pre[r]-pre[l-1]=0 的位置即为所求位置，用 map 保存不同前缀和的位置，即可快速求出数量。

1
void solve(){
2
    int n;cin>>n;
3
    string s;cin>>s;
4
    vector<int> a(n),pre(n);
5
    map<int,int> precnt;
6
    for(int i=0;i<n;i++) a[i]=s[i]-'0'-1;
7
    pre[0]=a[0];
8
    precnt[pre[0]]++;
9
    for(int i=1;i<n;i++){
10
        pre[i]=a[i]+pre[i-1];
11
        precnt[pre[i]]++;
12
    }
13
    int ans=precnt[0];
14
    for(auto [_,it]:precnt){
15
        ans+=(it*(it-1)/2);
16
    }
17
    cout<<ans<<endl;
18
}

D. Colored Rectangles #

分别有 $R,G,B$ 对颜色为红、绿、蓝色的小棒，给定每对小棒的长度，每次取颜色不同的两对小棒组成矩形，问组成的所有矩形的面积和最大为多少。

显然对于同色小棒来说，优先取长度长的小棒，故先由大到小排序。设 dp[i][j][k] 为用了前 i 对红色小棒，前 j 对绿色小棒，前 k 对蓝色小棒后可以达到的最大面积。状态转移见程序。

1
signed main(){
2
    int R,G,B;cin>>R>>G>>B;
3
    vector<int> r(R+1),g(G+1),b(B+1);
4
    for(int i=0;i<R;i++)cin>>r[i];
5
    for(int i=0;i<G;i++)cin>>g[i];
6
    for(int i=0;i<B;i++)cin>>b[i];
7
    sort(r.rbegin(),r.rend());
8
    sort(g.rbegin(),g.rend());
9
    sort(b.rbegin(),b.rend());
10
    vector<vector<vector<int>>> dp(R+1,vector<vector<int>>(G+1,vector<int>(B+1)));
11
    int ans=0;
12
    for(int i=0;i<=R;i++){
13
        for(int j=0;j<=G;j++){
14
            for(int k=0;k<=B;k++){
15
                if(i<R&&j<G)dp[i+1][j+1][k]=max(dp[i][j][k]+r[i]*g[j],dp[i+1][j+1][k]);
16
                if(i<R&&k<B)dp[i+1][j][k+1]=max(dp[i][j][k]+r[i]*b[k],dp[i+1][j][k+1]);
17
                if(j<G&&k<B)dp[i][j+1][k+1]=max(dp[i][j][k]+g[j]*b[k],dp[i][j+1][k+1]);
18
                ans=max(ans,dp[i][j][k]);
19
            }
20
        }
21
    }
22
    cout<<ans<<endl;
23
    return 0;
24
}