Codeforces Round #681 (Div. 2, based on VK Cup 2019-2020

A:http://codeforces.com/contest/1443/problem/A

解析:

考虑从2*n开始,每次+2构造

#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int maxn=1e5+10,maxn2=31*maxn;
int n,m;
int a[500];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int cnt=0;
        for(int i=2*n;i<=4*n;i+=2)
        {
            a[i]=1;
            cnt++;
            if(cnt==n)
                break;
        }
        for(int i=2*n;i<=4*n;i++)
            if(a[i])
                cout<<i<<" ";
        cout<<endl;
    }
} 

B:http://codeforces.com/contest/1443/problem/B

题意:

只含01的字符串。引爆一次花费a,放置一个炸弹花费b。

1为炸弹,0为无炸弹

炸一个1,与他周边相连的1都会炸掉。

求消除掉所有1的最小花费。(可以通过增加炸弹,来达到相邻引爆的目的)

解析:

思路均为贪心

1:首先是较为好理解的贪心思路。

求出所有1连通块的数量 x +每两个连通块之间0的数目(设0总数y)

列出两个极端情况:

(1)一个炸弹不放,直接一块一块地引爆,花费是x*a

(2)每个连通块之间的0都放上炸弹,花费是y*b+a

那么其他情况,就处于这两个值之间。把收集起来的每两个连通块之间0的数目存到d[],对其进行排序。

根据贪心,对每个(1*a,2*a....x*a),括号里表示,需要引爆的连通块数量,它们需要再加上补炸弹的数目*b,而这个数目正是d[]里的数,根据贪心,肯定从小往大来。说的有点多了,举个例子:

100110001110000100

1连通块数:4

d[每两个连通块之间0的数目]==2,3,4

需要求最小值的就是:4*a+0*b,3*a+2*b,2*a+5*b,a+9*b

代码:

#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=1e5+10,maxn2=31*maxn;
int n,m;
int a[maxn],b[maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x,y;
        string s;
        cin>>x>>y;
        cin>>s;
        int le=s.length();
        int fl=0;
        for(int i=0;i<le;i++)
        {
            if(s[i]=='1')
            {
                fl=1;break;
            }
        }
        if(!fl)
        {
            cout<<"0"<<endl;continue;
        }
        int ok=-1;
        int cnt=0;int sum=0,cnt1=0;
        for(int i=0;i<le;i++)
        {
            if(s[i]=='1')
            {
                ok=0;
                cnt++;
            }
            else
            {
                if(!ok)
                {
                    sum++;
                    ok=1;
                }
            }
        }        
        if(!ok)
            sum++;
        int minn=sum*x;
    //    cout<<sum<<endl;
        int tota=0,totb=0;
        for(int i=0;i<le;i++)
        {
            if(s[i]=='1')
            {
                a[tota++]=i;
            }
        }
        for(int i=0;i<tota-1;i++)
        {
            if(a[i+1]-a[i]==1)
                continue;
            b[totb++]=a[i+1]-a[i]-1;
        //    cout<<a[i]<<"--"<<a[i-1]<<"  "<<i<<endl;
        }
        sort(b,b+totb);
        int md=0;
        cnt=0;
        for(int i=0;i<totb;i++)
        {
            md+=b[i];
            cnt++;
            minn=min(minn,(sum-cnt)*x+md*y);
        }
        cout<<minn<<endl;
    }
    return 0;
}
//1
//5 3
//1001101

2:

其实根据前面的,对于第一个连通块往后的连通块,无非就两种选择:直接引爆或者把之前的0补上再跟随引爆。

第一个块肯定是要引爆的。后面的可能会跟随引爆,需要补b,不需要加a。也可能会自我引爆,这个时候直接+a

贪心取最小值即可。

这种贪心策略并不会影响后面的结果。

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#include<map>
typedef long long ll;
const int maxn=1e5+10;
const int maxn2=3e6+10;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a,b;
        cin>>a>>b;
        string s;
        cin>>s;
        int le=s.length();
        int l=-1;
        int sum=0;
        for(int i=0;i<le;i++)
        {
            if(s[i]=='1')
            {
                if(l<0)
                {
                    sum=a;
                    l=i;
                }
                else
                {
                    sum+=min(a,(i-l-1)*b);
                    l=i; 
                }
            }
        }
        cout<<sum<<endl;
    }
}

C:http://codeforces.com/contest/1443/problem/C

题意:

n个所需物品

a[]表示每个物品,商家配送所需时间

b[]表示每个物品,到店取所需时间

取这n个所需最短时间。

解析:

b[]的分析明显很麻烦,先看a[]

假设我们定a[]的某个值为最大值maxx,那么所有小于它的,都要选被配送,不会增加耗时,以最大值为准。

所以可以考虑枚举每个a[],以此定为最大值,把对应所需b[]的花费求出来,取个min(max)即可。

这里使用了vector<pair<ll,ll>来记录成对量并进行捆绑排序,第一次用,很值得学习。

#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=2e5+10,maxn2=31*maxn;
const int inf=1e18+10;
ll a[maxn],b[maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        ll sumb=0;
        for(int i=1;i<=n;i++)
            cin>>b[i],sumb+=b[i];
        vector<pair<ll,ll> >pp;
        for(int i=1;i<=n;i++)
        {
            pp.push_back(make_pair(a[i],b[i]));
        }
        sort(pp.begin(),pp.end());
        ll sum = sumb;
    //    cout<<sumb<<endl;
        for(int i=1;i<=n;i++)
        {
            sumb-=pp[i-1].second;
            sum=min(sum,max(sumb,pp[i-1].first));
        }
        cout<<sum<<endl;
    }
    return 0;
}

 vector pair自定义排序:

bool cmp(const pair<int, char> a, const pair<int, char> b) {
    return a.first<b.first;//自定义的比较函数
}
 sort(p.begin(), p.end(), cmp);
原文地址:https://www.cnblogs.com/liyexin/p/13922740.html