codeforce #381 ABC题解_381abccom

不去吐槽自己的英文水平，不去吐槽自己的思维局限，只说题目意思和解法

A题

题意：我现在有n本书，现在有3种书的套装可以买，a元买1本的套装，b元买2本的套装，c元买3本的套装，套装不能拆开卖。问：我最少需要花多少钱，可以使得我的书的总数可以被4整除

分析：n如果直接是4的倍数，答案是0；余数分三种情况：

余数为3：买1本？！不一定！买5本？！买9本？！

因为要求是花最少的钱，那么买多少本书其实不重要，有多少种花钱方式比较重要（类似dp的思维）

买1本：花a元；买5本，花b+c元；买9本，花3*c元（这些都是有可能构成最小花费的）

余数为2和余数为1也是相同的思考方法

来说两种代码：一种dp，一种枚举的

#include<bits/stdc++.h>
using namespace std;
 
#define LL __int64
LL n,a,b,c,ans;
LL dp[100];
 
int main(){
    while(cin>>n>>a>>b>>c){
        dp[1]=a;
        dp[2]=min(dp[1]+a,b);
        dp[3]=min(c,min(dp[2]+a,dp[1]+b));
        for(int i=4;i<=10;i++)
            dp[i]=min(dp[i-1]+a,min(dp[i-2]+b,dp[i-3]+c));
        if (n%4==0) puts("0");
        else if (n%4==1) cout<<min(dp[3],dp[7])<<endl;
        else if (n%4==2) cout<<min(dp[2],dp[6])<<endl;
        else cout<<min(dp[1],min(dp[5],dp[9]))<<endl;
    }
    return 0;
}
 
#include<bits/stdc++.h>
using namespace std;
 
#define LL __int64
LL n,a,b,c,ans;
LL dp[100];
 
int main(){
    while(cin>>n>>a>>b>>c){
        if (n%4==0) ans=0;
        else if (n%4==1){
            ans=c;
            ans=min(3*a,ans);
            ans=min(a+b,ans);
        }
        else if (n%4==2){
            ans=b;
            ans=min(a+a,ans);
            ans=min(c+c,ans);
        }
        else{
            ans=a;
            ans=min(b+c,ans);
            ans=min(3*c,ans);
        }
        cout<<ans<<endl;
    }
    return 0;
}
 

B题：看懂了题的话，要求最大值：我们只需要去判断每个的计算是不是正的

要计算【a，b】区间内的和，必须用前缀和啊，所以就暴力跑一圈吧，注意初始化是0就好了

#include<bits/stdc++.h>
using namespace std;
 
const int maxn=150;
int n,m;
int a[maxn];
int sum[maxn];
 
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        sum[0]=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sum[i]=a[i]+sum[i-1];
        }
        int ans=0,u,v;
        while(m--){
            scanf("%d%d",&u,&v);
            if (sum[v]-sum[u-1]>0) ans+=sum[v]-sum[u-1];
        }
        printf("%d\n",ans);
    }
    return 0;
}

C题：读题是个很麻烦的事情：重点应该是这句话的吧

The mex of a set S is a minimum possiblenon-negative integer that is not in S.

在集合S中mex这个值，是S集合中的没有出现过的最小的非负整数（会博弈论的话，SG函数要用这个）

m个区间中都取mex，然后找到这样的最大值

 

其实：答案很简单：就是最小的区间长度：想想为什么？

因为没有出现过的最小的非负整数！意思是：我们要想那个值最大，就必须从0开始起来编号对吧

拿第一个样例来说，我们必须0 1 0 1的编号，那么答案才会是2（最小的区间长度）

那么，这个题就成了简单构造题

 
#include<bits/stdc++.h>
using namespace std;
 
int n,m,u,v;
 
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        int ans=n+1;
        while(m--){
            scanf("%d%d",&u,&v);
            ans=min(ans,v-u+1);
        }
        printf("%d\n",ans);
        for(int i=1;i<=n;i++)
            printf("%d%c",i%ans,i==n?'\n':' ');
    }
    return 0;
}