CWOI 2019 NOIP 暑假测试三

Problem A Cut

题面

给你一个长度为$n$的序列，你每次可以将一个序列分割成两个连续的的子序列，分割的代价为原序列的总和。现在允许你在初始时将序列重新排列一次。问分割成$n$个长度为$1$的序列的最大总代价是多少？

题解

在从小到大排序后，显然答案为$$\sum_{i}^{n-1}a_i \times i + a_n \times (n-1)$$

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int n;
    long long ans=0;
    vector<int> vec;
    cin>>n;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        vec.push_back(t);
    }
    sort(vec.begin(),vec.end());
    for(int i=0;i<n;i++){
        ans+=vec[i]*(i+1); 
    }
    cout<<ans-vec[n-1]<<endl;
    return 0;
}

Problem B 用水填坑

题面

现有一块$n \times m$的地，每块$1 \times 1$的地的高度为$h_{i,j}$，在$n \times m$的土地之外的土地高度均为$0$（即你可以认为最外圈无法积水）

现在下了一场足够大的雨，试求出这块地总共积了多少单位体积的水。

题解

首先假定~~这里涨了一场洪水~~所有的地方水涨到了与最高峰平齐的位置，然后退潮水向下下降，然后外流，直到流不动位置，此时统计即为答案。

代码

#include <iostream>
using namespace std;
const short MAXM=1005;
bool fuck;
int n,m;
long long ma[MAXM][MAXM],water[MAXM][MAXM],ans=0,bw; 
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ma[i][j];
            bw=max(ma[i][j],bw);
            ans-=ma[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        //Begin
        for(int j=1;j<=m;j++){
            water[i][j]=bw;
        }
    }
    do{
        fuck=false;
        for(int i=1;i<=n;i++){
            //Left
            for(int j=1;j<=m;j++){
                if(water[i][j-1]<water[i][j]&&water[i][j]!=max(water[i][j-1],ma[i][j])){
                    water[i][j]=max(water[i][j-1],ma[i][j]);
                    fuck=true;
                }
            }
            //Right
            for(int j=m;j>0;j--){
                if(water[i][j+1]<water[i][j]&&max(water[i][j+1],ma[i][j])!=water[i][j]){
                    water[i][j]=max(water[i][j+1],ma[i][j]);
                    fuck=true;
                }
            }
        }
        for(int i=1;i<=m;i++){
            //Up
            for(int j=1;j<=n;j++){
                if(water[j-1][i]<water[j][i]&&water[j][i]!=max(water[j-1][i],ma[j][i])){
                    water[j][i]=max(water[j-1][i],ma[j][i]);
                    fuck=true;
                }
            }
            //Down
            for(int j=n;j>0;j--){
                if(water[j+1][i]<water[j][i]&&water[j][i]!=max(water[j+1][i],ma[j][i])){
                    water[j][i]=max(water[j+1][i],ma[j][i]);
                    fuck=true;
                }
            }
        }
    }while(fuck);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans+=water[i][j];
        }
    }
    cout<<ans<<endl;
    return 0;
}

Problem C 序列

该题目为Codeforces 743E，以下为中文翻译。

题面

给定一个长度为$n$的序列，序列中的数字只由$[1,8]$这八个数字组成。要你找一个最长的子序列满足下面的两个条件：

子序列中每个数字的数目相差不超过$1$，即$|num_i-num_j| \leq 1(1 \leq i \leq j \leq 8),比如序列$[1,1,2,2]$不满足条件，因为$|num_8-num_1| =2 gt 1$
相同数字在子序列中要求连续，比如序列$[1,1,2,2,1,1]$不满足条件。

题解

设子序列中每个数字的数量至少为$len$，其中长度为$len+1$的为$k$个，则子序列长度为$$k \times (len+1)+(8−k) \times len$$，通过二分枚举$len$，然后用状压DP判断是否可行并得到最大的$k$，设数组$dp[n][(1<<8)−1]$，在$dp[i][s]$中，$s$ 的二进制串中，$1$表示那个数字已经出现了至少$len$次，反之亦然。$dp[i][s]$表示在前$i$位中，$s$的二进制串为$1$那位的那个数字已经出现了至少len次。

代码

#include <bits/stdc++.h>
using namespace std;
const short MAXN = 1010;
int n;
vector< int > g[10];
int a[MAXN], p[10], cur[10], dp[MAXN][1 << 8];
inline int check( int len ) {
    memset( cur, 0, sizeof( cur ) );
    memset( dp, -1, sizeof( dp ) );
    dp[0][0] = 0;
    for ( int i = 0; i < n; i++ ) {
        for ( int j = 0; j < ( 1 << 8 ); j++ ) {
            if ( dp[i][j] == -1 )
                continue;
            for ( int k = 1; k <= 8; k++ ) {
                if ( j & ( 1 << ( k - 1 ) ) )
                    continue;
                int x = cur[k] + len - 1;
                if ( x >= g[k].size() )
                    continue;
                dp[g[k][x]][j | ( 1 << ( k - 1 ) )] = max( dp[g[k][x]][j | ( 1 << ( k - 1 ) )], dp[i][j] );
                if ( ( ++x ) >= g[k].size() )
                    continue;
                dp[g[k][x]][j | ( 1 << ( k - 1 ) )] = max( dp[g[k][x]][j | ( 1 << ( k - 1 ) )], dp[i][j] + 1 );
            }
        }
        cur[a[i]]++;
    }
    int ans = -1;
    for ( int i = 1; i <= n; i++ )
        ans = max( ans, dp[i][( 1 << 8 ) - 1] );
    if ( ans == -1 )
        return -1;
    return ans * ( len + 1 ) + ( 8 - ans ) * len;
}
void Solve() {
    int l = 1, r = n / 8, mid;
    while ( l + 1 < r ) {
        mid = ( l + r ) >> 1;
        if ( check( mid ) != -1 )
            l = mid;
        else
            r = mid - 1;
    }
    int ans = max( check( l ), check( r ) );
    if ( ans == -1 ) {
        ans = 0;
        for ( int i = 1; i <= 8; i++ )
            if ( g[i].size() )
                ans++;
    }
    cout << ans << endl;
}
int main() {
    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        cin >> a[i];
        g[a[i]].push_back( i );
    }
    Solve();
    return 0;
}