投稿
  1. 高性能架构探索首页
  2. C/C++

CF #642(div.3)

admin • • C/C++ • 阅读 201

A. Most Unstable Array

time limit per test: 1 second

memory limit per test: 256 megabytes

题意： \(t\) 组数据 \((1 \leq t \leq 10^4)\) ，每组数据给出整数 \(n\) 和 \(m~(1 \leq n,m \leq 10^9)\) ，现要求把 \(m\) 划分成 \(n\) 个大于等于 \(0\) 的数之和，设这 \(n\) 个数构成数组 \(a\)，求

\[\sum_{i=1}^{n-1}|a_i-a_{i+1}|
\]

的最大值

分析： 因为要求划分的数都大于等于 \(0\) ，所以最好的划分就是一个大于 \(0\) 的数左右两边都是 \(0\) ，这样的划分就等价于 \(0,m,0,...,0\) ，所以

  • \(n=1,ans=0\)
  • \(n=2,ans=m\)
  • \(n>2,ans=2m\)

代码：

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t,n,m;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        if(n==1) cout<<0<<endl;
        else if(n==2) cout<<m<<endl;
        else cout<<2*m<<endl; 
    }
}

B. Two Arrays And Swaps

time limit per test: 1 second

memory limit per test:256 megabytes

题意： \(t~(1 \leq t \leq 200)\) 组测试数据，每组数据先有整数 \(n\) 和 \(k~(1 \leq n \leq 30;0 \leq k \leq n)\) ，然后给出大小为 \(n\) 的整数数组 \(a\) 和 \(b~(1 \leq a_i,b_i \leq 30)\)，现在最多有 \(k\) 次机会互换 数组 \(a\) 和 \(b\) 内的任意元素，使得最后 \(a\) 的元素和最大，求这个最大元素和

分析： 模拟

代码：

#include<bits/stdc++.h>
using namespace std;
#define P pair<int,int>
const int N = 100;
P s[N];

bool cmp(P a,P b)
{
    if(a.first==b.first) return a.second<b.second;
    return a.first>b.first;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t,n,k;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1,x;i<=n;i++) cin>>x,s[i]=P(x,1);
        for(int i=n+1,x;i<=n+n;i++) cin>>x,s[i]=P(x,2);
        sort(s+1,s+n+n+1,cmp);

        int sum=0,cnt=1;
        for(int i=1;i<=n;i++)
        {
            if(s[cnt].second==1) sum+=s[cnt].first,cnt++;
            else if(k){
                sum+=s[cnt].first,cnt++,k--;
            }
            else{
                while(s[cnt].second==2) cnt++;
                sum+=s[cnt].first,cnt++;
            }
        }
        cout<<sum<<endl;
    }
}

C. Board Moves

time limit per test: 1 second

memory limit per test: 256 megabytes

题意： 给定一个 \(n \times n~(n \in odd;1 \leq n \leq 5 \times 10^5)\) 的矩阵，每个点上有个数字，求把所有数字集中到一个点上的最小花费，一个点上的数字移动到相邻的点上的花费为 \(1\) (相邻的定义为周围八个位置)

分析： \(n\) 是奇数，显然把所有点移到矩阵的中心花费是最小的，根据相邻的定义，从中心点周围第一圈花费为 \(1\) ，第二圈花费为 \(2\) ，... 打个表就可以了

代码：

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 5E5+10;
ull a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    a[1]=0;
    ull cnt=1;
    for(int i=3;i<N;i+=2) a[i]=a[i-2]+((i-2)*4+4)*cnt,cnt++;

    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cout<<a[n]<<endl;
    }

}

D. Constructing the Array

time limit per test: 1 second

memory limit per test: 256 megabytes

题意： 给定大小为 \(n~(1 \leq n \leq 2 \cdot 10^5)\) 的数组 s ，初始全为 \(0\) ，现在要求填 \(n\) 次数字，第 \(i\) 填 \(i\) ，每一次都需要在数组中找到最长的 \(0\) 段(如果有多个取最左边的)，设它的长度为 \(m\)，区间为 \([l,r]\) 若

  • \(m \in odd，则s[\frac{l+r}{2}]=i;\)
  • \(m \in even，则s[\frac{l+r-1}{2}]=i;\)

输出最后的数组

分析： 根据题目的优先级建立优先队列模拟填写过程

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2E5+10;
int a[N]; 

struct node{
    int l,r;
    bool operator<(const node& a)const{
        if(r-l!=a.r-a.l) return r-l<a.r-a.l;
        else return l>a.l;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        priority_queue<node>q;
        q.push((node){1,n});
        int cnt=1;
        while(!q.empty())
        {
            node top=q.top();q.pop();
            int l=top.l,r=top.r;
            if((r-l+1)%2==1)
            {
                int m=(r+l)/2;
                a[m]=cnt;
                if(r-l>1)
                  q.push((node){l,m-1}),
                  q.push((node){m+1,r});
            }
            else
            {
                int m=(r+l-1)/2;
                a[m]=cnt;
                if(l<m) q.push((node){l,m-1});
                if(m<r)  q.push((node){m+1,r});
            }

            cnt++; 
        }
        for(int i=1;i<=n;i++) cout<<a[i]<<' ';
        cout<<endl;
    }
}

E. K-periodic Garland

time limit per test: 1 second

