codeforce #381 ABC题解
不去吐槽自己的英文水平，不去吐槽自己的思维局限，只说题目意思和解法
题意：我现在有n本书，现在有3种书的套装可以买，a元买1本的套***元买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;
}
