2018-team7-CF29

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

好难 这场= =

菜到爆炸

A题2y20 看错了题目条件 按照题意模拟即可

B题不会做 

状态压缩之后如果两行状态不等 说明他们不会被一起选

然后如果他们存在某列全为1 那么显然不合法

C题 水题 精度需要注意下 二分即可

D题 

显然

mark[i] = m[i] + d[i] + 1;

其中mark[i]非严格递增且最大差1

转换为求这样的sum of d[i] 最小

那我们可以从前往后先把序列变成非严格递增（差值加进答案）

从后扫一遍若后面的值大于前面的值+1

把前面的值变成后面的值-1

差值加进答案
{{{
#!C
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int m[102020];
int dp[102020];
int main(){
    int n;
    ll ans=0;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>m[i],++m[i];
    for(int i=2;i<=n;++i){
        if(m[i]<m[i-1]){
            ans+=m[i-1]-m[i];
            m[i]=m[i-1];
        }
    }
    for(int i=n;i>=2;i--){
        if(m[i]>m[i-1]+1){
            ans+=m[i]-1-m[i-1];
            m[i-1]=m[i]-1;
        }
    }
    cout<<ans<<endl;
    return 0;
}
}}}

好难 这场= =

菜到爆炸

A题2y20 看错了题目条件 按照题意模拟即可

B题不会做

状态压缩之后如果两行状态不等 说明他们不会被一起选

然后如果他们存在某列全为1 那么显然不合法

C题 水题 精度需要注意下 二分即可

D题

显然

mark[i] = m[i] + d[i] + 1;

其中mark[i]非严格递增且最大差1

转换为求这样的sum of d[i] 最小

那我们可以从前往后先把序列变成非严格递增（差值加进答案）

从后扫一遍若后面的值大于前面的值+1

把前面的值变成后面的值-1

差值加进答案

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int m[102020];
int dp[102020];
int main(){
    int n;
    ll ans=0;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>m[i],++m[i];
    for(int i=2;i<=n;++i){
        if(m[i]<m[i-1]){
            ans+=m[i-1]-m[i];
            m[i]=m[i-1];
        }
    }
    for(int i=n;i>=2;i--){
        if(m[i]>m[i-1]+1){
            ans+=m[i]-1-m[i-1];
            m[i-1]=m[i]-1;
        }
    }
    cout<<ans<<endl;
    return 0;
}