memory limit per test: 256 megabytes

题意： \(t~(1 \leq t \leq 25000)\) 组测试数据，每组数据先给出 \(n\) 和 \(k~(1 \leq n \leq 10^6;1 \leq k \leq n)\)，然后给出长度为 \(n\) 的 \(01\) 序列代表 \(n\) 盏灯，\(0\) 表示关，\(1\) 表示开，每次可以选择一盏灯改变它的状态，问最少需要操作多少次使得所有 \(1\) 之间的间距为 k

分析： 设 \(dp[i]\) 表示第 \(i\) 位为 \(1\)，\([1,i]\) 满足条件的情况下需要最少的操作步数，则转移方程不难给出，设 \(sum[i]\) 为前 \(i\) 盏灯原状态为 \(1\) 的数量

if(第i盏灯原状态为1){
    if(i<=k) dp[i]=sum[i-1];  //前面不足k盏灯，所以必须全为0
    else{  
        dp[i]=dp[i-k]+(sum[i-1]-sum[i-k]); 
        //否则，第i-k盏灯必须为1，且开区间(i-k,i)之间的状态必须都为0
        dp[i]=min(dp[i],sum[i-1]);
        //或者前i-1个都为0，取较小代价
    }
}
else{   //下述同理，唯一区别就是第i盏灯原状态为0，代价+1
    if(i<=k) dp[i]=sum[i-1]+1; 
    else{  
        dp[i]=dp[i-k]+(sum[i-1]-sum[i-k]+1); 
        dp[i]=min(dp[i],sum[i-1]+1);
    }
}

但是这样还不够，我们从前往后求的 \(dp[i]\) 是基于第 \(i\) 点状态为 \(1\) 的情况下区间 \([1,i]\) 的最优解，后面的怎么管?——其实可以在 dp 的时候顺便枚举以当前点为最后一个状态 \(1\) 时的最小代价，即

f=min(f,dp[i]+sum[n]-sum[i]); //第i个点之后的状态1全部置为0

上面考虑的是至少有一个状态 \(1\) 的情况，所以最后再与全部置 \(0\)，代价即 \(sum[n]\) 作比较取最小值即可

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1E6+10;
int dp[N],sum[N];
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t,n,k;
    cin>>t;
    while(t--)
    {
        cin>>n>>k>>s;
        for(int i=1;i<=n;i++) 
           if(s[i-1]=='1') sum[i]=1;
           else sum[i]=0;

        for(int i=2;i<=n;i++) sum[i]+=sum[i-1];
        for(int i=0;i<=n;i++) dp[i]=0;
        int f=1000000;
        for(int i=1;i<=n;i++)
        {
            if(s[i-1]=='1') 
            {
                if(i-k>0){
                    dp[i]=dp[i-k]+(sum[i-1]-sum[i-k]);
                    dp[i]=min(dp[i],sum[i-1]);
                }
                else{
                    dp[i]=sum[i-1];
                }
            }
            else
            {
                if(i-k>0){
                    dp[i]=dp[i-k]+(sum[i-1]-sum[i-k]+1);
                    dp[i]=min(dp[i],sum[i-1]+1);
                }
                else{
                    dp[i]=sum[i-1]+1;
                }
            }
            f=min(f,dp[i]+sum[n]-sum[i]); 
        } 
        cout<<min(dp[n],min(f,sum[n]))<<endl;
    }
}

F. Decreasing Heights

time limit per test: 2.5 seconds

memory limit per test:256 megabytes

题意： \(t~(1 \leq t \leq 100)\) 组测试数据，每组数据先给出 \(n\) 和 \(m~(1 \leq n,m \leq 100)\)，然后给出 \(n \times m\) 的整数矩阵，花费一次代价你可以把矩阵内任意点上的元素减 \(1\)，现在要求从点 \((1,1)\) 开始走，只能往下或者往右，且下一步的点上的元素要比上一步的点上的元素恰好大 \(1\)，走到 \((n,m)\) 的最小代价(保证有解)

分析： 最小代价，所以本着尽量少改变的原则，至少有一个点上的元素是不变的，那么我们枚举这个点然后递推一遍求代价就可以了

代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N = 100+10;
#define ll long long
#define INF 1E18

ll dp[N][N],ans;
ll s[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t,n,m;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        rep(i,1,n)rep(j,1,m)
        {
            cin>>s[i][j];
        }  
        ans=INF;
        rep(i,1,n)rep(j,1,m)
        {
            if(s[1][1]<s[i][j]-(i-1)-(j-1)) continue; 
            //这个点与起点距离通过操作无法满足1的等差条件

            rep(x,0,n)rep(y,0,m) dp[x][y]=INF;
            dp[1][1]=s[1][1]-(s[i][j]-(i-1)-(j-1));
            rep(x,1,n)rep(y,1,m)
            {
                if(x==1&&y==1) continue;
                ll res=s[i][j]+(x-i)+(y-j);
                if(s[x][y]<res) continue;
                dp[x][y]=min(dp[x-1][y],dp[x][y-1])+s[x][y]-res;
            }
            ans=min(ans,dp[n][m]);
        }
        cout<<ans<<endl;
    }
}

原文链接: https://www.cnblogs.com/17134h/p/12903202.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    CF #642(div.3)

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/349167

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 上午5:32
下一篇 2023年3月2日 上午5:33

相关推荐