Educational Codeforces Round 112 (Rated for Div. 2)(部分题解!)

本文主要是介绍Educational Codeforces Round 112 (Rated for Div. 2)(部分题解!)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. PizzaForces

A. PizzaForces
题意：易懂，略
思路：简单贪心即可，把n分成这样的形式n=10+x+10y，那么10y个人用y个large蛋糕，剩下的10+x用三种蛋糕组合看哪个最省时间

AC_code:


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){int t;cin>>t;while(t--){ll n;cin>>n;ll temp = n%10;ll ans = n/10;ll sum = 0;if(ans==0){if(temp<=6)sum+=15;else if(temp<=8){sum+=20;}else sum+=25;}else{if((temp==0||temp==2||temp==4||temp==6||temp==8)){sum = n*2.5;}else{sum = (ans-1)*25;if(temp==1) sum+=30;else if(temp==3) sum+=35;else if(temp==5) sum+=40;else if(temp==7) sum+=45;else if(temp==9) sum+=50;}} cout<<sum<<'\n';}return 0;
}

C. Coin Rows

C. Coin Rows
题目大意：现在有2*n的格子，每一个格子有一个权值，现在Alice和Bob都在(1,1)这个点，规定他们只能向下或者向右走，Alice先从(1,1)走到 (2,n)并且Alice会把所经过的格子(包括起点)的权值变为0，然后Bob从(1,1)走到 (2,n)，现在Alice想让Bob经过的路径权值之和最小，而Bob想让自己经过的路径权值之和最大，两人都采用最优策略，问最后Bob的权值之和是多少？

思路: 显然，我们不难发现，当Alice走了之后，Bob有且只有两种走法能够使它路径权值之和最大，分别是7形和L形走法，所以我们只需要考虑Alice怎么样走才能让Bob路径权值之和最小,用前缀和处理一下路径权值之和即可

AC_code:

#include<bits/stdc++.h>
using namespace std;
const int Maxn = 1e5+10;
int sum1[Maxn]={0};
int sum2[Maxn]={0};
int main(){int t;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=n;i++){int di;cin>>di;sum1[i] = sum1[i-1]+di;}for(int i=1;i<=n;i++){int di;cin>>di;sum2[i] = sum2[i-1]+di;}int ans = 1e9+10;for(int i=1;i<=n;i++){ans = min(ans,max(sum1[n]-sum1[i],sum2[i-1]));}cout<<ans<<'\n';}return 0;
}

D. Say No to Palindromes

D. Say No to Palindromes
题意：给你一个字符串只由abc组成，现在你可以对字符串的任何位置的字符修改为a或b或c，问你最少需要修改多少次，使得这个字符串的长度大于1的所有子串都不是回文串

思路：字符串只有abc三个字符构成，所以任意三个相邻的字符串都不能重复，例如：abcabcabc，然后我们可以发现，满足要求的字符串是有循环节并且长度为3，所以循环节的形态一共有6种，分别是abc，acb，bac，bca，cab，cba，所以我们只需要把原字符串分别修改成这六种循环节形式的字符串，然后取最小的那个修改次数即可.所以我们设 $d p [i] [j]$ 表示前j个字符修改成第i种循环节形式的修改次数，对于[L,R]的询问,1<=i<=6,min(dp[i][r]-dp[i][l-1])就是答案

AC_code:

#include<bits/stdc++.h>
using namespace std;
const int Maxn = 2e5+10;
string s[6] = {"abc","bac","acb","bca","cab","cba"};
string str;
int n,m;
int f[6][Maxn]={0};//dp[i][j]表示前i个字符修改为第i个回文串的方式，原字符串需要修改多少个字符 
void solve(){for(int i=0;i<6;i++){for(int j=1;j<=n;j++){f[i][j] = f[i][j-1]+(s[i][(j-1)%3]!=str[j-1]);}}return ;
}
int main(){cin>>n>>m;cin>>str;solve();while(m--){int l,r;cin>>l>>r;int res = Maxn;for(int i=0;i<6;i++){res = min(res,f[i][r]-f[i][l-1]);}cout<<res<<'\n';}return 0;
}

E. Boring Segments

E. Boring Segments
题目大意：略
思路：这题其实说的不是区间覆盖,而是能够连通,
例如[1,3]和[4,5]是不连通的,因为线段之间没有相交
而[1,3]和[3,5]是连通的.
处理方法是将m–,每条线段的右端点r–,
这样的话就不需要判相交,只需要判断是否覆盖了[1,m]就行了.
经典的区间连通操作，把所有给定的区间和询问的区间右端点-1即可,然后判断一个区间是否连通，只需要判断这个区间的最小值是否为0即可，这样就可以用线段树维护区间最小值来解决了

AC_code:

#include<bits/stdc++.h>
#define ls dep<<1
#define rs dep<<1|1
using namespace std;
const int Maxn = 3e5+10;
const int Maxm = 1e6+10;
int n,m;
typedef struct node{int l,r,val;
}Node;
Node stu[Maxn];
int tr[Maxm*4]={0};
int lazy[Maxm*4]={0};
void pushup(int dep){tr[dep] = min(tr[ls],tr[rs]);return ;
}
void pushdown(int dep){if(lazy[dep]!=0){lazy[ls]+=lazy[dep];lazy[rs]+=lazy[dep];tr[ls]+=lazy[dep];tr[rs]+=lazy[dep];lazy[dep] = 0;pushup(dep);}return ;
}
void update(int l,int r,int ql,int qr,int dep,int val){
//	cout<<l<<' '<<r<<'\n';if(ql<=l&&r<=qr){tr[dep]+=val;lazy[dep]+=val;return ;}pushdown(dep);int mid = l+r>>1;if(ql<=mid) update(l,mid,ql,qr,ls,val);if(qr>mid) update(mid+1,r,ql,qr,rs,val);pushup(dep);return ;
}
int query(int l,int r,int ql,int qr,int dep){if(ql<=l&&r<=qr){return tr[dep];}pushdown(dep);int mid = l+r>>1;int res = 1e6+10;if(ql<=mid) res = min(res,query(l,mid,ql,qr,ls));if(qr>mid) res = min(res,query(mid+1,r,ql,qr,rs));pushup(dep);return res;
}
int cmp(Node a,Node b){return a.val<b.val;
}
int solve(){int res = 1e6+10;int l=1,r=1;update(1,m,stu[1].l,stu[1].r,1,1);    while(l<=r&&r<n){while(query(1,m,1,m,1)&&l<=r){res = min(res,stu[r].val-stu[l].val);update(1,m,stu[l].l,stu[l].r,1,-1);l++;}r++;update(1,m,stu[r].l,stu[r].r,1,1);}while(query(1,m,1,m,1)&&l<=r){res = min(res,stu[r].val-stu[l].val);update(1,m,stu[l].l,stu[l].r,1,-1);l++;}return res;
}
int main(){scanf("%d %d",&n,&m);m--;for(int i=1;i<=n;i++){scanf("%d %d %d",&stu[i].l,&stu[i].r,&stu[i].val);stu[i].r--;}sort(stu+1,stu+n+1,cmp);printf("%d",solve());return 0;
}